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

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

ЛЕКЦИЯ 25
8. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ
(ПРОДОЛЖЕНИЕ)

2.

8. ВЫПУКЛОЕ ПРОГРАММИРОВАНИЕ
(ПРОДОЛЖЕНИЕ)
8.4. Теорема Куна-Таккера . Ограничения типа неравенств.

3.

8.4. Теорема Куна-Таккера . Ограничения типа неравенств.
Теорема 3 (Куна-Таккера). Пусть в задаче 1 m = s , выполнено условие регулярности
U * ¹ Æ. Тогда для каждой точки u * U * необходимо существует вектор
* 0 такой, что пара u* , * образует седловую точку функции Лагранжа для
и
этой задачи.
Доказательство.
и
В пространстве
R m +1
рассмотрим два множества
ì
æ a0 ö
ï
ç 1÷
0
a
³ I (u ),
a
ï
ç
÷
A = ía =
$u U 0 : i
çL ÷
a ³ gi (u ), i = 1,L , m
ï
çç m ÷÷
ï
èa ø
î
ì æ b0 ö
ü
ï ç 1÷
ï
ï çb ÷ 0
ï
i
B = íb =
b < I * , b < 0, i = 1,L , m ý .
ç ÷
ï çL ÷
ï
ï çè b m ÷ø
ï
î
þ
ü
ï
ï
ý,
ï
ï
þ

4.

Покажем, что
u U 0 ,
A I B = Æ.
Действительно, пусть
a A.
Тогда найдется такое
что будут справедливы неравенства
a0 ³ I u ,
a1 ³ g1 u ,L , a m ³ g m u .
ì æ b0 ö
ü Если u U , то
ï ç 1÷
ï
ï çb ÷ 0
ï a 0 ³ I u ³ I* > b0 Þ
i
B = íb =
b < I * , b < 0, i = 1,L , m ý
çL ÷
ï ç ÷
ï
0
0
a
¹
b
Þ a Ï B.
ï çè b m ÷ø
ï
î
þ
i { 1,L , m} , что gi (u ) > 0.
i
i
i
i
a
¹
b
Þ a Ï B.
a
³
g
(
u
)
>
0
>
b
Þ
Тогда
i
Множества A и B выпуклы. Для множества B это очевидно. Докажем выпуклость
Если
u U 0 \ U ,
множества
A.
Пусть
то найдется такой номер
æ a0 ö
æ d0 ö
ç 1÷
ç 1÷
a ÷
d ÷
ç
ç
a=
A, d =
A.
çL ÷
çL ÷
çç m ÷÷
çç m ÷÷
èa ø
èd ø

5.

Тогда найдется
v U 0 ,
что
u U 0 ,
что
a 0 ³ I u , a1 ³ g1 u ,L , a m ³ g m u
и
d 0 ³ I v , d 1 ³ g1 v ,L , d m ³ g m v .
Для произвольного числа
0,1
положим
æ a0 ö
æ d 0 ö æ a0 + 1 - d 0 ö
ç 1÷
ç 1÷ ç
1
1 ÷
a ÷
d ÷ ç a + 1- d ÷
ç
ç
a =
+ 1-
=
,
÷
çL ÷
çL ÷ ç
L
÷
çç m ÷÷
çç m ÷÷ çç m
m÷
èa ø
è d ø è a + 1- d ø
}
u = u + 1 - v U 0 .
выпукло
Покажем, что точка
включение
u U 0
является именно той, существование которой доказывает
a A. Действительно, в силу выпуклости функций I , g 1 , , g m
справедливы неравенства
£ a0
£d 0
I u = I u + 1 - v £ I u + 1 - I (v) £

6.

£ a 0 + 1 - d 0 = a 0 Þ I u £ a 0 .
Аналогично
£ ai
£d i
gi u = gi u + 1 - v £ gi u + 1 - gi (v) £
i
g
u
£
a
i = 1,L , m.
£ a + 1- d = a Þ i
,
Таким образом, a A и выпуклость множества A доказана.
i
i
i
По теореме об отделимости выпуклых множеств
{
G с, g = w R
,
n +1
}
существует гиперплоскость
c, w = g , c ¹ 0 отделяющая множества A = A
c, a ³ g ³ c, b , "a A, "b B
иB
:
6 .
æ 0* ö
ç *÷
1 ÷
ç
¹ 0. (Именно этот вектор и будет тем, существование которого
Обозначим с =
çL ÷
çç * ÷÷ требуется доказать). Тогда неравенство (6) принимает вид
è m ø
m
m
* i
a
³
g
³
å
å ib
i =0
* i
i
i =0
"a A, "b B.

7.

Определим величину
g.
Заметим, что
u* U * ¹ Æ, U * Ì U 0
включения
y A,
Включение
y B
æ I* ö
ç ÷
0÷
ç
y=
A I B.
çL ÷
ç ÷
è0ø
является той, существование которой требуется для
т.к. имеет место
I u* = I* , gi u* £ 0, i = 1,L , m.
очевидно. Вычисляем
y A I B Þ y G c, g Þ
g = c, y = 0* I* .
0* I*
Перепишем неравенство (6)
m
Покажем, что пара
*
u
,
*
æ 0* ö
æ I* ö
ç *÷
ç ÷
0
с = ç 1 ÷, y = ç ÷
çL ÷
çL ÷
çç * ÷÷
ç ÷
è0ø
è m ø
}
c, a ³ g ³ c, b , "a A, "b B
0* a 0 + å i*a i ³ 0* I * ³
i =1
Действительно, точка
m
6
в виде
b + å i*bi , "a A, "b B.
* 0
0
i =1
7
æ ö
ç ÷
, где * = ç L ÷ , удовлетворяет условиям теоремы 1
ç m* ÷
è ø
*
1

8.

1) L u* , * £ L u , * , " u U 0 ;
2) i* gi (u* ) = 0, i = 1,L , m, и, следовательно, является седловой точкой функции
3) u* U .
Лагранжа.
Действительно, условие 3)
u* U * Ì U
очевидно выполнено.
Проверим выполнение условия 2). Для всех
æ I* ö
ç
÷
0
ç
÷
ç L ÷
z (i ) = ç £0 ÷
çg u ÷
ç i * ÷
ç L ÷
ç 0 ÷
è
ø
Из неравенства (7)
при
m
ì æ a0 ö
ï ç ÷
ïï ç a1 ÷
ía =ç ÷
ï çL ÷
ï ç m÷
îï è a ø
$u U 0 : ü
ï
0
a ³ I ( u ), ïï
ý
ai ³ gi ( u ), ï
i =1,L , m ïï
þ
A
i {1, , m}
I
положим
ì æ b0 ö
ü
ï ç ÷
ï
1
ïï ç b ÷ 0
ïï
i
b
=
b
£
I
,
b
£
0,
i
=
1,
L
,
m
í ç ÷
ý
*
ï çL ÷
ï
ï ç m÷
ï
ïî è b ø
ïþ
B
m
a + å a ³ I ³ b + å i*bi , "a A, "b B
a = b = z i
*
0
0
i =1
находим
*
i
i
*
0 *
* 0
0
i =1
7

9.

i* gi u*
64 7 48
i* gi u*
678
}
}
m
m
* 0
* i
*
* 0
0 a + å i a ³ 0 I * ³ 0 b + å i*bi Þ
I*
I*
i =1
i =1
I + gi u*
*
0 *
*
i
7
*
*
I
+
³ I ³ 0 *
i g i u* Þ
*
0 *
ìï i* gi u* ³ 0,
*
Þ
í *
i g i u* = 0, i = 1,L , m.
ïî i gi u* £ 0
æ I* ö
ç
÷
0
ç
÷
ç L ÷
z (i ) = ç £0 ÷
çg u ÷
ç i * ÷
ç L ÷
ç 0 ÷
è
ø
8
Условие 2) теоремы доказано.
Покажем, что
æ I * - 1ö
ç
÷
0
÷
b(0) = ç
ç L ÷
ç
÷
0
è
ø
i* ³ 0, i = 0,1,L , m.
Полагаем
ì
æ ö
æ I* ö ïï ç b1 ÷
ç ÷ ïíb =çç b ÷÷
ç 0 ÷ ïï çç Lm ÷÷
ç L ÷ ïî è b ø
B
, b (i ) = ç ÷
ç -1 ÷
çL ÷
çç ÷÷
è0ø
i = 1,L , m.
ì æ b0 ö
ü
ï ç ÷
ï
ïï ç b1 ÷ 0
ïï
i
íb = ç ÷ b £ I* , b £ 0, i =1,L , m ý
ï çL ÷
ï
ï ç m÷
ï
ïî è b ø
ïþ
0
ü
ï
ïï
b0 £ I* , bi £ 0, i =1,L , m ý
ï
ï
ïþ
B
,

10.

Подставляя эти вектора в правую часть (7), I ³ b +
находим
*
0 *
* 0
0
m
å b , 7
i =0
* i
i
последовательно
æ I* -1ö
ç
÷
ç 0 ÷
ç L ÷
çç
÷÷
è 0 ø
m
}
*
*
*
*
*
0
³
Þ
I
1
+
×
0
Þ
b 0 : 0 I * ³ 0 *
å i
0
0 ³ 0,
i =0
æ I* ö
ç ÷
ç0÷
çL ÷
ç ÷
ç -1÷
çL ÷
ç ÷
ç0÷
è ø
}
b i : 0* I * ³ 0* I * +
Неравенства
m
*
å × 0 - Þ 0 ³ - Þ i ³ 0, i = 1,L , m.
s =1
s ¹i
*
i
i* ³ 0, i = 0,1,L , m
Покажем, что
*
i
*
i
установлены.
0* > 0. Пусть u U точка, фигурирующая в условиях Слейтера.
$u U : g1 u < 0,L , g m (u ) < 0 Тогда

11.

æ I u ö
ç
÷ $u}=u
g
u
1 ÷
ç
a=
A. Для вектора a из левой части неравенства (7)
ç L ÷
I u
gi u
}
}
m
çç
÷÷
* 0
*
i
*
g
u
a
+
a
³
7 находим
m
è
ø
å i
0
0 I*
i =0
m
0* I u + å i* gi u ³ 0* I * .
9
i =1
От противного 0* = 0 из (9) выводим
m
*
å i gi u ³ 0.
æ} ö
ç 0* ÷
ç *÷
В силу с = ç 1 ÷ ¹ 0
çL ÷
çç * ÷÷
è m ø
0
10
i =1
æ 1* ö
$i: > 0
ç ÷
*
Из
доказанных
неравенств
L
¹
0.
i ³ 0, i = 1,L , m
ç ÷
ç m* ÷
è ø
*
i
следует

12.

и условий Слейтера
$u U : g1 u < 0,L , g m (u ) < 0
m ³ 0 ,$i: i > 0
*
i
i =1
m
å
Последнее неравенство противоречит (10).
выводим, что
<0
gi u < 0.
*
å i gi u ³ 0
10
Остается признать, что
i =1
> 0.
*
0
Поделим неравенство (7)
m
m
a + å a ³ I ³ b + å i*bi
*
0
0
i =1
* i
i
*
0 *
* 0
0
i =1
7
на
0* > 0.
æ 0* ö
ç *÷
1 ÷
ç
Новые компоненты вектора с =
будем обозначать прежними символами. Тогда
çL ÷
çç * ÷÷
è m ø
æ 1* ö
ç
÷
0* = 1 и * = ç L ÷ 0 . Неравенство (7) принимает вид
ç m* ÷
è
ø
m
m
a + å a ³ I * ³ b + å i*bi
0
i =1
* i
i
0
i =1
11

13.

Для завершения доказательства теоремы осталось установить справедливость условия 1).
1) L u* , * £ L u , * , " u U 0
u U 0 .
Пусть
Тогда
ì
æ a0 ö
ï
ç 1÷
0
a
³ I (u ),
a
ï
ç
÷
A = ía =
$u U 0 : i
çL ÷
a ³ gi (u ), i = 1,L , m
ï
çç m ÷÷
ï
èa ø
î
æ I (u ) ö
ç
÷
g
u
÷ A.
a(u ) = ç 1
ç L ÷
ç
÷
g
(
u
)
è m ø
Из левого неравенства в (11) a +
0
m
* i
å i a ³ I*
11
для этой точки имеем
i =1
(8)Þ= 0
64
7 48
m
I (u ) + å i* gi u ³ I * + i* gi u* Þ
i =1
6 4 44 7 4 4 48
L u* , *
m
L u , *
6447448
m
I u* + å gi (u* ) £ I (u ) + å i* gi (u ) Þ
i =1
*
i
i =1
L u* , * £ L u , * , " u U 0 .
Теорема доказана.
ü
ï
ï
ý
ï
ï
þ