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

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

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

2.

6. ТЕОРЕМЫ ОБ ОТДЕЛИМОСТИ ВЫПУКЛЫХ
МНОЖЕСТВ
6.1. Проекция точки на множество
6.2. Отделимость точки и множества.
6.3. Отделимость выпуклых множеств.

3.

6.1. Проекция точки на множество
n
Определение 1. Пусть U Ì R .
n
Проекцией точки v R на множество U
называется точка
w
U
w = PU (v) U ,
удовлетворяющая условию
u
w - v = inf u - v .
u U
v
Справедливо следующее утверждение.
Теорема 1. Пусть U
v Rn
Ì R n замкнутое множество. Тогда для всякой точки
существует ее проекция на это множество.
то проекция единственна и равенство
тогда, когда
w = PU (v )
w - v, u - w ³ 0, "u U .
Если множество
U
выпукло,
имеет место тогда и только
( 1)
w = PU (v) - проекции точки v
1
множество U сводится к минимизации функции I : U ® R , определенной
Доказательство.
Задача построения
на

4.

равенством
( 2)
I (u ) = u - v 2 = u - v , u - v .
Очевидно, что точка минимума этой функции,
O ( v, r )
v
принадлежать множеству
B u U
w
где
O ( v, r )
для него
r
PU (v) = w.
если она существует,
должна
B = O ( v, r ) I U ,
шар столь большого радиуса, что
B ¹ Æ.
Множество
и выпукло, а функция
I
B
компактно
непрерывна, поэтому по
w U
теореме Вейерштрасса точка минимума
функции I действительно существует, т.е.
По теореме 5.2 (минимум гладкой выпуклой функции) выводим
2( u - v )
u =w
I '( w) , u -
Единственность точки
Теорема доказана.
точка
минимума
w
³0Þ
w = PU (v)
w - v , u - w ³ 0 " u U .
следует из строгой выпуклости функции (2).

5.

6.2. Отделимость точки и множества.
разделить гиперплоскостью так,
полупространствах,
что они будут находиться в разных замкнутых
определяемых этой гиперплоскостью.
Теорема 2. Пусть
v int U
Точку и выпуклое множество можно
U Ì Rn
выпуклое множество. Тогда для любой точки
существует вектор l ¹ 0, такой, что
u
l , u ³ l , v , " u U ,
v U ,
если при этом
l
то
v
2
l, u ³ l, v + l , " u U .
Доказательство.
Сначала рассмотрим случай
v U .
и выпукло. Тогда согласно теореме 1 существует проекция
v
на множество
U,
U
w = PU ( v ) U
Множество
причем
w - v ¹ 0,
замкнуто
U
w - v, u - w ³ 0, "u U .
Заметим, что
U
так как
v U .
(1)
Положим
v
l = w - v.
w
Тогда
точки

6.

w- v
l , u - v = w - v, u - v = w - v, u - v ± w = w - v , ( u - w ) + ( w - v ) =
6 44( 1)7Þ ³40 48
= w - v, u - w +
l
l
w - v, w - v ³ l , l = l
2
l, u - v ³ l Þ l, u ³ l, v + l
2
2
Þ
v
" u U
и для рассматриваемого случая теорема доказана. l , u ³ l , v + l
Пусть теперь v U \ int U .
Тогда
v k ® v, v k U , k = 1,2,
выше существует вектор
lk ¹ 0
v (U )
Для каждого номера
требуемое соотношение.
то обе части
lk > 0, k = 1, 2,L Переходя,
если это необходимо, к подпоследовательности, принимаем, что
k
по доказанному
( 1)
lk = 1, k = 1, 2L . Если бы это было не так,
В неравенстве (1) устремим
, " u U
k = 1,2,
такой, что
неравенства (1) следовало бы поделить на величину
l = 1 ¹ 0.
2
vk
и существует последовательность
lk , u > lk , vk , " u U .
Можно считать, что
U
lk ® l .
При этом
в бесконечность. В пределе получим
l , u ³ l , v , " u U
Теорема доказана.

7.

Доказанной теореме придадим следующий геометрический смысл. Пусть
u
l
v
v U
и l ¹ 0 - вектор существование которого доказано
в теореме 2. Этот вектор будет нормальным для
U
P ( l, g )
гиперплоскости
G ( l, g ) = u Rn
G ( l, g )
( 2)
l, u = g ,
разделяющей точку v и множество U . При изменении величины g гиперплоскость
будет перемещаться параллельно самой себе. Она будет оставаться разделяющей, если
l , u ³ l , v , " u U Þ inf l , u ³ l , v
g
6 4 4 7 4u U4 8
é l , v ,inf l , u ù
u U
ë
û
Для него гиперплоскость
Пусть теперь
Полупространство, содержащее множество
.
G ( l, g )
P ( l, g ) = u Rn
inf l , u £ l , v .
u U
Тогда
v
inf l , u = l , v Þ g é l , v ,inf l , u ù Þ g = l , v Þ
u U
u U
ë
û
v G ( l, g ) = G ( l, l, v ) .
имеет вид
l, u ³ g .
служит границей.
v ( U ) = U \ int U . В этом случае v U
и должно выполняться неравенство
U,
U

8.

В этом случае разделяющая гиперплоскость
U
и множество
G ( l, l, v
v.
имеют общую точку
)
G ( l, l, v
G ( l , l , v ) называется опорной
к множеству U в точке v U .
l
v
U
U
в точке
)
Гиперплоскость
Полупространство P
Вектор
l
( l,
l, v
)
называется опорным к множеству
называют опорным вектором к множеству
Заметим, что если множество
U
U
в точке
v.
компактно, то любой вектор
P ( l, l, v
)
v U .
l S ( 0,1)
U в некоторой точке v ( l ) U .
l , v ( l ) = min l , v .
может служить опорным к множеству
Эта точка определяется из условия
G ( l, l, v
U
l
v( l)
)
Множество
v U
совокупность всех точек
v U
v( l)
V ( l) .
может содержать более одного
элемента.
V ( l ) = v ( l ) U l , v ( l ) = min l , v -
U
l
G ( l, l, v
)

9.

V ( l)
Множество
вектора
называется опорным множеством к множеству
l.
G ( l, l, v
Опорные гиперплоскости
для всех
v V ( l )
U
в направлении
) и опорные полупространства P ( l ,
l, v
)
совпадают между собой. Эту гиперплоскость и полупространство
будем называть опорной гиперплоскостью и опорным
P ( l, l, v
U
)
полупространством к множеству
V ( l) .
l
вектора
G ( l, l, v
)
l
и обозначать символами
соответственно.
Таким образом,
P( l) = u R
l , u ³ min l , v .
G ( l ) = u R n l , u = min l , v .
v U
n
v U
( 2)
(3)
U
в направлении
G( l) , P( l) ,

10.

ìïæ x ö x 2 y 2
üï
U = íç ÷
+
£ 1ý Ì R 2
ïîè y ø 20 5
ïþ
Упражнение. Для множества
y
опорное множество,
V ( l)
x
xV
l
построить
отвечающее направлению
Решение.
æl =ç
çè
Запишем уравнение касательной к эллипсу,
перпендикулярную направлению l.
Имеем
-1
y = k x + b Þ y = -x + b
Координата
xV
является корнем уравнения
x ( -x + b)
2
2
+
=1Þ
x + 4 ( - x + b ) = 20 Þ
20
5
2
2
2
2
2
5
x
8
xb
+
4
b
- 20 = 0 Þ
x + 4 x - 8 xb + 4b - 20 = 0 Þ
2
2
4b ± 16b 2 - 20b 2 + 100 4b ± -4b 2 + 100
x1,2 =
=
.
5
5
ö
.
÷
2 ÷
2 ø
2
2

11.

4b ± 16b 2 - 20b 2 + 100 4b ± -4b 2 + 100
x1,2 =
=
.
5
5
Корень должен быть только один. Тогда
y
l
æ xV
ç
è yV
V ( l)
xV
x
b = ±5, xV = ±4, yV = ±1
ö æ -4 ö
÷ = ç ÷ не подходит, т. к.
ø è -1 ø
l, v ( l )
æ= min l , v , l = ç
v U
çè
Из чертежа видно, что
ö
÷.
2 ÷
2 ø
2
2
ìæ 4 ö ü
V ( l ) = íç ÷ ý .
îè 1 ø þ

12.

6.3. Отделимость выпуклых множеств. Результаты предыдущего пункта допускают
обобщение на случай, когда вместо точки берется выпуклое множество.
Определение 2. Будем говорить, что множества
некоторого вектора
l S ( 0,1)
A, B Ì R n отделимы,
если для
справедливо неравенство
( 2)
sup l , b £ inf l , a Û $g R1 : l , b £ g £ l , a , "a A, b B ,
a A
b B
строго отделимы, если
l , b < l , a , "a A, b B ,
сильно отделимы, если знак неравенства в (2)
sup l , b £ inf l , a
b B
a A
( 2)
строгий.
Геометрический смысл отделимости множеств состоит в существовании
гиперплоскости
множества
G ( l , g ) = u R n u, l = g , l S ( 0,1) , g R1 , для которой
Aи B
находятся в разных по отношению к ней полупространствах.
Такую гиперплоскость называют отделяющей (строго, сильно).
Ниже дается геометрическая интерпретация различных случаев отделения.

13.

l, b < l, a ,
sup l , b £ inf l , a
a A
b B
"a A, b B,
l
A
G ( l, g )
l
A
B
G ( l, g )
G ( l, g )
Отделимость
a A
b B
A
l
B
sup l , b < inf l , a
BB
Сильная
отделимость
Строгая
отделимость
В теореме 2 утверждается, что любая точка, не принадлежащая выпуклому
множеству, отделима от его замыкания, и если при этом точка не принадлежит
замыканию множества, то отделение сильное.
Теорема 3. Пусть
множества
A
и
B
A, B Ì R n непустые выпуклые множества и A I B = Æ. Тогда
можно отделить. Причем, если
то в отделяющей гиперплоскости
g = l, v ,
A B ¹ Æ
G ( l , g ) = u R n u, l = g
и
v A I B,
можно положить
т. е отделяющая гиперплоскость будет проходить через точку
v.

14.

Доказательство. Рассмотрим множество
Множество
U = A - B = u = a - b a A, b B .
U выпукло. Поскольку A I B = Æ, постольку 0 U .
теореме 2 существует вектор
l S ( 0,1) ,
что
a -b
Тогда по
l , u ³ l , 0 = 0, " u U .
Отсюда выводим
( 3)
l , a - b ³ 0 Þ l , a ³ l , b , a A, b B.
Пусть теперь
a A, b B. Найдутся последовательности
ak ® a, bk ® b,
ak A, bk B, k = 1, 2,L .
В силу неравенства (3) будет выполняться
l , ak ³ l , bk , k = 1, 2,L
Переходя в последнем неравенстве к пределу при
k ® ¥,
получим
l , a ³ l , b , " a A, b B ,
что и означает выполнение неравенства (2).
sup l , b £ inf l , a
b B
a A
( 4)
( 2)

15.

Пусть, наконец,
v A I B ¹ Æ.
l , a ³ l , b , " a A, b B ,
а с другой из
v B
( 4)
и снова (4) следует
v A
Тогда с одной стороны из
вытекает, что
и (4)
l , b £ l , v , "b B ,
l , a ³ l , v , "a A.
Таким образом,
l , b £ l , v £ l , a , "a A, "b B Þ g = l , v .
Теорема доказана.
Теорема 4. Пусть
A, B Ì R n
одно из которых ограничено и
отделимы. sup
b B
непустые выпуклые замкнутые множества,
A
A I B = Æ. Тогда множества
B
сильно
l , b < inf l , a
a A
Доказательство. В условиях доказываемой теоремы множество
замкнуто.
и
Действительно, пусть для определенности множество
предельная точка множества U , и последовательность
ak A, bk B, k = 1, 2,L
U = A- B
A
uk ® u, где
ограничено,
U = A - B
uk
u-
= ak - bk ,
В силу ограниченности (компактности) множества
A

16.

из последовательности
a ® a A.
Из
kj
a k
можно извлечь сходящуюся подпоследовательность
uk = ak - bk
® a A
следует
В результате предельного перехода при
A
U
A
U
®u U
bk = ak - uk Þ bk j = ak j - uk j .
kj ®¥
получим
bk j ® b = a - u.
ak j - uk j ® a - u = b A - U Þ
Тогда
В силу замкнутости множества B, выполнено включение b B.
A
B
b = a -u Þ u = a- b, Þ u A- B =U,
Таким образом, предельная точка
u
множества
U
принадлежит множеству
U,
что и означает его замкнутость.
Из условия
A B = Æ
следует, что
0 U = U .
По теореме 2 существует
вектор l ¹ 0, такой, что
a -b
2
l , u ³ l , 0 + l , " u U Þ l , u ³ l , " u U .
2
Отсюда выводим
2
l , a - b ³ l , " a A, b B.

17.

l , a - b ³ l , " a A, b B Þ l , a ³ l , b + l
2
inf l , a ³ sup l , b + l
a A
Теорема доказана.
b B
2
2
" a A, b B Þ
l , a > sup l , b
Þ inf
a A
b B
G ( l, g ) = u Rn l, u = g ,
æ
ö
g ç sup l , b , inf l , a ÷
g
sup l , b
inf l , a
a
A
è b B
ø
Может служить сильно отделяющей для множеств A и B.
Заметим, что любая гиперплоскость
b B
a A
где