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