Similar presentations:
Выпуклый анализ. Выпуклые множества. Лекция 6
1. ВЫПУКЛЫЙ АНАЛИЗ
ЛЕКЦИЯ 62. ВЫПУКЛЫЕ МНОЖЕСТВА
(ПРОДОЛЖЕНИЕ)
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.
U6 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.
mm
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