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

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

ЛЕКЦИЯ 3
1. ПРОСРАНСТВО ПОДМНОЖЕСТВ
(ПРОДОЛЖЕНИЕ)
R
n

2.

1. ПРОСРАНСТВО ПОДМНОЖЕСТВ
Rn .
(ПРОДОЛЖЕНИЕ)
1.3. Алгебраические линейные комбинации подмножеств
(продолжение)
1.4. Расстояние Хаусдорфа.
n
R .

3.

1.3. Алгебраические линейные комбинации подмножеств
A1 ,L , Am Ì R n компактны. Тогда их любая
m
m
ì
ü
A = å li Ai = íа = å li ai ai Î Ai , i = 1,L , m ý
i =1
i =1
î
þ
Пусть множества
Теорема 3.
алгебраическая комбинация
является компактным множеством.
Доказательство. Докажем ограниченность множества
место включения
A1 , , Am Ì R
a =
ÎAi
ål a
i =1
i
Ai Ì O ( 0, Ai ) , i = 1,L , m.
n
i
A. Действительно, имеют
Из компактности множеств
max u
uÎAi
следует их ограниченность и конечность величин
aÎ A
Тогда для всех
m
(продолжение)
m
справедливо неравенство
£ å li
i =1
Ai , i = 1,L , m.
£ max u = Ai
uÎAi
ai
m
å
£
i =1
æ m
ö
li × Ai Þ A Ì O ç 0, å li × Ai ÷
è i =1
ø
m
A = å li Ai .
что и означает ограниченность множества
Докажем замкнутость
i =1
множества
x.
A.
Пусть последовательность
Надо доказать, что
x Î A.
{x },x
j
j
Î A, j = 1, 2,L
сходится к
Действительно, справедливо представление

4.

ÎAi
}
x j = å li aij , aij Î Ai , i = 1,L , m, j = 1, 2,L , .
i =1
x1 , x2 , L
xj, L ® x
m
m
L
L
m
L
å li ai1 = å li ai 2 = L =å li aij = LL
m
i =1
i =1
= l1a12 +
+ l2 a22 +
+L +
+ lm am 2
= l1a11 +
+ l2 a21 +
+L +
+ lm am1
L
L
L
L
L
L
i =1
l1a1 j +
+ l2 a2 j +
+L +
+ lm amj
L
L
L
L
L
L
Î A1
Î A2
L
Î Am
Ai для всех i = 1,L , m
i = 1,L , m.
Действительно,
Из компактности множеств
{a } ®a
ij
i0
Î Ai ,
a11 , a12 , L
Î A1
Î A1
a1k ( 1) , a1k ( 1) , L
1
2
Î A1
Î A1
a1 j , L Î A1 ,
Î A1
a1k ( 1) , L ® a10 Î A1 ,
j
Î A1
a2 k ( 1) , a2 k ( 1) , L , a2 k ( 1)
1
ÎA2
j
2
ÎA2
a2 k ( 2) , a2 k ( 2) , L
1
Î A2
2
Î A2
можно считать, что
ÎA2
L Î A2
a2 k ( 2) , L ® a20 Î A2 ,
j
Î A2

5.

L Î A3 ,
a3k ( 2) , a3k ( 2) , L , a3k ( 2)
1
j
2
Î A3
Î A3
Î A3
LL ® a Î A
amk ( m) ,L amLk ( m) , LL L amkL
,
( m)
m0
m
1
Î Am
Переобозначим
j
2
Î Am
( m)
k1
( m)
¸ 1, k 2
Î Am
( m)
¸ 2, L , k j
¸ j, L
æ =å li aij ö
предел берется по
переобозначеным номерам j ç i =1
m
}
} ÷
æ
ö
ç
÷
lim
l
a
x=
lim
xj =
å
i ij ÷ =
ç
j ®¥
j ®¥
ç
÷
è i =1
ø
ç
÷
è
ø
Тогда
m
}ÎAi
= å li ai 0 Î
m
i =1
И так. Доказано, что если
x-
она принадлежит этому множеству.
компактность. Теорема доказана.
ai 0
6
4
7
48
m
å li lim ( aij ) =
i =1
j ®¥
m
å l A = A.
i =1
i
i
m
A = å li Ai ,
i =1
Отсюда следует замкнутость множества A
предельная точка множества
то
и его

6.

m = 2.
Упражнение 1. Доказать теорему 3 при
A1 , A2 Ì R n
Теорема 3. Пусть множества
A = l1 A1 + l2 A2
алгебраическая комбинация
множеством.
Доказательство. Ограниченность. Для всех
ÎA1
£ max u = Ai
ÎA2
a = l1 a1 + l2 a2 £ l1
uÎA1
a1
A Ì O ( 0, l1 × A1 + l2 × A2 ) ,
Доказательство замкнутости.
Пусть последовательность
сходится к
xÎR .
представление
n
= l1a11 +
+ l2 a21 +
Тогда их любая
является компактным
aÎ A
справедливо неравенство
£ max u = A2
+ l2
uÎA2
a2
£
l1 × A1 + l2 × A2 Þ
что и доказывает ограниченность множества
{x },
j
Надо доказать, что
x1
компактны.
, x2 L
= l1a12 + L
+ l2 a22 L
L
A.
x j Î A, j = 1, 2,L
x Î A.
xj
= l1a1 j +
+ l2 a2 j
Действительно, справедливо
L ®x
L
L
L
Î A1
Î A2

7.

Из последовательности
a11 , a12 ,L , a1 j ,L Î A1
в силу компактности множества
A1
можно выделить подпоследовательность
a1k ( 1) , a1k ( 1) ,L , a1k ( 1) ,L ® a10 Î A1.
1
a2 k ( 1) , a2 k ( 1) ,L , a2 k ( 1) ,L Î A2
Из последовательности
A2
j
2
1
2
можно выделить подпоследовательность
в силу компактности множества
j
a2 k ( 2) , a2 k ( 2) ,L , a2 k ( 2) ,L ® a20 Î A2 .
Переобозначим
( 2)
k1
1
2
( 2)
¸ 1, k 2
1
2
¸ 2, L , k j ¸ j , L
Тогда
предел берется по
переобозначеным номерам j
x = lim ( x j ) =
j ®¥
6 44 7 4 48
æ l1a1 j}+ l2 a2 j ö
lim ç x j ÷
j ®¥ ç
÷
è
ø
Î A1
=
lim ( l1a1 j + l2 a2 j ) =
j ®¥
ÎA2
= l1 lim ( a1 j ) + l2 lim ( a2 j ) = l1 a10 + l2 a20 Î
j ®¥
j ®¥
l1 A1 + l2 A2 = A.

8.

И так. Доказано, что если x - предельная точка множества A = l1 A1 + l2 A2 , то
она принадлежит этому множеству. Отсюда следует замкнутость множества A и его
компактность.
Теорема доказана.
Непосредственно проверяется, что для любых чисел
U ,V Ì R n
,
и любых множеств
выполняются следующие свойства.
1)
2)
3)
( U ) = ( ) U ;
1×U = U ;
( U + V ) = U + V .
Эти свойства являются следствием соответствующих свойств векторов из пространства
Rn .
Однако пространство подмножеств
Rn
нельзя считать линейным пространством,
хотя бы потому, что не всегда выполняется равенство
Пример 3.
( + ) × U = U + U .
( 2)
Пусть U = O ( 0,1) , = 1, = -1.
U = 1× O ( 0,1) = O ( 0,1) ,
Тогда с одной стороны

9.

U = ( -1) × O ( 0,1)
Теорема 2
= O ( 0, -1 ×1) = O ( 0,1) Þ
U + U = O ( 0,1) + O ( 0,1)
Теорема 1
=
O ( 0, 2 ) ,
а с другой
æ 1 -1 ö
ç + ÷ × U = ( 1 - 1) × O ( 0,1) = { 0} ¹ O ( 0, 2 ) .
è
ø
(
)
Вместо равенства (2) + × U = U
справедливо лишь одностороннее вложение
+ U
( 2)
в общем случае
( + ) × U Ì U + U .
u Î ( + ) ×U .
Действительно, пусть
что
u = ( + ) u( ) .
0
Тогда существует
u ( 0) Î U
такой,
Отсюда следует
u = ( + ) u
( 0)
= u
( 0)
+ u
( 0)
Î U + U .

10.

1.4. Расстояние Хаусдорфа. Пусть U , V
Определение 17.
Ì Rn
- компактные множества.
{
Величина
e
e
min
e
³
0
U
É
V
,
V
ÉU
r ( U ,V ) =
называется расстоянием Хаусдорфа между множествами
Обозначим
e1
Тогда
e2
V.
}
e1 = min e ³ 0 U e É V ,
r ( U , V ) = max { e1 , e 2 } .
Покажем, что введенное понятие действительно является
расстоянием,
т.е. что для любых множеств
справедливо
1)
3)
и
e 2 = min { e ³ 0 V e É U } .
U
V
{
U
}
r ( U ,V ) ³ 0;
r ( U ,V ) = r ( V ,U ) ;
2) r
4)
U ,V ,W Ì R n
( U ,V ) = 0 Û U = V ;
r (U , W ) £ r (U , V ) + r (V , W )
Подробного доказательства требует лишь пункт 4). Приведем его. Пусть
= r ( U ,V ) ,
= r ( V ,W ) .

11.

Тогда
r ( V , W ) = Þ V Ì W + O ( 0, ) ,
r ( U ,V ) = Þ U Ì
ÌW + O ( 0, )
U Ì W + O ( 0, ) + O ( 0, )
V + O ( 0, ) Þ
= W + O ( 0, + ) Þ
U Ì W + O ( 0, + ) ,
( 3)
r ( U ,V ) = Þ V Ì U + O ( 0, ) ,
r ( V ,W ) = Þ W Ì
W Ì U + O ( 0, ) + O ( 0, )
ÌU + O ( 0, )
V
+ O ( 0, ) Þ
= U + O ( 0, + ) Þ
W Ì U + O ( 0, + ) .
Из (3) и (4) выводим
r ( U ,W ) £ + = r ( U ,V ) + r ( V ,W ) ,
что и доказывает требуемое свойство.
( 4)

12.

x2
Упражнение 2. Найти расстояние Хаусдорфа
между множествами
ìïæ x1 ö
üï
U = íç ÷ x1 = 0, x2 Î [ -1,1] ý ,
ïîè x2 ø
ïþ
и
1
æ -1 ö
ç ÷
è0ø
ìæ -1ö æ 1 ö ü
V = íç ÷ , ç ÷ ý
îè 0 ø è 0 ø þ
U
e1 =
= min { e ³ 0 U Ì V + O ( 0, e ) } =
= 2,
= min { e ³ 0 V Ì U + O ( 0, e ) } =
= 1,
x2
1
1
1
-1
x1
x1
-1
e2 =
x2
-1
1
-1
Решение.
æ1ö
ç ÷
è0ø
1
-1
-1
x1

13.

Таким образом,
r ( U ,V ) = max { R1 , R2 } = max
{
}
2,1 = 2.
Упражнение 3. Найти расстояние Хаусдорфа между шарами
{
}
{
O ( u1 , ) = u Î R n u - u1 £ , O ( u2 , ) = u Î R n u - u2 £
Решение.
e1 = min { e ³ 0 O ( u2 , ) Ì O ( u1 , ) + O ( 0, e ) } =
= min { e ³ 0 O ( u2 , ) Ì O ( u1 , + e ) }
+ u2 - u1 + = + e1 Þ
e1 = + u2 - u1
Аналогично
e1
u1
u2
u2 - u1
}

14.

e 2 = min { e ³ 0 O ( u1 , ) Ì O ( u2 , ) + O ( 0, e ) } =
= min { e ³ 0 O ( u1 , ) Ì O ( u2 , + e ) } = + u2 - u1
r ( O ( u1 , ) , O ( u2 , ) ) = max { R1 , R2 } =
= max { + u2 - u1 , + u2 - u1 } = max { , } + u2 - u1 .
Упражнение 4. Дан треугольникDOBC координатами своих вершин
O ( 0, 0 ) , B ( 1,1) , C ( 3, 0 ) . Найти расстояние Хаусдорфа между этим треугольником и
y
точкой
D,
являющейся пересечением высоты,
опущенной из вершины
с этой стороной.
Уравнение стороны
O
на сторону
BC
D ( xD , y D )
B ( 1,1)
Решение.
BC : y - 1 =
1- 0
( x - 1) Þ
1- 3
O ( 0, 0 )
1
1
1
3
( x - 1) Þ y = - x + Þ kBC = - Þ k BD = 2.
2
2
2
2
Уравнение высоты BD : y - 0 = 2 ( x - 0 ) Þ y = 2 x
y -1 = -
C ( 3, 0 )
x

15.

Координаты точки
D:
1
3
ì
y
=
x
+
,
ï
2
2 Þ
í
ïî y = 2 x
1
3
2x = - x + Þ
2
2
y
6
3
y
=
.
xD = Þ D
5
5
r ( DOBC , { D} )
2
5
3
x= Þ
2
2
D ( xD , y D )
B ( 1,1)
2
6× 5
æ3 ö æ6
ö
= DC = ç - 3 ÷ + ç - 0 ÷ =
5
è5 ø è5
ø
O ( 0, 0 )
C ( 3, 0 )
x