Выпуклое программирование

Общая задача выпуклого программирования имеет вид

(6.4.1)

где – выпуклые функции, – выпуклое множество.

Будем обозначать – область определения функции, т.е. множество на котором функция определена, а за его пределами не определена.

Условия экстремума. Необходимые и достаточные условия задачи (6.4.1) сформулированы в следующей теореме.

Теорема 17 (Кун-Таккер). Пусть , i=1,…,m, – выпуклые функции, – выпуклое множество, входящее в области определения функций и выполняется условие Слейтера: найдется такое, что

(6.4.2)

Тогда допустимая точка является глобальным решением (6.4.1), если и только если найдутся такие, что:

и (6.4.3)

, (6.4.4)

где и

, (6.4.5)

Как и ранее функцию будем называть функцией Лагранжа, вектор – множителями Лагранжа, – прямыми переменными, – двойственными переменными, условие – условием дополняющей нежесткости, набор индексов – множеством активных ограничений. Если для задачи (6.4.1) выполнены условия теоремы 1, то будем говорить о регулярной точке минимума или регулярной задаче.

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

Пусть – два множества. Пара называется седловой точкой функции на , если

(6.4.6)

т.е. точка является точкой минимума по на , а – точкой максимума по на . Выражение (6.4.6) эквивалентно равенству

. (6.4.7)

Наличие седловой точки означает возможность перестановки операций минимума и максимума.

Теорема 18 (Кун-Таккер). В условиях теоремы 1 является решением задачи (6.4.1) тогда и только тогда, когда пара при некотором является седловой точкой на , т.е.

(6.4.8)

Двойственность. Симметрия относительно переменных и в (6.4.8) для задачи минимизации (6.4.1) по позволяет наедятся найти экстремальную задачу относительно переменных для которой также справедливы условия (6.4.8). Введем функцию

(6.4.9)

Поэтому исходная задача (6.4.1) может быть записана

. (6.4.10)

Образуем задачу, поменяв роль переменных и операций максимума и минимума. Введем

(6.4.11)

(возможно, что при некоторых ) и рассмотрим задачу

. (6.4.12)

Задача (6.4.12) называется двойственной, а (6.4.1) или (6.4.10) – прямой.

Теорема 19 (теорема двойственности). Справедливы соотношения двойственности:

а) Для любых допустимых и (т.е. для )

. (6.4.13)

б) Если прямая задача регулярна, – ее решение, – множители Лагранжа, то – решение (6.4.12) и

. (6.4.14)

в) Если для допустимых, , имеет место (6.4.14), то – решение прямой, а – решение двойственной задачи.

Максимум y(y) может достигаться лишь в точках, где . Поэтому (6.4.12) равносильна задаче

(6.4.15)

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

Единственность решения (6.4.1) гарантируется строгой выпуклостью функции .