Выпуклый анализ. Теория двойственности. Лекция 27

1. ВЫПУКЛЫЙ АНАЛИЗ

ЛЕКЦИЯ 27
10. ТЕОРИЯ ДВОЙСТВЕННОСТИ

2.

10. ТЕОРИЯ ДВОЙСТВЕННОСТИ
10.1. Постановка двойственной задачи.
10.2. Теорема двойственности.

3.

10.1. Постановка двойственной задачи. Рассмотрим задачу выпуклого
программирования
I ( u ) ® inf, u Î U ,
U = { u Î U 0 gi ( u ) £ 0, i = 1,L , m; g i ( u ) = 0, i = m + 1,L , s} ,
Пусть
L : U 0 ´ L 0 ® R1 -
ее регулярная
функция Лагранжа. Рассмотрим функцию
c : U 0 ® R1 ,
определенную формулой
ì
ü
æ l1 ö
li ³ 0, ï
ï
ç ÷
0
s
L = íl = ç L ÷ Î R
ý
i
=
1,
L
,
m
ï
ï
çl ÷
è sø
î
þ
s
é
ù
c (u ) = sup L ( u, l ) = sup0 ê I ( u ) + å li g i (u ) ú , u Î U 0 .
lÎL ë
i =1
û
lÎL 0
Нетрудно видеть, что
³ 0,
i =1,L , m
s "знак i = m +1,L s
u Î U Þå
и при
i =1
l = 0 Î L0
Пусть
li
×
gi (u )
£ 0, "l Î L 0
неравенство переходит в равенство.
либо $ i Î { 1,L , m} : g i (u ) > 0,
u ÎU 0 \ U Þ
либо $ i Î { m + 1,L , s} : gi (u ) ¹ 0.
s
Тогда величина
£ 0, i =1,L , m ,
0, i = m +1,L s
å l g (u )
i =1
i
i
выбором вектора
угодно большой. Отсюда выводим равенство
l Î L0
может быть сделана сколь

4.

64 7£0 48 ö
ì
æ
s
ï
ç
÷
u ÎU ,
ïsup0 ç I (u ) + å li gi (u ) ÷ ,
=
c (u ) = sup L ( u, l ) = ílÎL ç
i =1
÷
lÎL 0
ï
è
ø
ï
+¥,
u ÎU 0 \ U .
î
u ÎU ,
ì I (u ),
c (u ) = inf I (u ) = I* .
=í
Þ uinf
ÎU 0
uÎU
+¥
,
u
Î
U
\
U
0
î
Тогда исходную задачу можно переписать в виде.
Задача 1.
Наряду с функцией
c (u ) ® inf, u Î U 0 .
c рассмотрим функцию y : L 0 ® R1 ,
определенную
y (l ) = inf L( u, l ) , l Î L0
формулой
и сконструируем задачу.
Задача 2.
uÎU 0
y ( l ) ® sup,
l Î L0 .
Определение 1. Задача 2 называется двойственной к задаче 1 (основной).
Переменные
u 1 , , u n
двойственными.
называются основными, а переменные
l1 ,L , ls -

5.

Обозначим через
{
}
*
y
= supy ( l )
L = l Î L y ( l ) =y ,
0
*
*
*
0
*
lÎL
множество всех решений двойственной задачи и оптимальное значение ее целевой
функции, соответственно.
10.2. Теорема двойственности. Установим связь между оптимальными значениями
целевых функций основной и двойственной задач.
Теорема 1. Имеет место неравенство
y * = supy ( l ) £ inf I (u ) = I * .
uÎU
lÎL 0
Доказательство. Для всех
u ÎU 0 , l Î L0
справедливо
y ( l ) = inf L ( u, l ) £ L ( u, l ) .
( 1)
uÎU 0
Возьмем точную верхнюю грань по переменной
l ÎL
0
от обеих частей (1)
y * = supy ( l ) £ sup0 L ( u, l ) = c (u ), " u Î U 0 .
lÎL 0
lÎL
( 2)

6.

Переходя в неравенстве (2)
" u ÎU 0 ,
получим
y * £ c (u )
( 2)
к точной нижней грани по переменной
y * £ inf c (u ) = I * Þ y * £ I * .
uÎU
0
Теорема доказана.
Теорема 2 (двойственности). Для того чтобы было выполнено
U * ¹ Æ, L * ¹ Æ , I * = y *
( 3)
необходимо и достаточно, чтобы функция Лагранжа имела седловую точку на
множестве
U 0 ´ L0.
множеством
Множество седловых точек функции Лагранжа совпадает с
{
}
U * ´ L* = ( u* , l * ) u* Î U * , l * Î L * .
Доказательство. Необходимость. Пусть выполнены соотношения (3).
для любых
u * ÎU * , l* Î L*
Лагранжа.
Имеем
y =y ( l
*
*
)
пара
*
*
является седловой точкой для функции
y ( l ) = inf L ( u , l )
uÎU 0
=
£ sup L(u* , l )
lÎL 0
(u , l )
Покажем, что
inf L(u , l * ) £ L(u* , l * ) £
uÎU 0
sup L ( u , l ) = c ( u )
lÎL 0
=
c ( u* ) = I * .
( 4)

7.

I* = y * .
По условию необходимости
Тогда из неравенства (4)
y * = inf L(u, l * ) £ L(u* , l * ) £ sup L(u* , l ) = I *
uÎU 0
lÎL
0
( 4)
следует, что
sup L(u* , l ) = L(u* , l * ) = inf L(u, l * ).
uÎU 0
lÎL 0
Последнее равенство означает, что
( 5)
L(u* , l ) £ L(u* , l * ) £ L(u , l * ), " u Î U 0 , " l Î L 0 .
Таким образом, пара
( u , l ) - седловая точка.
*
*
Отсюда также следует,
U * ´ L* вложено в множество седловых точек функции Лагранжа.
доказана.
Достаточность. Пусть
Тогда
( u , l ) ÎU
*
*
0
´
L
0
L(u* , l ) £ L(u* , l * ),
что множество
Необходимость
седловая точка функции Лагранжа.
"l Î L 0 .
Отсюда следует
sup L(u* , l ) = c ( u* ) £ L(u* , l * ).
lÎL 0
Аналогично из неравенства
( 6)

8.

L(u * , l* ) £ L(u, l* ), " u ÎU 0
выводим
inf L(u, l * ) = y ( l * ) ³ L(u* , l * ).
( 7)
uÎU 0
sup L(u* , l ) = c ( u* ) £ L(u* , l * )
Из (7),(6)
lÎL
0
( 7)
L(u* , l ) £ y ( l
*
*
)
y * = sup y ( l )
lÎL0
y*
£
y * £ I*
теорема 1
£
( 6)
в силу теоремы 1 получим
I* = inf c ( u )
I*
uÎU 0
£
( 6)
c (u* ) £ L(u* , l * )
y ( l * ) = y * = I * = c ( u* ) Þ
Тогда
y * = I* ,
u* Î U * , l * Î L *
Отсюда выводим, что множество седловых точек функции Лагранжа вложено в
множество
U * ´ L* .
Теорема доказана.
Отсюда, в частности следует, что если пары
(u*( ) , l *( ) ), (u*( ) , l *( ) ) Î U 0 ´ L 0
1
1
2
образуют седловые точки функции Лагранжа,
2
то и пары

9.

(u*( 2) , l *( 1) ), (u*( 1) , l *( 2) ) Î U 0 ´ L 0
также являются седловыми точками. Тогда множители Лагранжа в теореме Куна – Таккера
можно выбирать одними и теми же для всех
u* Î U * .
Замечание. В доказательстве теоремы двойственности нигде не использовался тот
факт, что исходная задача является задачей выпуклого программирования. Таким образом,
теорема двойственности верна и для произвольной задачи математического
программирования.
Очевидно, что если пара
Лагранжа, то пара
(u * , l* ) Î U 0 ´ L0
(uˆ , lˆ ) ÎU 0 ´ L0
образует седловую точку функции
определенная из условия
L(uˆ , lˆ ) = L(u * , l* )
не обязана быть седловой точкой. Более того пусть
(u* , l * ) Î U 0 ´ L 0 - седловая
точка функции Лагранжа. Рассмотрим множества
U * ( l * ) = { u Î U 0 L(u , l * ) = L(u* , l * )} ,

10.

{
}
L ( u* ) = l Î L 0 L(u* , l ) = L(u* , l * ) .
В общем случае выполняется лишь
U * Ì U * ( l * ) , L* Ì L* ( u* ) .
Пример 1. Пусть
L ( u , l ) = l u , U 0 = L 0 = R1.
*
(
u
,
l
) = ( 0, 0 ) ,
Данная функция имеет единственную седловую точку
*
U * ( l * ) = L * ( u* ) = R1.
Существуют задачи выпуклого программирования, для которых y
*
а
< I* , даже если
U * ¹ Æ, L * ¹ Æ.
Пример 2. Пусть
I ( u ) = e - u ,U 0 = R1 , m = 0, s = 1, g1 ( u ) = g ( u ) = ue - u
Тогда
и
U = { u Î U 0 g ( u ) = 0} = { 0} Þ U * = { 0} , I * = I ( 0 ) = 1,
L 0 = ( -¥, +¥ ) .

11.

Выпишем функцию Лагранжа для данной задачи
I ( u ) = e - u , g ( u ) = ue - u
L ( u , l ) = e - u + l ue - u = e - u ( 1 + l u ) .
Вычисляем
y ( l ) = inf1 L ( u, l ) =
uÎR
ì 0,
ï
í -¥,
ï -1+ l1
îl e ,
l = 0;
l > 0;
( 8)
l <0
Пояснения требует третья строчка в равенстве (8). Приведем график функции
L ( u, l )
1.5
1
1
2
-0.5
-1
-1.5
l = -5.
u* ( l ) Î R1
при
0.5
-1
l = const < 0
u* ( l )
3
4
5
= e-u ( 1 - lu )
l = const < 0
Найдем минимизирующую точку
для
l < 0.
Имеем
¶L ( u , l )
= -e - u - l ue -u + l e -u = 0 Þ
¶u
-1 - l u + l = 0 Þ
l -1
u* ( l ) =
.
l

12.

Таким образом, для
l<0
имеем
y ( l ) = L ( u* ( l ) , l )
=e
-
l -1
l
и соотношение (8) доказано.
l -1
u* ( l ) =
.
l
=e
- u* ( l )
( 1- u ( l ) ×l )
*
l -1
u* ( l ) =
l
l -1 ö
-1+ l1
æ
ç1 + l ×
÷= le
l ø
è
Отсюда
æì
0,
çï
*
y = supy ( l ) = sup ç í -¥,
lÎR1 ç ï
lÎR1
ç l e -1+ l1 < 0,
èî
l = 0;
l > 0;
l<0
ö
÷
÷ = y ( 0) = 0 Þ
÷÷
ø
y * = 0, L * = { 0} ¹ Æ,
Таким образом,
L = { 0} ¹ Æ, U * = { 0} ¹ Æ,
*
но
y * = 0 < 1 = I* .
=

13.

Двойственная задача всегда является задачей выпуклого программирования
независимо
от того, какой была основная (исходная) задача. Действительно, двойственная задача
y ( l ) ® sup, l Î L 0
эквивалентна задаче
0
yˆ ( l ) ® inf, l Î L 0 , yˆ ( l ) = -y ( l ) , l Î L .
0
Достаточно установить выпуклость функции yˆ на множестве L . Имеем
0
sup
é
L
u
,
l
ù
,
l
Î
L
.
)û
yˆ ( l ) = -y (l ) = - inf L ( u, l ) =
ë (
Для всех
uÎU 0
0
(
l ( 1) , l ( 2) Î L , a Î [ 0,1]
( 9)
uÎU 0
справедливо
(
)
)
sup é - L u , al ( 1) + ( 1 - a ) l ( 2) ù =
û
uÎU 0 ë
s
é
ù
( 1)
( 2)
= sup ê - ( a + ( 1 - a ) ) I ( u ) - å ali + ( 1 - a ) li gi ( u ) ú =
uÎU 0 ë
i =1
û
s
s
é
ù
( 1)
( 2)
= sup ê -a I ( u ) - ( 1 - a ) I ( u ) - a å li g i ( u ) - ( 1 - a ) å li g i ( u ) ú =
uÎU 0 ë
i =1
i =1
û
yˆ al ( 1) + ( 1 - a ) l ( 2) =
(
)

14.

s
s
é
ù
1
= sup ê -a I ( u ) - ( 1 - a ) I ( u ) - a å li( ) gi ( u ) - ( 1 - a ) å li( 2) gi ( u ) ú =
uÎU 0 ë
i =1
i =1
û
s
s
ì é
ù
é
ùü
1
( )
( 2)
= sup í-a ê I ( u ) + å li gi ( u ) ú - ( 1 - a ) ê I ( u ) + å li g i ( u ) ú ý =
uÎU 0 î
i =1
i =1
ë
û
ë
ûþ
= sup é -a L u , l ( 1) - ( 1 - a ) L u , l ( 2) ù £
û
uÎU 0 ë
( 1) ù
( 2) ù
é
é
£ sup -a L u, l
+ sup - ( 1 - a ) L u, l
=
ë
û
ë
û
uÎU 0
uÎU 0
(
)
(
(
( )
6 4 47 4 48
(
)
)
yˆ l ( 1)
( 9)
(
1)
)
( )
yˆ l ( 2)
6447448
ù + ( 1 - a ) sup é - L u, l ( 2) ù =
û
û
uÎU 0 ë
(
= ayˆ ( l ( ) ) + ( 1 - a ) yˆ ( l ( ) ) .
= a sup é - L u, l (
uÎU 0 ë
)
1
)
2
Выпуклость функции yˆ на множестве L доказана, т.е. двойственная задача
является задачей выпуклого программирования. Благодаря этому обстоятельству в задачах
математического программирования, регулярная функция Лагранжа которых имеет
0
седловую точку, удобнее сначала исследовать двойственную к ней задачу.

15.

Двойственная задача к двойственной не обязана совпадать с исходной задачей.
Например, если исходная задача не является задачей выпуклого программирования.