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

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

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

2.

2. ВЫПУКЛЫЕ МНОЖЕСТВА (ПРОДОЛЖЕНИЕ)
2.5. Выпуклые оболочки.

3.

2.5. Выпуклые оболочки. Сформулируем и докажем одно свойство выпуклых
множеств, которое иногда непосредственно берется за определение выпуклого множества.
Определение 9. Пусть
m
таковы,
что
åa
i =1
точек
i
u1 , , u m R n
= 1. Точка u =
m
åa u
i =1
i i
и числа
a1 0, , a m 0
называется выпуклой комбинацией
u1 ,L , um R n .
Теорема 9
Множество U
Ì Rn
выпукло тогда и только тогда, когда оно
содержит все выпуклые комбинации любого конечного числа своих точек.
Необходимость. Пусть множество
m.
При
m=2
U
выпукло. Проведем индукцию по числу
справедливость утверждения теоремы вытекает непосредственно
из определения выпуклого множества. Предположим, что утверждение теоремы верно
для любого
k £ m - 1, m > 2.
Рассмотрим произвольную выпуклую комбинацию

4.

каких-либо
m
точек этого множества
m
u = å a i ui , u1 ,L , um U ,
i =1
Требуется доказать, что
u U .
a1 0,L , a m 0,
Для определенности примем, что
m -1
1 - a m = å a j > 0.
j =1
aj
bj =
,
1- am
j = 1,L , m - 1, v = å b j u j R n ,
m -1
тогда
j =1
i =1
i
=1
a m < 1.
Тогда
j = 1,L , m - 1.
j =1
aj
å
åa
Полагаем
m -1
Имеет место равенство
m -1
m
1-a m
}
bj =
-a m
6417
48
m -1 a
1 æ m -1 ö
j
=
× ç åa j ÷ = 1
å
1 - a m è j =1 ø
j =1 1 - a m
v = å b j u j является выпуклой комбинацией m - 1 точек u1 ,L , um -1 U .
i =1
В силу предположения индукции v U . Тогда из выпуклости множества
U
U
æ ( 0,1) ö } ( 0,1) }
ç 1 - a m ÷ v + a m um U .
è
ø
С другой стороны
U
следует

5.

U
6 4 4 47
4 4 48
m-1
å b ju j
i =1
}
( 1 - a m ) v + a m um =
aj
m -1
( 1- am ) å
j =1
1-a m
}
b j u j + a mum =
m -1
m
aj
u j + a mum = å a j u j + a mum = å a i ui = u.
( 1- am ) å
j =1
i =1
j =1 1 - a m
Таким образом u U . Необходимость доказана.
n
Достаточность. Если множество U Ì R содержит все выпуклые комбинации
m -1
любого конечного числа своих точек, то оно содержит, в частности, и любые выпуклые
комбинации любых своих двух точек, следовательно, оно выпукло. Достаточность доказана.
n
Приведем одно простое свойство выпуклых комбинаций конечного числа точек из
R .
Теорема 10. Пусть
u1 , , u m R n
– фиксированные точки и
v1 ,L , vs -
– их произвольные выпуклые комбинации. Тогда любая выпуклая комбинация точек
v1 , , v s
является выпуклой комбинацией точек
u1 ,L , um .
Доказательство. Действительно, для любой из точек
представление
v1 , , v s
справедливо

6.

m
m
v j = å a ji ui ,
åa
i =1
Тогда для любых
m
å
i =1
s
}
w = å b j vj =
å b ja ji
j =1
m
}
å gi =
и точка
a ji 0,
b1 0,L , b s 0,
s
m
å b åa
j =1
j
i =1
m
u =
ji i
s
åb
j =1
j
j = 1,L s, i = 1,L , m.
=1
m
s
åå b a
j =1 i =1
j
имеет место
ji
64 7g i 48
m
s
ui = åå b ja ji ui = å g i ui .
i =1
i =1 j =1
s
Очевидно, что
i =1
= 1,
a ji ui
j =1
s
i =1
ji
g i = å b ja ji 0, i = 1,L , m.
j =1
Кроме того
64 7=1 48
}=1
s
m
ö s
æ s
ö s æ m
ç å b ja ji ÷ = å ç å b ja ji ÷ =å b j å ( a ji ) = å b j = 1
å
j=
ø j =1 i =1
i =1 è j =1
ø j =1 è i =1
w будет выпуклой комбинацией точек u1 ,L , um с коэффициентами
m
g i , i = 1,L , m
Теорема доказана.
n-
мерного
Из доказанной теоремы легко выводится, например, что любая точка
куба является выпуклой комбинацией своих вершин. Покажем это на примере
двухмерного куба (квадрата).

7.

На рисунке видно, что точка
комбинацией точек
E
и
F.
M
B
является выпуклой
E
Те в свою очередь являются
M
A, D и C , B
соответственно. Таким образом, точка M является
выпуклой комбинацией вершин куба A, B, C , D.
выпуклыми комбинациями вершин
Упражнение. Доказать непосредственно, что точка
комбинацией точек ABCD.
Решение.
C
A
M
F
D
является выпуклой
uE = a B uB + a C uC , a B 0, a C 0, a B + a C = 1,
uF = a Au A + a D uD , a A 0, a D 0, a A + a D = 1,
Þ
uM = a F u F + a E uE , a F 0, a E 0, a F + a E = 1.
a B uB +a C uC
a Au A +a D uD
uM = a F
}
uF
+ aE
}
uE
= a F ( a Au A + a D uD ) + a E ( a B uB + a C uC ) =
}b1
}b2
}b3
}b4
= a F a A u A + a F a D uD + a Ea B uB + a Ea C uC = b1u A + b1u D + b1u B + b1uC

8.

bi 0, i = 1,L , 4 и
a Ea C
aFa A
a FaD
a Ea B
}
}
}
}
b1 + b 2 + b3 + b 4 = a F a A + a F a D + a Ea B + a Ea C =
Очевидно, что
64 7=1 48
64 7=1 48
64 7=1 48
= a F ( a A + a D ) + a E ( a B + a C ) = a F + a E = 1.
В тех случаях, когда рассматриваемое множество не выпукло бывает полезно
расширить его до выпуклого множества. По аналогии с аффинной оболочкой множества
введем понятие выпуклой оболочки множества.
Определение 10. Пересечение всех выпуклых множеств, содержащих множество
U Ì Rn ,
U coU
называется выпуклой оболочкой множества и
обозначается
Множество
coU .
coU
выпукло как пересечение выпуклых
множеств, и оно содержится в любом выпуклом множестве,
содержащим
U.
Таким образом, выпуклую оболочку множества
как минимальное выпуклое множество, содержащее
U.
U
можно трактовать

9.

U coU
состоит из
тех и только тех точек, которые являются выпуклыми
комбинациями конечного числа точек из
Доказательство. Пусть
числа точек из
U Ì Rn
Теорема 11. Выпуклая оболочка множества
U.
U.
W - множество всех выпуклых комбинаций
Покажем, что
так как в силу выпуклости множества
co U = W .
co U
Вложение
конечного
W Ì co U
оно будет содержать все
очевидно,
(теорема 9)
выпуклые комбинации конечного числа своих точек, в частности, и точек из множества
U Ì coU . Для доказательства обратного вложения co U Ì W
достаточно установить выпуклость множества
комбинация конечного числа точек
W.
в силу
Действительно, пусть
w1 ,L , wm W .
Каждая из точек
U ÌW
w-
выпуклая
wi W
U . Тогда по теореме 10 точка
w будет выпуклой комбинацией конечного числа точек из U . Последнее означает, что
является выпуклой комбинацией конечного числа точек из
w W .
Таким образом, любая выпуклая комбинация любого числа точек множества
ему принадлежит. Следовательно в силу теоремы 9 множество
доказана.
W
W
выпукло. Теорема

10.

В качестве примера заметим, что выпуклая оболочка двух точек на плоскости
представляет собой отрезок прямой, их соединяющий; трех точек, не лежащих на одной
прямой – треугольник. В общем случае выпуклая оболочка конечного числа точек
на плоскости, не лежащих на одной прямой, образует выпуклый многоугольник,
а в пространстве – выпуклый многогранник.
Частным случаем выпуклой оболочки множества, состоящего из конечного числа
точек,
является
n-
мерный симплекс.
Определение 11. Выпуклая оболочка множества точек
для которых набор векторов
u1 - u 0 , , u m - u 0
u0 , u1 ,L , um R n ,
линейно независим, называется
симплексом, натянутым на эти точки и обозначается символом
Точки u 0 , u1 , , u m
называются вершинами симплекса.
B
В частности, симплекс, натянутый на три точки
плоскости,
A
S ( u0 , u1 ,L , um ) .
C
не лежащие на одной прямой,
треугольник с вершинами в этих точках.
A, B, C
будет

11.

Согласно теореме 10 справедливо равенство
S ( u0 , u1 ,L , um ) =
Теорема 12 (Каратеодори). Пусть
Тогда любая точка
n +1
u co U
m
m
ì
ü
íu = å a i ui a i 0, å a i = 1ý .
i =0
i =0
î
þ
U Ì R n – произвольное непустое множество.
представима в виде выпуклой комбинации не более чем
точки из U .
Доказательство. По теореме 11 любая точка
u co U
m
m
i =1
i =1
представима в виде
u = å a i ui , a i 0, ui U , i = 1,L , m, å a i = 1. ( 1)
Будем считать, что a i > 0, i = 1,L , m, т. к. в (1) нас интересуют только ненулевые слагаемые.
Покажем, что число слагаемых (ненулевых!) в этом выражении можно уменьшить, если
m > n + 1.
Пусть
m > n + 1.
В пространстве
R n +1
рассмотрим
æ ui ö
ui = ç ÷ R n +1 , i = 1,L , m > n + 1.
è1ø
m векторов вида

12.

m > n + 1,
Число таких векторов
g 1 , , g
Тогда существуют числа
æ ui ö
gi ç ÷ = 0 Þ
å
i =1
è1ø
m
В силу (1) u =
m
m
å a iui ,
åai = 1
i =1
i =1
m
å( a
i =1
i
åg u
i =1
m
åg
из условия
s
i
i
- tg i ) =
g 1 , , g m
и число
= 0,
( 2)
= 0.
1
справедливы равенства
для
всех
и
(2)
t
R
1
( )
)Þ= 0
6(1)7Þ=8u
6( 27
8
m
m
åa u - t × å g u
i i
i =1
(1)Þ=1
m
åa
i =1
t
= u,
i i
i =1
( 2 )Þ= 0
}
m
i
- t × å g i = 1.
i =1
равны нулю, а их сумма равна нулю, постольку
среди них найдутся строго положительные.
Определим номер
i i
}
å(a
Поскольку не все числа
m
i =1
- tg i ) ui =
m
i =1
поэтому они линейно зависимы .
что будет выполняться
m не все равные нулю,
Полагаем
I = { i { 1,L , m} g i > 0} .
}>0
æ ai
as
t = >0 = min ç
}
i I
è gi
gs
ö
÷ > 0.
ø

13.

Покажем, что для всех номеров
Действительно, для
а для
i = 1, , m
справедливо неравенство
i Ï I = { i { 1,L , m} g i > 0}
i I вычисляем
a i - t g i 0.
>0
это очевидно:
>0 £0
a i - t g i > 0,
æa ö
= min ç i ÷
i I è g i ø
}
as
ai
a
g
a i - t g i = i
g i = 0.
i ai gs
gi
При этом при
i=s
имеем
=
as
gs
}
as
( a i - t g i ) i = s = a s - t g s = a s - g s = 0.
gs
Таким образом, точку u удалось представить в виде выпуклой комбинации
64 7 0 48
u = å ( a i - t g i ) ui ,
m
i =1
i¹s
Теорема доказана.
64 7 0 48
å ( a i - t g i ) = 1 меньшего, чем m числа точек из множества U .
m
i =1
i¹s