Выпуклый анализ. Выпуклое программирование. Лекция 26

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

ЛЕКЦИЯ 26
9. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ

2.

8. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ
(ПРОДОЛЖЕНИЕ)
8.5. Теорема Куна - Таккера для многогранных множеств.
8.6. Теорема Куна – Таккера. Общий случай.

3.

8.5. Теорема Куна - Таккера для многогранных множеств. Теорема о
существовании седловой точки функции Лагранжа в случае, когда множество U R n
является многогранником и U верна без предположения о регулярности множества
U.
Теорема 4. Пусть в задаче 1 выпуклого программирования
U0 = Rn ,
i
ìï
g
u
=
a
,
u
b
£ 0,
i = 1,L , m;
(
)
i
i
n
U = íu Î R
i
g
u
=
a
,
u
b
= 0, i = m + 1,L , s
(
)
ïî
i
i
üï
ý,
ïþ
ai Î R ; b Î R ; i = 1,L , s и множество U . Тогда для
0
необходимо
существует
вектор
Î
каждой точки u ÎU
где
n
i
1
ì
ü
æ 1 ö
ï
ï
ç ÷
0
s
= í = ç L ÷ Î R i ³ 0, i = 1,L , m ý
ï
ï
ç ÷
è sø
î
þ
такой, что пара
( u , ) образует
седловую точку функции Лагранжа
для этой задачи.

4.

Доказательство. Возьмем
{
u Î U .
Полагаем
}
B = i Î { 1,L , m} ai , u = bi .
Построим конус
ìï
üï
ai , e £ 0,
i Î B ;
n
K = íe Î R , e 0
ý.
ai , e = 0, i Î { m + 1,L , s} ïþ
ïî
Покажем, что множество возможных направлений множества
$t0 > 0 : u + te Î U , "t Î [ 0, t0 ]
совпадает с конусом
U
в точке
u
K.
e Î R n , e 0 - возможное направление множества U в
точке u . Тогда существует число t0 > 0, что
Действительно, пусть
u = u + te Î U
при всех
ai , u + te - bi £ 0, i = 1,L , m;
ai , u + te - bi = 0, i = m + 1,L , s
t Î ( 0, t0 ] . Далее пусть
{ 1,L , m}
i Î B U{ m + 1,L , s} ai , u - bi = 0.
( 2)
( 1)

5.

Тогда
( 1) :
ai , u + te - bi £ 0
>0
ai , t e £ 0 ai , e £ 0,
i
(2) : ai , u - b = 0
(1) : ai , u + te - bi = 0
>0
ai , t e = 0 ai , e = 0.
i Î { m + 1,L , s}
i
(2) : ai , u - b = 0
i Î B
ìï
üï
ai , e £ 0,
i Î B ;
n
Таким образом, e Î K K = íe Î R , e 0
ý.
ai , e = 0, i Î { m + 1,L , s} þï
îï
Обратно, пусть e Î K . Покажем что $t0 > 0 : u + te Î U , "t Î [ 0, t0 ] т. е. что это
направление возможное.
Для индекса
{
i Î B = i Î { 1,L , m} ai , u = bi
³0 }
ai , u + te - bi = ai , u + t × ai , e - bi £
eÎK £ 0
}
и
t³0
имеем
6 4 7 48 ( 2)
ai , u - bi = 0
ai , u -bi = 0, i = B
ai , u + te - bi £ 0 "t ³ 0, i Î B .

6.

Для индекса
t0 > 0
{
i Î { 1,L , m} \ B = i Î { 1,L , m} ai , u < b i
}
при малых
iÎ{ 1,L , m} \ B < 0
имеет место неравенство
6 4 7 48
ai , u + te - bi = ai , u - bi + t ai , e £ 0 "t Î [ 0, t0 ] .
Наконец для индексов i Î { m + 1, , s} выполняется
ai , u -bi = 0, i ={ m +1,L , s} ( 2 )
6 4 7 48
eÎK = 0
i
ai , u + te - bi = ai , u + t ai , e - b =
ai , u - bi
= 0 "t.
ai , u + te - bi £ 0,
Таким образом, соотношения (1)
i = 1,L , m;
( 1)
установлены.
ai , u + te - b = 0, i = m + 1,L , s
Следовательно, направление e является возможным.
Для точки u ÎU по теорема 5.2 о минимуме дифференцируемой выпуклой функции,
i
определенной на выпуклом множестве, имеет место неравенство
I ' ( u ) , u - u ³ 0, "u Î U .
Для всех
eÎ K
справедливо включение
Тогда из (3) выводим
( 3)
u = u + te Î U , t Î ( 0, t0 ] , t0 > 0.
>0
I ' ( u ) , u + te - u = t I ' ( u ) , e ³ 0 I ' ( u ) , e ³ 0
- I ' ( u ) , e £ 0 "e Î K .

7.

В дальнейшем потребуется ссылка на теорему Фаркаша.
Пусть заданы матрицы
B ¸ m ´ n, B ¸ ( s - m ) ´ n , s ³ m
{
}
причем
X = x Î R n Bx £ 0, Bx = 0 .
Теорема 6 (Фаркаша). Для вектора
выполняется для всех
вектора
xÎ X
v Î Rn
неравенство
в том и только том случае,
v, x £ 0
если существуют
u Î R m , u ³ 0, u Î R s - m , такие что v = B ' u + B ' u .
Установим соответствие в обозначениях теоремы Фаркаша
и доказываемой теоремы
x « e;
æL L L L ö
ç iе-ограничен ие ÷
æ am +11 L
6
4
7
4
8
конус
ç
÷
ç
n
B
«
a
L
a
,
i
Î
B
,
X « K R ;
B «ç L
L
ç i1
in ÷
çL L L L ÷
ç as 1 L
è
ç
÷
v « - I ' ( u ) .
è
ø
- I '( u )
eÎK
v , xбыло
£ 0 установлено на предыдущем слайде
am +1n ö
÷
L ÷
as n ÷ø
!

8.

æ m +1 ö
ç
÷
u «ç L ÷
ç s ÷
è
ø
æ L ö
ç
÷
Из теоремы Фаркаша следует
u
«
³
0
ç i
÷ , i Î B
cсуществование векторов
ç L ÷
s
è
ø
таких, что
i ai
i ai
å
å
- I '( u )
iÎB
i = m+1
}
}
}
I
'
u
=
(
)
å i ai v = B 'u + B 'u
Доопределяем:
i = 0, i Î { 1,L , m} \ B .
m
I ' ( u ) = -å a i =1
Заметим, что
равенство умножим на
u - u
i = m +1
å
i = m +1
s
a = -å i ai .
i i
произвольного
( 5)
u ÎU 0 = R
скалярно
s
I ' ( u ) , u - u + å i ai , u - u = 0.
i =1
( 4)
i =1
678
g ( u ) = 0, i = 1,L , m.
I ' ( u ) + å a = 0.
å
i ai .
Тогда
s
= 0,
= 0,iÎB
iÎ{ 1,L , m} \ B
i
i
s
Для
i i
i =1
Из (4) следует
i i
iÎB
s
( 6)
n
последнее

9.

æ 1 ö
ç ÷
s
0
По
построению
=
L
Î
R
.
³
0,
i
Î
1,
L
,
m
Î
.
Полагаем
{
}
ç ÷
i
ç s ÷
è ø
Для всех
u ÎU 0 = R
n
имеем
s
å i ( ai , u -bi )
6 4 4 4 7i=1 4 4 48
L ( u, ) - L ( u , ) =
L( u , ) = I ( u ) +
s
s
i =1
i =1
= I ( u ) + å i ( ai , u - bi ) - I ( u ) - å i ( ai , u - bi ) =
I ( u ) - I ( u ) ³ I '( u ) , u -u , uÎU
первый критерий выпуклости
=
6 44 7 4 48
I ( u ) - I ( u )
s
+ å i ai , u - u ³
( 6)
i =1
6 4 4 4 4 4 44 7 4 4 4 4 4 4 48
s
³ I ' ( u ) , u - u + å i ai , u - u = 0
i =1
L ( u,
) - L( u , )
L
u
,
³
L
u
,
(
)
(
) , "u ÎU 0 ,
³0
( 7)

10.

æ 1 ö
ç ÷
Таким образом, для u Î U , = ç L ÷ Î 0 , выполнено
ç s ÷
è ø
i ³ 0, i Î { 1,L , m} , i gi ( u ) = 0, i = 1,L , m
L ( u , ) ³ L ( u , ) , "u Î U 0 .
Отсюда по теореме 1 заключаем,
что точка
(u , ) ÎU
( 5) ,
( 7)
0
´ 0
является
седловой для функции Лагранжа. Теорема доказана.
Из доказанной теоремы, в частности следует, что для функции Лагранжа в задаче
линейного программирования, имеющей конечное решение, всегда существует седловая
точка.
8.6. Теорема Куна – Таккера. Общий случай. Приведем без доказательства общий
вариант теоремы Куна-Таккера.
Теорема 5. Пусть в задаче выпуклого программирования
существует точка
регулярности).
u Î riU 0 U
множество U
и
такая, что g i ( u ) < 0, i = 1,L , m. (условие

11.

Тогда для каждой точки
u ÎU необходимо существует вектор множителей
Лагранжа такой, что пара
0
u
,
Î
U
´
( ) 0 ,
где
ì
ü
æ 1 ö
ï
ï
ç
÷
L
ï
ï
ç
÷
ïï
ïï
ç m ÷
0
s
Î = í = ç
÷ Î R i ³ 0, i = 1,L , m ý ,
ç m +1 ÷
ï
ï
ç L ÷
ï
ï
çç
÷÷
ï
ï
ïî
ïþ
è s ø
является седловой точкой для функции Лагранжа.