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

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

f(x₁,x₂,...,x_n)®max, (6.3)

g_i(x₁,x₂,...,x_n)£b_i (i=1,..., m), (6.4)

x_i³0 (j=1,...,n), (6.5)

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

Для решения сформулированной задачи в такой общей постановке не существует универсальных методов.

Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и g_i, разработаны эффективные методы их решения.

В частности, ряд таких методов имеется для решения ЗНЛП (6.3) — (6.5) при условии, что f — вогнутая (выпуклая) функция и ОДР, определяемая ограничениями (6.4) — (6.5), — выпуклая.

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

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

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

Если введенные выше неравенства выполняются как строгие, функция f(x) — строго выпуклая или строго вогнутая соответственно.

Сумма выпуклых (вогнутых) функций есть выпуклая (вогнутая) функция.

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

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

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

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

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

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

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

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