Задачи Выпуклое программирование (примеры)

Пример 1. Рассмотрим задачу

Точка X°=(2,1) — оптимальный план задачи, — функция Лагранжа. Проверим выполнение условий Куна-Таккера:

(5)

Легко видеть, что эти условия выполняются на плане X°=(2,1) при . Таким образом, пара является седловой точкой функции Лагранжа:

Т. е., для любых , и выполняется условие дополняющей нежесткости.

Пример 2. Пусть имеем задачу

(6)

Где — матрица ().

Задача (6) является задачей выпуклого программирования (задача квадратичного программирования). Запишем для нее функцию Лагранжа

Тогда двойственная функция запишется в виде:

. (7)

Так как функция Лагранжа строго выпукла по X (D>0), то точка минимума X(l) задачи (7) совпадает со стационарной точкой функции Лагранжа:

Найденное значение подставим в функцию Лагранжа. Тогда

Из теории матриц известно, что , если , и, значит, функция является строго вогнутой. Следовательно, ее точка максимума совпадает с ее стационарной точкой, т. е.

Итак, l° — решение двойственной задачи , к задаче (6). Подставив в выражение для X(l) вектор l° получим решение X°=X(l°) исходной задачи (6).