Решение задачи выпуклого программирования
Рассмотрим задачу выпуклого программирования, в которой ОДР задается системой неравенств:Z = f (x1,…, xn) → max (min), (14)
gi (x1,…, xn) ≤ bi,
![](https://www.semestr.ru/images/math/math/n1_image003.gif)
Выпишем для нее функцию Лагранжа:
L(x, λ) = L(x1,…, xn, λ 1,…, λ m) = f (x1,…, xn) +
![](https://www.semestr.ru/images/math/math/n1_image048.gif)
Обозначим I =
![](https://www.semestr.ru/images/math/math/n1_image049.gif)
![](https://www.semestr.ru/images/math/math/n1_image004.gif)
Теорема 7. Пусть решается задача максимизации (14) – (15), причем функция f вогнутая, функции g1,…, gm выпуклые, все функции непрерывно дифференцируемые и выполнено одно из следующих условий регулярности:
1. существует точка x', такая что gi(x') < bi для всех
![](https://www.semestr.ru/images/math/math/n1_image051.gif)
2.
![](https://www.semestr.ru/images/math/math/n1_image052.gif)
![](https://www.semestr.ru/images/math/math/n1_image053.gif)
3. градиенты ограничений {
![](https://www.semestr.ru/images/math/math/n1_image054.gif)
В этом случае точка
![](https://www.semestr.ru/images/math/math/n1_image004.gif)
![](https://www.semestr.ru/images/math/math/n1_image038.gif)
![](https://www.semestr.ru/images/math/math/n1_image040.gif)
![](https://www.semestr.ru/images/math/math/n1_image055.gif)
![](https://www.semestr.ru/images/math/math/n1_image003.gif)
![](https://www.semestr.ru/images/math/math/n1_image056.gif)
![](https://www.semestr.ru/images/math/math/n1_image003.gif)
Соотношения (16) – (18) называются условиями Куна-Таккера, а вектор
![](https://www.semestr.ru/images/math/math/n1_image057.gif)
Условие (16) можно записать в векторной форме:
![](https://www.semestr.ru/images/math/math/n1_image058.gif)
![](https://www.semestr.ru/images/math/math/n1_image059.gif)
Оно означает, что если выполнено любое из условий регулярности, и точка x* является оптимальным решением задачи ВП, то градиент целевой функции представим в виде линейной комбинации градиентов активных ограничений. Отметим, что если решается задача минимизации выпуклой функции, то это условие выглядит несколько иначе:
![](https://www.semestr.ru/images/math/math/n1_image060.gif)
Условие (17) означает, что если множитель Лагранжа положителен, то соответствующее ему ограничение в точке оптимума обязательно должно быть равенством. Если же ограничение не является равенством в точке оптимума, то его множитель Лагранжа равен нулю. Это условие аналогично условию дополняющей нежесткости в задаче ЛП.
В отличие от классической задачи условной оптимизации на множители Лагранжа накладывается условие неотрицательности (18).
Множители Лагранжа допускают интерпретацию, аналогичную интерпретации оптимальных оценок ограничений в задаче ЛП. Так множитель Лагранжа i-го ограничения характеризует величину изменения оптимального значения ЦФ Z* при увеличении правой части этого ограничения на единицу и фиксированных значениях остальных ограничений. А именно, справедлива формула:
![](https://www.semestr.ru/images/math/math/n1_image061.gif)
Однако в отличие от задачи ЛП величина
![](https://www.semestr.ru/images/math/math/n1_image062.gif)
Множество Х называется выпуклым, если для любой пары точек x, y ∈Х и любого числа α∈(0, 1) точка z = αx + (1 – α)y принадлежит этому множеству, то есть, если это множество вместе со своими любыми двумя точками содержит соединяющий их отрезок.
Линии уровня ЦФ рассматриваемой задачи будут эллипсами при выполнения следующих условий: а2 > 0, b2 > 0 и а2 ≠ b2. Если же а2 > 0, b2 > 0, но а2 = b2, то линии уровня представляют собой семейство окружностей, имеющих общий центр О.