Выпуклый анализ. Выпуклые множества. Лекция 4

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

ЛЕКЦИЯ 4
2. ВЫПУКЛЫЕ МНОЖЕСТВА

2.

2. ВЫПУКЛЫЕ МНОЖЕСТВА
2.1. Определение выпуклого множества. Примеры.

3.

2. ВЫПУКЛЫЕ МНОЖЕСТВА
2.1. Определение выпуклого множества. Примеры.
Геометрический смысл
выпуклости множества состоит в том, что выпуклое множество вместе с любыми двумя
точками содержит и отрезок, их соединяющий. Например, левое множество на
рисунке выпукло, а правое нет.
u2
u2
u1
u1
называется выпуклым, если для всех
a u1 + (1 - a )u2 Î U .
Дадим
формальное определение выпуклого множества.
Определение 1. Множество
u1 , u 2 ÎU , a Î 0,1
U Rn
справедливо включение
Пустое и одноточечное множества принимаются
выпуклыми по определению.
Приведем примеры выпуклых множеств.
Пример 1. Замкнутая (открытая) окрестность точки
u0 Î R n радиуса R
множество

4.

{
}
O ( u0 , R ) = u Î R n u - u 0 £ R , u 0 Î R n , R ³ 0
( O ( u , R) = { u Î R
}
u - u0 < R , u0 Î R , R ³ 0
n
0
является выпуклым множеством.
u1 , u 2 Î O ( u 0 , R )
n
a Î [0,1]
Действительно для всех
справедливо
a u0 + (1-a ) u0
a u1 + (1 - a )u2 -
}
u0
=
= a u1 + (1 - a )u2 - a u0 - (1 - a )u0 =
= a ( u1 - u0 ) + ( 1 - a )( u2 - u0 ) £
£R
64 7
4
8
£ a u1 - u0 +
£R
64 7
4
8
( 1 - a ) u 2 - u0 £
)
и

5.

£R
£R
64 7
4
8
64 7
4
8
£ a u1 - u0 + ( 1 - a ) u2 - u0 £
£ a R + ( 1 - a ) R = R Þ a u1 + (1 - a )u2 Î O ( u0 , R ) .
Доказательство для открытой окрестности аналогично.
Пример 2.
{
Множество точек
( c, g ) = u Î R n c, u = g
, c Î R n , c ¹ 0, g Î R1 ,
называемое гиперплоскостью в
Действительно, для всех
и
u1 , u 2 Î ( c , g )
}
R n , выпукло.
a Î 0,1
справедливо
c, a u1 + (1 - a )u2 =
c
( c, g )
}=g
}=g
a c, u1 + ( 1 - a ) c, u2 =
= ag + ( 1 - a ) g = g Þ a u1 + (1 - a )u2 Î ( c, g ) .

6.

Гиперплоскости
{
( c, g )
поставим в соответствие множества
}
+ ( c, g ) = u Î R n c, u ³ g ,
{
c, u ³ g
- ( c, g ) = u Î R n c , u £ g
}
c
( c, g )
которые называются замкнутыми
полупространствами, и множества
{
}
c, u £ g
{
+ ( c, g ) = u Î R n c , u > g , - ( c, g ) = u Î R n c, u < g
}
которые называются открытыми полупространствами.
Пример 3. Множества
+ ( c, g ) , - ( c, g ) , + ( c, g ) , - ( c, g )
Доказательство этого утверждения
выпуклости множества
( c, g )
выпуклы.
проводится аналогично доказательству
в предыдущем примере.

7.

v, d Î R n , d ¹ 0
Векторам
поставим в соответствие множества
{
M 1+ u
}
M 1 = u = v + td t Î ( -¥, +¥ ) ,
{
M 1+ = u = v + td t Î 0, +¥ )
d
v
}
M1
O
которые будем называть, соответственно, прямой и лучом
проходящими через точку
v
Пример 4. Множества
a Î [0,1]
и
в направлении вектора
M 1 , M 1+
d.
выпуклы. Действительно, для всех
u1 = v + t1d , u2 = v + t2 d ,
t1 , t2 Î R1
(
справедливо
t1 , t2 ³ 0 )
wa = a u1 + (1 - a )u2 = a ( v + t1d ) + (1 - a ) ( v + t2 d ) =
ta Î( -¥ , +¥ )
6 44 7 4 48 6 4 4 7 4 48
= a v + (1 - a )v + éëa t1 + ( 1 - a ) t2 ùû d = v + ta d .
v

8.

ta Î R1 ( ta = a t1 + ( 1 - a ) t2 ³ 0 )
В силу
включение
wa Î M 1
(w
a
отсюда следует требуемое
ÎM
+
1
).
Теорема 1. Пересечение любого числа выпуклых множеств является выпуклым
множеством.
Доказательство. Пусть
U b , b Î B,
выпуклые в
Rn
множество произвольной мощности, Покажем, что множество
v1 , v2 Î U .
что каждое из множеств
Тогда
v1 , v2 Î U b
Ub , b Î B
I
vl ÎU b
vl Î I U b = U
b ÎB
Теорема доказана.
для всех
b Î B.
Ub
B-
является
В силу того,
является выпуклым, имеет место включение
vl = l v1 + ( 1 - l ) v2 Î U b ,
Отсюда
U=
b ÎB
выпуклым.
Пусть
множества, где
"l Î 0,1 , b Î B.
и множество
U
является выпуклым.

9.

Из теоремы 1, в частности, следует, что множество
{
U = u Î R n Au £ b; Au = b ; u k ³ 0, k Î K { 1,L , n}
}
( 1)
являющееся областью допустимых значений оптимизирующих параметров в общей
задаче линейного программирования, выпукло.
Справедливость этого утверждения
вытекает из того обстоятельства, что формула (1) определяет множество
пересечение гиперплоскостей и полупространств в
Rn .
выпуклых множеств не обязательно выпукло.
A
B
U как
Заметим, что объединение

10.

Упражнение 1.
Доказать выпуклость эллипса
üï
ì
ü ìï
x2 y 2
2 2
2 2
U = í( x, y ) 2 + 2 £ 1ý = í( x, y ) a1 x + b1 y £ 1ý
a
b
î
þ ïî
ïþ
= 12
a
Решение.
Пусть
æ x1 ö æ x2 ö
ç ÷ , ç ÷ Î U , a Î 0,1 .
è y1 ø è y2 ø
y
= 12
b
x
0
b
a
Надо доказать, что
æ a x1 + ( 1 - a ) x2 ö
æ xa ö
æ x1 ö
÷ ÎU ,
ç ÷ = a ç ÷ + ( 1-a ) ç
è y1 ø
è ya ø
è a y1 + ( 1 - a ) y2 ø
т. е., что
a éëa x1 + ( 1 - a ) x2 ùû + b éëa y1 + ( 1 - a ) y2 ùû £ 1.
2
2
1
Справедливо неравенство
2
1
2
£ x12 + x22
}
2
éëa x1 + ( 1 - a ) x2 ùû = a 2 x12 + a ( 1 - a ) 2 x1 x2 + ( 1 - a ) x22 £
2

11.

£ x12 + x22
}
2
a x + a ( 1 - a ) 2 x1 x2 + ( 1 - a ) x22 £ a 2 x12 + ( 1 - a ) éa x12 + x22 + ( 1 - a ) x22 ù =
2
2
1
ë
(
)
û
= a 2 x12 + ( 1 - a ) ( a x12 + a x22 + x22 - a x22 ) = = a 2 x12 + ( 1 - a ) ( a x12 + x22 ) =
= a 2 x12 + a x12 + x22 - a 2 x12 - a x22 = a x12 - a x22 + x22 = a x12 + ( 1 - a ) x22 Þ
éëa x1 + ( 1 - a ) x2 ùû £ a x12 + ( 1 - a ) x22
2
Аналогично
éëa y1 + ( 1 - a ) y2 ùû £ a y12 + ( 1 - a ) y22 .
2
Тогда
£a x12 + ( 1-a ) x22
£a y12 + ( 1-a ) y22
6 4 44 7 4 4 48
6 4 44 7 4 4 48
2
2
2
2
a1 éëa x1 + ( 1 - a ) x2 ùû + b1 éëa y1 + ( 1 - a ) y2 ùû £
£ a12 éëa x12 + ( 1 - a ) x22 ùû + b12 éëa y12 + ( 1 - a ) y22 ùû =
£1
£1
£ a ( a12 x12 + b12 y12 ) + ( 1 - a ) ( a12 x22 + b12 y22 ) £ a + ( 1 - a ) = 1.

12.

Упражнение 2. Рассмотрим задачу математического программирования
I ( u ) ® min, u Î U R n ,
g1 ( u ) £ 0,L , g m ( u ) £ 0,
U-
выпуклое множество.
g m +1 ( u ) = 0,L , g s ( u ) = 0,
Пусть
u* -
ее решение. Полагаем
{
Доказать выпуклость множества
ìæ
ö
a0
ïç
÷
i
ïç { a , i Î B* ÷
ïç
÷ Î R1+ k + s - m
m +1
A=í
ç a
÷
ïç
÷
L
ïç
÷÷
s
ïçè
a
ø
î
где
k £ m-
}
B* = i Î { 1,L , m} g i ( u* ) = 0 .
число элементов в множестве
ü
$u Î U :
ï
a 0 = I ' ( u* ) , u - u* ; ïï
ý,
i
a = gi ' ( u* ) , u - u* , ï
i Î B* U{ m + 1,L , s} ïï
þ
B* .

13.

Рассмотреть случай
m = 2, s = 3.
I ( u ) ® min, u Î U R n ,
Тогда
g1 ( u ) £ 0, g 2 ( u ) £ 0, g 3 ( u ) = 0,
U R n - выпуклое множество.
g1 ( u* ) = 0, g 2 ( u* ) < 0, g3 ( u* ) = 0.
Пусть
u* -
Тогда
B* = i Î { 1, 2} g1 ( u* ) = 0 = { 1} ,
ее решение и
{
ì
ïæ a 0 ö
ïç 1 ÷
3
A = íç a ÷ Î R
ïç a 3 ÷
ïè ø
î
}
$u Î U :
{ m + 1,L , s} = { 3}
ü
ï
0
a = I ' ( u* ) , u - u* ; ï
ý,
1
a = g1 ' ( u* ) , u - u* , ï
3
ï
a = g3 ' ( u* ) , u - u* þ

14.

Решение.
Пусть
æ a 0j ö
ç 1÷
a j = ç a j ÷ Î A, j = 1, 2
ç a 3j ÷
è ø
и
a Î 0, 1 .
æ a10 ö
æ a20 ö
æ aa0 ö
ç 1÷
ç 1÷
ç 1÷
aa = ç aa ÷ = a ç a1 ÷ + ( 1 - a ) ç a2 ÷ =
ç a13 ÷
ç a23 ÷
ç aa3 ÷
è ø
è ø
è ø
В силу определения множества
ì
ïæ a 0 ö
ïç 1 ÷
A = íç a ÷ Î R 3
ïç a 3 ÷
ïè ø
î
Требуется показать, что точка
æ a a10 + ( 1 - a ) a20 ö
ç 1
1 ÷
ç a a1 + ( 1 - a ) a2 ÷ Î A.
ç a a13 + ( 1 - a ) a23 ÷
è
ø
A
$u Î U :
ü
ï
0
a = I ' ( u* ) , u - u* ; ï
ý,
1
a = g1 ' ( u* ) , u - u* , ï
a 3 = g3 ' ( u* ) , u - u* ïþ
для этого требуется подобрать такое
ua Î U ,
равенства
чтобы выполнялись

15.

Из включений
u j Î U , j = 1, 2
aa0 = a a10 + ( 1 - a ) a20 = I ' ( u* ) , ua - u* ,
( 1)
aa1 = a a11 + ( 1 - a ) a12 = g1 ' ( u* ) , ua - u* ,
( 2)
aa3 = a a31 + ( 1 - a ) a31 = g3 ' ( u* ) , ua - u* ,
( 3)
æ a10 ö
æ a20 ö
ç 1÷
ç 1÷
a1 = ç a1 ÷ Î A, a2 = ç a2 ÷ Î A
ç a13 ÷
ç a23 ÷
è ø
è ø
следует существование точек
таких, что
a10 = I ' ( u* ) , u1 - u* ,
a11 = g1 ' ( u* ) , u1 - u* ,
a13 = g3 ' ( u* ) , u1 - u* ,
( 4)
( 5)
( 6)
a20 = I ' ( u* ) , u2 - u* ,
a12 = g1 ' ( u* ) , u2 - u* ,
a23 = g3 ' ( u* ) , u2 - u* ,

16.

В силу выпуклости множества
U
справедливо включение
ua = a u1 + ( 1 - a ) u2 Î U .
Эта точка является именно той, существование которой требуется для установления
включения
aa = a a10 + ( 1 - a ) a20 Î A.
0
0
0
a
=
a
a
+
1
a
a
(
)
1
2 = I ' ( u* ) , ua - u* ,
Действительно, докажем равенства (1)-(3)) a
aa1 = a a11 + ( 1 - a ) a12 = g1 ' ( u* ) , ua - u* ,
aa3 = a a13 + ( 1 - a ) a23 = g3 ' ( u* ) , ua - u* .
( 1)
( 2)
( 3)
Имеем
I ' ( u* ) ,
a u1 + ( 1-a ) u2
ua
- u* =
I ' ( u* ) , a u1 + ( 1 - a ) u2 -
a u* + ( 1-a ) u*
}
u*
= I ' ( u* ) , a u1 + ( 1 - a ) u2 - a u* - ( 1 - a ) u* =
= I ' ( u* ) , a u1 - a u* + I ' ( u* ) , ( 1 - a ) u2 - ( 1 - a ) u* =
=

17.

= I ' ( u* ) , a u1 - a u* + I ' ( u* ) , ( 1 - a ) u2 - ( 1 - a ) u* =
a10 = I '( u* ) , u1 - u*
( 4)
a20 = I '( u* ) , u2 -u*
( 4)
6 4 4 7 4 48
6 4 4 7 4 48
= a I ' ( u* ) , u1 - u* + ( 1 - a ) I ' ( u* ) , u2 - u* =
= a a10 + ( 1 - a ) a20 = aa0 (= I ' ( u* ) , ua - u* ).
Равенство (1)
aa0 = I ' ( u* ) , ua - u*
доказано.
1
1
1
a
=
a
a
+
1
a
a
(
)
Установим справедливость (2)
a
1
2 = g1 ' ( u* ) , ua - u* ,
( 2)
Имеем
g1 ' ( u* ) ,
a u1 + ( 1-a ) u2
ua
g1 ' ( u* ) , a u1 + ( 1 - a ) u2 -
- u* =
-a u* -( 1-a ) u*
= g1 ' ( u* ) , a u1 + ( 1 - a ) u2 - a u* - ( 1 - a ) u* =
a11 = g1 '( u* ) , u1 -u*
( 5)
a12 = g1 '( u* ) , u2 -u*
6 4 47 4 48
6 4 4 7 4 4 (8)
= a gi ' ( u* ) , u1 - u* + ( 1 - a ) gi ' ( u* ) , u2 - u* =
5
}
u*
=

18.

a11 = g1 '( u* ) , u1 -u*
( 5)
a12 = g1 '( u* ) , u2 -u*
6 4 47 4 48
6 4 4 7 4 4 (8)
= a gi ' ( u* ) , u1 - u* + ( 1 - a ) gi ' ( u* ) , u2 - u* =
(
= a a11 + ( 1 - a ) a12 = aa1 = g1 ' ( u* ) , ua - u*
Равенство (2)
aa1 = g1 ' ( u* ) , ua - u*
справедливость равенства (3).
множество
A
выпукло.
( 2)
5
)Þ
доказано. Аналогично устанавливается
aa3 = g3 ' ( u* ) , ua - u* .
( 3)
Таким образом,