logo
ммпур методичка

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

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

f (x1, x2, ..., xn)max, (3.3)

gi (x1, x2, ..., xn)bi (i=1, ..., m), (3.4)

xi0 (j=1, ..., n), (3.5)

где f и gi — некоторые функции n переменных x1, x2, ..., xn.

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

Функция f(x1, x2, ..., xn), заданная на выпуклом множестве X, называется выпуклой, если для любых двух точек X1 и X2 из X и любого 01 выполняется соотношение

Функция f(x1, x2, ..., xn), заданная на выпуклом множестве X, называется вогнутой, если для любых двух точек X1, X2 из X и любого 01 выполняется соотношение

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

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

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

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

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

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

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

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

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