Задачи выпуклого программирования

Пусть исходная задача имеет вид:

Задача называется задачей выпуклого программирования, если выполняются следующие условия:

1. — вогнутая функция, то есть для.

• 2. область допустимых решений выпуклая
• 3. область регулярная, то есть существует по крайней мере одна внутренняя точка

Можно построить функцию Лагранжа:

Теорема 8: точка является оптимальным решением задачи выпуклого программирования тогда и только тогда, когда существует вектор такой, что для функции Лагранжа выполняются условия:

1.

2. условия дополняющей не жесткости:

3.

Условия называются условиями Куна — Таккера.

В общем случае система уравнений и неравенств слишком сложна для аналитического решения. Однако в задачах квадратичного программирования есть способы решения этой системы условий, сводящиеся к нахождению опорных решений систем линейных алгебраических уравнений.

Геометрический смысл условий Куна-Таккера:

Если все, , то условия дополняющей не жесткости запишутся в виде.

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