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