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

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

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

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

2. Область допустимых решений выпуклая.

3. Область регулярная, то есть существует по крайней мере одна внутренняя точка .

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

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

1.

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

3.

Условия (14) называются условиями Куна-Таккера, а точка – точкой Куна-Таккера

Рассмотрим геометрический смысл условий Куна-Таккера.

Из первого условия (14.2) следует, что если все , , то

Второе условие (14.2), так как , запишется в виде

и означает, что для неактивных ограничений .

Тогда из условий дополняющей нежесткости следует

(15)

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

Если в оптимальной точке какая-либо координата , то вместо градиентов функций и рассматриваются их проекции на плоскость, перпендикулярную оси .

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