Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 44
Текст из файла (страница 44)
Множество Х =(и=(х, у) ЕЕ', — 1< х < 1, у=О) выпукло и не имеет внутренних точек; Х = (и = (х, у): — 1 < х < 1, у = 0). Для любого аффинного множества М из .Е" имеем М =М, так что М— замкнутое множество: это видно, например, из представления (4) аффинного множества; для множеств из примеров 6-8 также Х = Х. В частности, аН Х = аНХ, откуда будет следовать, что аН Х = аН Х для любого множества Х из Е . Т е о р е м а 2. Если А — выпуклое множество, то гго замыкание тоже выпукло. Д о к а з а т е л ь с т в о. Пусть а и Ь вЂ” произвольные точки множества А. Поскольку выпуклое множество не имеет изолированных точек, то точки а и 6 будут предельными для А.
Тогда существуют последовательности (а,), (6,) Е А, сходящиеся соответственно к а, Ь. Возьмем произвольные сс е [О, 1с!. В силу выпуклости А тогда с, = сса,, + (1 — сс)Ь„Е А. Отсюда при Ь вЂ” ~ оо получим !!ш с = с, = сла+ (1 — ст)6. Таким образом, точка с является предельной для А и, следовательно, принадлежит А при любом ссЕ[0,1). П Теорема 3, Пусть Х вЂ” выпуклое множество и 1п1 Х ф0.
Пусть и Е щ1 Х, и Е Х, Тогда и„= и + сс(иь — и) Е !и! Х пди всех сс, 0 < сл < 1. Если и Е !п1 Х, уф !п1 Х, у ЕХ, то и„= и+ Л(у — и) Р Х при всех Л >1. Доказательство. Поскольку точка и Е !п1 Х, то найдется ее б-окрестность О(и, б) =(и: [и — из[< б), целиком принадлежащая Х. Сначала рассмотрим случай, когда и Е Х. Возьмем произвольное сх, 0 < сс < 1. Рис. 4.3 Покажем, что окрестность 0(и„, ссб) =(и: [и — и„[ < ссб) точки и„принадлежит Х. С этой целью возьмем произвольную точку и е О(и, ссб) и положим а=ил+(и — и )/сл (рис.
4,3). Поскольку [а — иь =[и — и„[/сс < бсл/сх = б, то аЕ 0(и„б) С Х. Йз определения точки а имеем представление и = и + +сс(а-иь)=и+сс(иь — и)+сс(а — иь)=сса+(1 — а)и, где а, иЕХ и 0< сс <1. Тогда и Е Х в силу выпуклости Х, Тем самым показано, что произвольная точка и из 0(и, слб) принадлежит Х. Следовательно, 0(и„, ссб) с Х, т, е. о„— внутренняя точка Х.
154 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Пусть теперь и е Х 1Х. Поскольку и — предельная точка Х, то найдется точка ю е Х такая, что !и — ю) < а(1 — а) '6. Возьмем точку ю = ю+ + сх(и — ю) (рнс. 4.4). В силу только что доказанного точка ю принадлежит множеству Х вместе со своей окрестностью 0(ю, сх6).
Но ~и — ю„) = [и+ + а(и — и) — ш — а(и — ш)! = (1 — а)[и — ш! < (1 — а)а(1 — а) '6 = а6. Следовательно, и„Е 0(ю, а6) С Х. Убедимся, что окрестность 0(и„)т) ()3 = 6а — ~и — ю [) точки и«также принадлежит Х. В самом деле, если и Е 0(п„,ф), то ~и — ю ( !и — и !+ !и — ю„! <!9+ !и — та„~ = 6а, т. е. О(и, )У) Е 0(юо, а6) Е Х. Рис. 4.4 Наконец, пусть ю, =и+ Л(у — и) (Л > 1), где и 6 [и! Х, уср!п1 Х, уЕХ. Допустим, что ю, Е Х прн каком-либо Л > 1.
Из представления для ю„ имеем у =и+(та, — и)(Л = ю, +(1 — 1/Л)(тл — ю„) = ю, + а(и — ис,), где а = 1 — [/Л Е (О, 1), ю Е Х, и Е [п1 Х. По доказанному выше тогда у Ып! Х, что противоречит условию. Следовательно, ю„ ф Х прн всех Л > 1. П Теорема 4. Если Х вЂ” выпуклое множество, то [п1 Х тоже выпукло. Доказательство. Пусть и,и — 'произвольные точки нз !п1Х. В теореме 3 было показано, что и„=аи+(1 — а)иЕ[п! Х прн всех а, О< а <1. Это н означает выпуклость [и! Х.
С) 3. В тех случаях, когда рассматриваемое множество Х невыпунло, часто бывает полезно расширить его до выпуклого множества. Посмотрим, как это делается. О и р еде л е н и е 7. Точка и называется выпуклой комбинацией точек ис,..., и, если существуют числа а! >О,..., сс >О, ос!+...+ а =! такие, что и=с«!и!+...+ а и Теорема 5. Множество в«тук«о тогда и только тогда, когда оно содержит всг выпуклые комбинации любого конечного числа своих точек. Доказательство. Необходимость, Пусть Х вЂ” выпуклое множество.
Тогда по определениго 1 множество Х содержит выпуклые комбинации любых двух своих точек. Сделаем индуктивное предположение: пусть множество Х содержит выпуклые комбинации лсобых т-1 своих точек. Рассмотрим выпуклусо комбинацию оси!+...+а и произвольных сп точек из Х. Можем считать, что а! > О, с = 1,,, т, Поскольку сс! +... + а = 1, то ы-! 0 < ас < 1, с = 1,..., т. Следовательно, точка о = ~; ас(1 — а„,) !и! является выпуклой с=! комбинацией точек ис,...,и ! и по предположению индукции принадлежит Х, Однако « †! и =(1 — а ) Л; ас(1 — а„,) !и!+ а и =(! — ат)о+ а и Е Х в силУ выпУклости Х.
с=! $1. ВЫПУКЛЫЕ МНОЖЕСТВА 155 Достаточность. Если множество Х содержит все выпуклые комбинации любого конечного числа своих точек, то оно содержит, в частности, выпуклые комбинации любых двух своих точек и, следовательно, выпукла. П О п р е д е л е н и е 8. Пересечение всех выпуклых множеств, содержащих множество Х, называется выпуклой оболочкой множества Х н обозначается через со Х Ясно, что соХ, как пересечение выпуклых множеств, является выпуклым множеством. Кроме того, со Х содержится в любом выпуклом множестве, содерукащем Х.
Тзк что со Х— это минимальное выпуклое множество, содержащее Х Теорема 6, Выпуклая оболочка множества Х состоит из тгх и только те точек, которьсе являются гыпуклой комбинацией конечного числа точек иэ Х. Если Х выпукло, то со Х = Х. До к а з а т е л ь с т в о. Пусть И' — множество всех точек, являющихся выпуклыми комби нациями любого конечного числа точек из Х. Нам надо показать, что со Х = Ис.
Поскольк Х С со Х и со Х вЂ” выпунлое множество, то по теореме 5 со Х соде жит все выпуклые ком х у бинации точек из со Х и, в частности, точек из Х. Следовательно, ру С со Х, Покажем, что Иг — выпуклое множество. В самом деле, пусть и, о е Ис, т. е.
и= а!и!+... ... + а и, ис е Х, ас > О, ! = 1,..., т, а! +... + а„, = 1, о = )усе! -'г... + Еров, ог Е Х, т г Ес >О, «=1,,р, Вс+,,+ 3 =1. Тогда и =аиж(1 — а)о= 2 аа и,. + ~" (1 — сс)Е оу т г г '=! !'=! где асс; > О, (! — а)!З > О, 2 аа, 4 ~; (1 — а)ду = 1 для каждого а е [О, 1]. Следовательно, с=! !'=! и является выпуклой комбинацией точек ис,..., и, ос,..., о е Х и принадлежит И' при всех а е [О, 1!. Таким образом, Ис — выпунлое множество, содержащее Х.
Но со Х по своему определении принадлежит всем выпуклым множествам, содержащим Х, и поэтому со Х С и'. Сравнивая с ранее доказанным включением И' С со Х, заключаем, что со Х = Иг. Если Х— выпуклое множество, то с учетом теоремы 5 имеем Х = Ис = со Х. Теорема 6 доказана. Г1 Заметим, что выпуклая оболочка двух точек на плоскости представляет собой отрезок, выпунлая оболочка трех точек, не лежащих на одной прямой, †треугольн. В общем случае выпуклая оболочка конечного числа точек на плоскости образует выпуклый многоугольник, а в пространстве — выпуклый многогранник.
Определение 9. Выпуклая оболочка множества точек ио, ис,..., и из В«таких, что система векторов (и,. — ио, с = 1,..., сп) линейно независима, называется симплексом, натянутым на эти точки, и обозначается через В = В (ио,ис,..., и ). Точки ио, ис,..., и называются гершинами симплекса. В случае т = 0,1,2,3 симплекс представляет собой соответственно точку, отрезок, треу- гольник, тетраэдр. Согласно теореме 6 симплекс В представим в виде В,„=(и!и= Л оси!,ас>0,«=О,...,га, Л а!=1). с=о с=о По теореме 6 любая точка выпуклой оболочки множества Х является выпуклой комбинацн.
ей конечного, но, быть может, довольно большого числа точек из Х. Замечательно, однако, то, что в В" для получения множества со Х достаточно ограничиться рассмотрением выпуклых комбинаций не более чем и 4 1 точек из Х. Точнее, верна Теорема 7 (Каратеодорн). Пусть Х вЂ” произвольное непустое множество из а", Тогда любая точка и е со Х представила в виде гыпуклой комбинации не более чем и+ 1 точек из Х, Доказательство.
Согласно теореме 6 любая точка и 6 соХ представима в виде и= =оси!+...+а„,и, где ис еХ, ас >О, с =!,...,т, ас+...+а,=1. Пусть т>а+1 и все а! > 0 (если а; =О, то число гсс может быть уменьшено). В и+ 1-мерном пространстве рассмотрим векторы йс = (и„1), с = 1,..., и!. Поскольку гп > и+ 1, то эти векторы линейно зависимы, т. е. существуют числа т!,..., Тт, не все равные нулю и такие, что тгй! +... ... + т й = О. Это равенство эквивалентно следующим двум равенствам: у!и!+... 4 гти =О, ус+...4 ум =О.
Тогда точка и представима другими выпуклыми комбинациями тех же точек ис,..., и «с с« А,'(а! — !ус)ис= А,' аси! — 2 У!и!=и. В самом деле, здесь а!>0 и, следовательно, ас-.йгг >О, =! ;=! с=! «««с « =1,...,гп при всех достаточно малых с и, кроме того, л, (а; — !Тг)= л сх! — ! г 7! =1 — с=! с=! Поскольку не все т! равны нулю, но а!+...+ у =О, то среди (сй) найдутся положительные. 156 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА 1 $1.
ВЫПУКЛЫЕ МНОЖЕСТВА 157 Пусть а,т, ! = ш!и а! т! '. Положим ! = а, т, !. При таком выборе ! все а! — тгй останутся г,>о неотрицательными, причем а, — ст, = О. Это значит, что точку и удэлось представить в виде выпуклой комбинации меньшего числа точек и!,...,и, !,и, „!,...,и . Ясна, что последова- тельно применяя описанный прием далее, число точек, участвующих в выпуклой комбинации, можно уменьшить до и 41, С! Теорема 8.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
