5. Теория двойственности в выпуклом программировании.

Рассмотрим задачу . Будем предполагать, что множество планов этой задачи регулярно. Тогда для нее справедлива теореме Куна-Таккера. По параметрам задачи (1) составим функцию Лагранжа, и будем строить две функции.

(22)

(23)

называется прямой, – двойственной для задачи (1). Рассмотрим две задачи:

(24)

(25)

Задачу (24) называют прямой, а (25) – двойственной для задачи (1). Множество называется множеством прямых планов, а множество – множеством двойственных планов.

Рассмотрим множество прямых планов. По определению функции получаем: . Тогда видно, что множество прямых планов (24) в точности совпадает с множеством планов основной задачи выпуклого программирования и на этом множестве . Это означает, что задачи (24) и (1) идентичны (одинаковы).

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

Теорема. (Соотношения двойственности)

1. Справедливо неравенство , . (26)

2. Если оптимальный план задачи (24), то тогда – оптимальный план задачи (25), причем

. (27)

3. Если – оптимальные планы задач (24), (25), то на них выполняется условие .

4. 4.1) Если на некоторой последовательности двойственных планов , то .

2. Если на некоторой последовательности , то множество двойственных планов пусто.

5. Для того чтобы были оптимальными планами (24), (25) необходимо и достаточно, чтобы пара была седловой точкой функции Лагранжа для задачи (1).

6. Если для некоторых планов выполняется , то они являются оптимальными планами (24), (25).

Доказательство.

1) Из определений (22), (23) следует, что .

Остальные соотношения (2)-(5) доказываются по той же логической схеме, что и соотношения двойственности в линейном программировании.

Ч.т.д.

6. Решение одной задачи выпуклого программирования.

Рассмотрим следующую задачу оптимизации

. (28)

В (28) – симметричная матрица, .

Очевидно, что (28) – задача со строго выпуклыми функциями и линейными ограничениями и имеет форму основной задачи выпуклого программирования с равенствами. Для этой задачи справедлива теорема Куна-Таккера, причем . Построим для задачи (28) функцию Лагранжа.

и будем строить двойственную функцию: . Поскольку функция Лагранжа при строго выпукла, то достигается в стационарной точке, то есть там, где (29)

Составим условие стационарности:

(30)

Отсюда получаем:

. И построим двойственную задачу: (31)

Нетрудно убедиться, что функция является строго вогнутой относительно (для этого нужно взять вторую производную по от и убедиться в том, что это будет матрица отрицательная). И поэтому задача (31) всегда имеет оптимальный план, и он достигается в стационарной точке

(32)

Составляем условие стационарности (32)

.

Отсюда находим оптимальный план (31), получаем:

– оптимальный план (31).

По теории двойственности тогда существует оптимальный план и прямой задачи, которая совпадает с (28) и он имеет вид:

Таким образом, теория двойственности позволяет для задачи (28) сразу получить оптимальный план в явной форме. Задача (28)относится к задачам квадратичного программирования, то есть к задачам с квадратичной целевой функцией и линейными ограничениями.