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