3.2. Выпуклое программирование Постановка задачи выпуклого программирования.

Рассмотрим задачу нелинейного программирования:

f (x₁, x₂, ..., x_n)max, (3.3)

g_i (x₁, x₂, ..., x_n)b_i (i=1, ..., m), (3.4)

x_i0 (j=1, ..., n), (3.5)

где f и g_i — некоторые функции n переменных x₁, x₂, ..., x_n.

Для решения сформулированной задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и g_i, разработаны эффективные методы их решения. В частности, ряд таких методов имеется для решения ЗНЛП (3.3) — (3.5) при условии, что f — вогнутая (выпуклая) функция и ОДР, определяемая ограничениями (3.4) — (3.5), — выпуклая.

Функция f(x₁, x₂, ..., x_n), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек X₁ и X₂ из X и любого 01 выполняется соотношение

Функция f(x₁, x₂, ..., x_n), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X₁, X₂ из X и любого 01 выполняется соотношение

Если f (X) — выпуклая функция, то –f (X) — вогнутая функция, и наоборот.

Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция. Задача (3.3) — (3.5) является задачей выпуклого программирования, если функция f(x₁, x₂, ..., x_n) является вогнутой (выпуклой), а функции g_i (X) (i=1, ..., m) — выпуклыми.

Т е о р е м а. Любой локальный максимум (минимум) задачи выпуклого программирования является глобальным максимумом (минимумом).

Говорят, что множество допустимых решений задачи (3.3) — (3.5) удовлетворяет условию регулярности, если существует по крайней мере одна точка X_i, принадлежащая ОДР такая, что g_i (X_i)<b_i (i=1,..., m).

Функцией Лагранжа задачи выпуклого программирования (3.3) — (3.5) называется функция

Точка называется седловой точкой функции Лагранжа, если для всех и

Центральное место в теории нелинейного программирования занимает теорема Куна — Таккера.

Для задачи выпуклого программирования (3.3) — (3.5), множество допустимых решений которой обладает свойством регулярности, X₀ тогда и только тогда является оптимальным решением, когда существует такой вектор , что — седловая точка функции Лагранжа.

Эта теорема называется также теоремой о седловой точке.