Основная задача выпуклого программирования. Седловая точка и оптимальный план.
Рассмотрим задачу
оптимизации
(1),
в которой
– вектор-функция,
функции
– выпуклые функции;
–
выпуклое множество простой структуры,
то есть подмножество, которое задается
с помощью простейших ограничений на
одну переменную (
).
Задача называется основной задачей
выпуклого программирования.
Любая задача
выпуклого программирования может быть
записана в форме (1). Для этого ограничения
задачи разбиваются на сложные (содержащие
несколько переменных) и простые. Сложные
ограничения формируют основные
(
– количество таких ограничений), а
простые ограничения задают множество
.
В частности, если у задачи простых
ограничений нет, то полагают
.
Докажем, что множество планов задачи
(1) выпукло.
можно представить
как
– выпуклое как пересечение
выпуклого множества. По параметрам
задачи (1) построим функцию:
,
(2)
.
Функция
называется функцией Лагранжа для задачи
(1).
Определение.
Пара
,
где
(3)
называется седловой
точкой
функции Лагранжа.
Теорема. Пусть
известно, что
–
седловая точка функции Лагранжа, тогда
–
оптимальный план основной задачи
выпуклого программирования.
Доказательство. Пусть построена седловая точка. Тогда для нее выполняется неравенство (3), то есть
(3*)
Рассмотрим левое
неравенство (3*),
отбросив одинаковые константы
:
(4)
1) Докажем, что
является планом задачи (1). Поскольку
известно, что
,
то нужно доказать, что
.
Предположим противное:
.
Положим в (4)
.
Тогда из (4):
.
.
Противоречие доказывает 1).
2) Докажем, что выполняются условия дополняющей не жесткости:
.
(5)
От противного
.
Положим в (4)
.
Тогда
.
Это невозможно, поскольку половина
отрицательного числа всегда число
большее, чем оно само.
Докажем, что – оптимальный план. Используем правую часть (3*):
.
– оптимальный план для основной задачи
выпуклого программирования.
Ч.т.д.
Замечание. Условие оптимальности, сформулированное в теореме 1, является достаточным, но необходимым, то есть можно построить такую задачу (1), у которой существует оптимальный план, но по нему нельзя построить седловую точку для соответствующей функции Лагранжа.
Теорема Куна-Таккера.
Определение.
Говорят, что
множество планов основной задачи
выпуклого программирования регулярно,
если существует вектор
(6)
Условие (6) называется условием Слейтера.
Геометрически (6)
означает, что у задачи (1) существует
такой план
,
который является внутренней точкой по
основным ограничениям.
Теорема 2.
(Куна-Таккера)
Для того, чтобы
был оптимальный план основной задачи
выпуклого программирования, для которой
выполняется условие регулярности (6),
необходимо и достаточно, чтобы существовал
такой вектор
такой, что пара
является седловой точкой функции
Лагранжа и при этом выполняется условие
дополняющей не жесткости (5) :
.
Теорема Куна-Такера сводит задачу оптимизации к задаче нахождения седловых точек, а последнее в некоторых случаях сводится к алгебраической задаче.