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