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

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

(22)

(23)

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

(24)

(25)

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

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

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

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

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

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

. (27)

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

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

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

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

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

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

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

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

Ч.т.д.