Главная страница Случайная страница Разделы сайта АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатикаИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханикаОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторикаСоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансыХимияЧерчениеЭкологияЭкономикаЭлектроника |
Задачи выпуклого программирования
Пусть исходная задача имеет вид:
Задача (11-13) называется задачей выпуклого программирования, если выполняются следующие условия: 1. – вогнутая функция, то есть для . 2. Область допустимых решений выпуклая. 3. Область регулярная, то есть существует по крайней мере одна внутренняя точка .
Можно построить функцию Лагранжа Теорема 8: точка является оптимальным решением задачи выпуклого программирования тогда и только тогда, когда существует вектор такой, что для функции Лагранжа выполняются условия
1. 2. условия дополняющей нежесткости: 3.
Условия (14) называются условиями Куна-Таккера, а точка – точкой Куна-Таккера
Рассмотрим геометрический смысл условий Куна-Таккера. Из первого условия (14.2) следует, что если все , , то Второе условие (14.2), так как , запишется в виде Тогда из условий дополняющей нежесткости следует (15) то есть градиент функции в оптимальной точке является линейной комбинацией с положительными коэффициентами градиентов к активным ограничениям. Иными словами, градиент критерия лежит в геометрическом конусе градиентов ограничений. Если в оптимальной точке какая-либо координата , то вместо градиентов функций и рассматриваются их проекции на плоскость, перпендикулярную оси .
В общем случае система уравнений и неравенств (14) слишком сложна для аналитического решения. Однако в задачах квадратичного программирования есть способы решения этой системы условий, сводящиеся к нахождению опорных решений систем линейных алгебраических уравнений.
|