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

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

ЛЕКЦИЯ 18
6. ТЕОРЕМЫ ОБ ОТДЕЛИМОСТИ ВЫПУКЛЫХ
МНОЖЕСТВ (ПРОДОЛЖЕНИЕ)

2.

6. ТЕОРЕМЫ ОБ ОТДЕЛИМОСТИ ВЫПУКЛЫХ
МНОЖЕСТВ
6.4. Некоторые следствия из теорем об отделимости
выпуклых множеств.

3.

6.4. Некоторые следствия из теорем об отделимости выпуклых множеств. Всякое
выпуклое множество полностью определяется своими опорными полупространствами.
Именно, справедлива следующая теорема.
Теорема 5. Выпуклое компактное множество
U
P l
совпадает с пересечением всех своих опорных полупространств
(перебор производится по всем lÎS 0,1 ).
Доказательство.
Требуется доказать, что
U=
где P
UÌ
I
lÎS 0,1
P l ,
w
v l
l
U
v lˆ
lˆ
v
l - опорное полупространство в направлении вектора l Î S 0,1 . Вложение
I P l очевидно. Действительно, для всех u Î Uи l ÎS 0,1
lÎS 0,1
uÎU
ì
ü
n
из равенства (2.3) P l = íu Î R l , u ³ min l , v ý (2.3)
vÎU
î
þ
Пусть теперь нашлась точка
wÎ
I
lÎS 0,1
Тогда по теореме 2 найдется вектор lˆ Î S
P l
0,1 ,
такая, что
выводим u Î P l .
w ÏU = U .
удовлетворяющий условию

4.

Теорема 2
6 4 4 4 4 44
7 4 4 4 4 4 48
2
lˆ, u ³ lˆ, w + lˆ , " u ÎU Þ
v lˆ
lˆ, u > lˆ, w , " u Î U .
ˆ
В частности, при
опорное в направлении l множество
644
4 4 44 7 4 4 4 4 4 48
u = v lˆ Î V lˆ = v lˆ Î U l , v lˆ = min lˆ, v
{
отсюда следует
lˆ, v lˆ
> lˆ, w Û
lˆ, w < lˆ, v lˆ
}
vÎU
определение
v lˆ
=
min lˆ, v .
vÎU
Последнее неравенство противоречит включению
сделанное предположение
wÎ
I
lÎS 0,1
{
P l Ì P lˆ = u Î R n lˆ, u ³ min lˆ, v
vÎU
} Þ lˆ, w ³ min lˆ, v .
vÎU
Теорема доказана.
Теорема 6.
Пусть
U Ì Rn
- выпуклый компакт. Тогда
w Î U Û l , w £ cU l , "l Î S 0,1 . cU l = max u, l
uÎU
Необходимость очевидна.

5.

Проверим достаточность.
w, l £ cU l = max u , l = - min - u, l
= - min u, -l
uÎU
uÎU
uÎU
"l Î S 0,1 Þ
w, l £ - min u, -l "l Î S 0,1 .
uÎU
Умножим полученное неравенство на (-1). Тогда
w, -l ³ min u, -l "l Î S 0,1 .
uÎU
В последнем неравенстве заменим
-l
на
l.
w, l ³ min u, l "l Î S 0,1 .
uÎU
Последнее означает, что точка
множества
U
w
В результате получим
{
P l = u Î R n l , u ³ min v, l
vÎU
}
(2.3)
принадлежит всем опорным полупространствам
и, по теореме 5, самому множеству
U.
Теорема доказана.
Пусть U , V Ì R n - выпуклые компакты. Вложение
место тогда и только тогда, когда
Теорема 7.
cU l £ cV l , "l Î S 0,1 .
Необходимость очевидна. Проверим достаточность.
U ÌV
имеет
1
От противного приходим к

6.

существованию точки
u
u ÎU ,
для которой
uÎU
cU l £ cV l , "l Î S 0,1 .
A, B Ì R n ,
1
Теорема доказана.
A I B = Æ. Вывести формулу для
a
вычисления величины e 1 = min a B Ì A ¹ Æ .
Величина
e1
cU lˆ = max u, lˆ ³ u , lˆ > cV lˆ ,
Упражнение. Пусть
A
u , lˆ > cV lˆ .
Тогда справедлива следующая цепочка неравенств
U
что противоречит (1).
По теореме 6 найдется вектор
lˆ Î S 0,1 , что
lˆ
V
u ÏV .
B
e,
{
e1 -
}
Решение.
наименьшее из положительных чисел
удовлетворяющих неравенству
c B l £ c Ae l , "l Î S 0,1 Þ
64 7=e 48
c B l £ c A+O 0,e l = c A l + c O 0,e l Þ
c B l £ c A l + e Þ e ³ c B l - c A l "l Î S 0,1 .

7.

e ³ c B l - c A l "l Î S 0,1 Þ e1 = max éë c B l - c A l ùû .
l =1
Упражнение.
Проверить полученную формулу для множеств
ææ0ö ö
ææ 2ö ö
2
A = O ç ç ÷ ,1÷ Î R , B = O ç ç ÷ ,1÷ Î R 2
èè0ø ø
èè 2ø ø
Решение.
y
A
e1 = max éë c B l - c A l ùû =
l =1
B
e1
x
é
ù
êc æ 2 ö l - c æ 0 ö l ú =
= max
æ ö
l12 + l22 =1 ê O ç æç ö÷,1÷
O çç ç ÷,1÷÷
ú
ç 2 ÷
0
è
ø
è
ø
è
ø
è
ø
ë
û
é
ù
êc 2 æ 0 ö l - c æ 0 ö l ú =
= max
æ ö
2
2
l1 + l2 =1 ê æç ö÷ + O ç æç ö÷ ,1÷
O
ú
ç
ç 0 ÷
ç ç 0 ÷ ,1÷÷
2
èè ø ø
ë è ø èè ø ø
û
é
ù
ê c æ 2 ö l + c æ 0 ö l - c æ 0 ö l ú = max c æ 2 ö l =
= max
æ ö
æ ö
2
2
l1 + l2 =1 ê ç ÷
l12 +l22 =1 ç ÷
O çç ç ÷,1÷÷
O çç ç ÷,1÷÷
ú
è 2ø
èè0ø ø
èè0ø ø
ë è 2ø
û

8.

= max
cæ 2ö l =
2
2
y
l1 + l2 =1
e1
A
B
ç ÷
è 2ø
æ 2 ö æ l1 ö
max
,ç ÷ =
ç
÷
2
2
l1 + l2 =1
è 2 ø è l2 ø
2 2
= 2 max
[ l1 + l2 ] = 2 2.
2
2
x
l1 + l2 =1
Полученный результат полностью согласуется с рисунком.
Следствие 1. Пусть U , V Ì R n - выпуклые компакты. Равенство
место тогда и только тогда, когда
cU l = cV l , "l Î S 0,1 .
Доказательство. Вытекает из утверждения
U =V Û U ÌV
логическое
I
V ÌU .
U =V
имеет

9.

Следствие 2. Пусть U , V Ì R n - выпуклые компакты. Тогда
r U ,V = max cU l - cV l .
lÎS 0,1
2
Доказательство. По определению расстояния Хаусдорфа выводим
r U , V = max { e1 , e 2 } ,
где величины
e1 , e 2 определяются из условия
e1 = min { U e É V } = min { cU e l ³ cV l } =
e >0
e >0
= min { cU l + e ³ cV l } = min { e ³ cV l - cU l } , "l Î S 0,1
e >0
e >0
Þ
e1 = max { cV l - cU l } ,
lÎS 0,1
e 2 = min { V e É U } = min { cV e l ³ cU l } =
e >0
e >0
= min { cV l + e ³ cU l } = min { e ³ cU l - cV l } , "l Î S 0,1
e >0
e >0
e 2 = max { cU l - cV l } .
lÎS 0,1
Þ

10.

e1 = max { cV l - cU l } , e 2 = max { cU l - cV l } .
lÎS 0,1
Тогда
{
lÎS 0,1
}
r U , V = max { e1 , e 2 } = max max { cV l - cU l } , max { cU l - cV l } =
{
lÎS 0,1
lÎS 0,1
}
= max max éë cV l - cU l , cU l - cV l ùû = max cU l - cV l .
lÎS 0,1
lÎS 0,1
Теорема доказана.
Упражнение. Вычислить расстояние Хаусдорфа между множествами
y
O
x
ìï
ü
æö
ïï
x
2
2
2
ï
÷
ç
O ( 0,1) = í u = ç ÷
÷Î R x + y £ 1ý
ç
÷
ïï
ïï
èyø
î
þ
и
ìï
üï
æ xö
2
K 0,1 = íu = ç ÷ Î R x £ 1, y £ 1ý
è yø
ïþ
îï
Решение.
1
6
4
7
48
}
}
64 7 48 64 7 48
2
2
l
+
l
l
+
l
r K 0,1 , O 0,1 = max c K 0,1 l - c O 0,1 l = lmax
1
2
1
2 =
2
2
+ l =1
l1 + l2
lÎS 0,1
l12 + l22
cos a
1
2
sin a

11.

y
}
}
max
l1 + l2
2
2
cos a ³ 0
l1 + l2 =1
O
x
sin a ³ 0
64 71 48
- l12 + l22 =
6 4 4 7³0 4 48
max cos a + sin a - 1 =
é pù
a Îê0, ú
ë 2û
= max cos a + sin a - 1 =
é pù
a Îê0, ú
ë 2û
2 -1
Этот же результат может быть получен из анализа рисунка.
U ,V Ì R n не являются выпуклыми, то равенство (2)
r U ,V = max cU l - cV l 2 может не выполняться.
В случае, если множества
lÎS 0,1
Пример 1.
Пусть
n=2
u2
b2 1
-1
a1
1
a2
0
b1
ì
ì
æ0ö
æ 0 öü
æ -1 ö
æ 1 öü
V
=
b
=
,
b
=
и U = ía1 = ç ÷ , a2 = ç ÷ ý ,
í 1 ç ÷ 2 ç ÷ý.
è -1ø
è 1 øþ
è0ø
è 0 øþ
î
î
Тогда r U , V = 2. С другой стороны
cU l = max ai , l = max { -l1 , l1} = l1 ,
u
1
iÎ{ 1,2}
cV l = max bi , l = max { -l2 , l2 } = l2 ,
iÎ{ 1,2}
-1
Таким образом,
max cU l - cV l = max
lÎS 0,1
l Î S 0,1 .
l1 2 + l2 2 =1
l1 - l2 = 1 < 2 = r U , V .

12.

Ì R n компактное множество и u Î int U . Тогда
u, l < cU l , "l Î S 0, 1 .
3
Обратно, если выполнено условие (3), то u Î int U .
Доказательство. Пусть u Î int U . Тогда O u , e Ì U для некоторого числа
e > 0. Для всех l Î S 0, 1 имеем
Теорема 8. Пусть U
u , l + c O 0,e l
64 7 48
c O u ,e l £ cU l Þ
e× l
64 7
48
u, l + c O 0,e l £ cU l Þ
1
u , l + e × l £ cU l Þ u , l < cU l , "l Î S 0, 1 .
Обратно, пусть
Непрерывная функция
S 0, 1 ,
Тогда
u , l < cU l , "l Î S 0, 1 .
j l = cU l - u , l
поэтому ее минимум на
S 0, 1
строго положительна на компакте
строго положителен.
Обозначим его через
e = min j l = min éë cU l - u , l ùû > 0.
lÎS 0,1
lÎS 0,1

13.

cU l - u, l ³ min éë cU l - u, l ùû = e Þ
lÎS 0,1
cU l - u , l ³ e Þ
cO u ,e l
l
u , l + e × 1 £ cU l , "l Î S 0, 1 Þ
6 44 7 4 48
u, l + e l £ cU l , "l Î S 0, 1 Þ
и точка
c O u ,e l £ cU l , "l Î S 0, 1 Þ O u , e Ì U ,
u внутренняя для U .
Теорема 9.
условие
Для любых выпуклых компактов
A B ¹ Æ
A, B Ì R n
имеет место тогда и только тогда,
A
когда выполнено неравенство
min l , a £ c B (l ), " l Î S 0, 1 .
aÎ A
Доказательство. Необходимость. Пусть
min l , a
aÎA
A É AI B
£
A I B ¹ Æ.
q, l
min l , q £ qmax
Î AI B
qÎAI B
что и доказывает необходимость.
B
AI B Ì B
£
AI B
4
Тогда
)
64c7B (l4
8
max q, l = c B (l ), " l Î S 0, 1 ,
qÎB

14.

Достаточность. От противного по теореме 4 (о сильной отделимости выпуклых
множеств)
l * Î S 0, 1 ,
приходим к существованию вектора
для которого
min l * , a > max l * , b = c B (l * ).
aÎA
bÎB
Последнее соотношение противоречит (4).
Теорема доказана.
Упражнение. Пусть
A, B Ì R ,
n
min l , a £ c B (l ), " l Î S 0, 1 .
aÎA
A I B = Æ.
Вывести формулу для
вычисления величины
{
a
}
e = min a A I B ¹ Æ ,
A
B
e
Решение.
В силу теоремы 9 величина
удовлетворяющих неравенству
e-
наименьшее из положительных чисел
mina l , aˆ £ c B (l ), " l Î S 0, 1 .
aˆÎA
4
*
a,

15.

mina l , aˆ £ c B (l ), " l Î S 0, 1 .
aˆÎ A
Заметим, что
mina l , aˆ =
aˆÎ A
min
aˆÎ A+ O 0,a
l , aˆ = min l , a + s =
aÎA,
sÎO 0,a
= min l , a + min l , s =
sÎO 0,a
aÎ A
*
min l , a - a .
aÎ A
Подставим полученное выражение в (*). Имеем
min l , a - a £ max l , b , " l Î S 0, 1 Þ
aÎ A
bÎB
a ³ min l , a - max l , b , " l Î S 0, 1 Þ
aÎA
bÎB
e = max é min l , a - max l , b ù .
lÎS 0,1 ë aÎA
bÎB
û

16.

Упражнение.
Проверить полученную формулу для множеств
ææ0ö ö
ææ 2ö ö
2
A = O ç ç ÷ ,1÷ Î R , B = O ç ç ÷ ,1÷ Î R 2
èè0ø ø
èè 2ø ø
y
Решение.
B
e1 = max é min l , a - max l , b ù .
lÎS 0,1 ë aÎ A
bÎB
û
e1
A
x
é
ù
ê min l , a - c
ú=
= max
l
ææ 2ö ö
ú
ææ0ö ö
l12 + l22 =1 ê
O
çç ç ÷,1÷÷
aÎO çç ç ÷,1÷÷
èè 2ø ø
êë è è 0 ø ø
úû
é
ù
æ 2 ö æ l1 ö
2
2
2
2
= max
ê - l1 + l2 - ç ÷ , ç ÷ - l1 + l2 ú =
l12 + l22 =1
êë
è 2 ø è l2 ø
úû
é æ 2 ö æ l1 ö
ù
é æ 2 ö æ l1 ö ù
= max
ê - ç ÷ , ç ÷ - 2 ú = max
ê ç ÷ , ç ÷ ú - 2 = 2 2 - 2.
2
2
2
2
l1 + l2 =1
êë è 2 ø è l2 ø
úû l1 +l2 =1 êë è 2 ø è l2 ø úû
Результат согласуется с рисунком.

17.

Теорема 10. Для любых компактных множеств U , W
и чисел
Ì R n , матриц
A n n
выполняются равенства
1. co U + W = co U + co W ;
2. co U = co U ;
3. co AU = Aco U .
Доказательство. Множества в правых и левых частях этих соотношений выпуклы и
компактны, их опорные функции совпадают, следовательно, совпадают и сами
множества.
n
Приведем подробное доказательство для первого равенства. Пусть v Î R . Имеем
c co U +W v = c U +W v = cU v + cW v =
= c coU v + c coW v = c coU + coW v .