Ф.П. Васильев - Методы оптимизации (1125241), страница 46
Текст из файла (страница 46)
юЕ!п1 Х и !п1 ХфИ. >З 5. Выпуклое множество Х = (и =(х«у, г) Е Ез: х + уз < 1, в = О), представляющее собой единичный круг в плоскости Г = (и =(х у г) Е Е: г = О), не имеет внутренних точек. Кстати, 3. здесь плоскость Г представляет собой зффинную оболочку множества Х. В та же время, если это множество Х рассматривать лишь относительно плоскости Г (т. е не «признавать« точки ЕЗ, лежащие вне Г), то Х вЂ” единичный круг — конечна же, имеет внутренние точки. Приводимая ниже теорема 1! показывает, что эго не случайно.
Для ее формулировки нзм понадобится Определение 10. Точка и ЕХ называется атноситально внутренней точкой множества Х, если существует г-окрестность О(и, г) = (и Е Е'! (и — и) < г) точки а такая, что пересечение О(и, г) П аЛ Х целиком принадлежит Х. Множество всех отйасительио внутренних точек множества Х обозначается через п' Х (иногда обозначают гейп1 Х).
Например, если Х = (и = (х«у«з) е Е~! х + уз < 1, х = О), то «1Х = (и =(х«у«г) е Е; 3. '+у <1, =О). Если множество Х С Еи имеет размерность п, т. е. Йпп аЛХ = и, то понятия внутренней и относительно внутренней точки для множества Х совпадают и г! Х = 1п1 Х, Нетрудно указать множества Х (например, ином«ество, состоящие из двух различных точек Е ), у которых г! Х = >с>. Однако для выпуклых множеств верна Теорема 11, Если Х нгпустог гыпукгог множество из Е", то п Х непусто, выпукло. пры этом селии е н х, ие х, то а„= и+а(ио — и) е г! х лри всех а, 0< а < 1. Если иепХ, уйпИ, уеХ, тоюй — — иЕЛ(у — и)ЕХ лривсехЛ>1. До к а ветел ь ство.
Можем считать, что точка ОеХ, так как в противном случае вместо множества Х мы рассмотрели бы множество Х вЂ” (и) = (ю ЕЕ"; ю = и — и, и Е,Х), где и— какая-либо точка из Х. Тогда 0 Е аВ И = Ып Х вЂ” подпространство в Еи. Пусть множество Х имеет размерность й!ш Х = т, 1 < т < и, (в случае т = О, когда Х состоит из единственной точки, утверждения теоремы тривиальны; случай т = и рассмотрен в теоремах 3, 4, 10). Тогда найдУтсн такие тачки иа, и>,.. ии ЕХ, что вектоРы е! — — и! — ио, .. и ею=и, — па линейно независимы и образуют базйс а(1 Л.
Ма>кис дополнить систему е>,, ст векторами с + „... ..., еи до базиса Е", причем можно считать, что (еч, с ) = О, « = 1,..., т, т' = т+ 1, .. и и. В этом базисе аКХ = (и = (и>,, ии) Е Е" ! ит+ = (е,„+ >, и) = О, .. и и" = (си, ы) = О) = =(и = (х, их+ ! =О, ..
и ив =О): хе Е~), так что аЕХ можно отождествить с пространством 159 $1. ВЫПУКЛЫЕ МНОЖЕСТВА 158 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА Е". Повторив в этом пространстве соответствующие рассуждения из доказательств теорем 3, 4, 10, убеждаемся в справедливости утверждений доказываемой теоремы. П Теорема 12. Пусть Х вЂ” яаяустое выпуклое множество из Е' и ус Х, у 4 г! Х. Тогда существует последовательность (уь), уь 4 Х, уь е айХ, )с = 1, 2,, сходящаяся к у.
Доказательство. Возьмем какую-либо точку и е г1Х. Согласно теореме !1 тогда тх — — и ! Л(у — и) 4 Х при всех Л > 1. Кроме того, поскольку ай Х = аН Х, то и у е аН Х и, следовательно, ю„е аНХ. Тогда уь — — юх —— н+ Ль(у — м), где Ль > 1, (Ль)-ч 1, — искомая последовательность, П Заметим, что если множество Х не является выпуклым, то утверждение теоремы 12 может оказаться неверным. Например, пусть Х вЂ” множество точек на числовой оси Е, имеющих ! рациональные координаты. Тогда аНХ = Ег,' и любая точка уе Е является граничной для Х.
! Таким образом, Х = Е ', и последовательности (уь) 4 Х, сходящейся к у здесь не существует. Теорема 13. Пусть Х вЂ” выпуклое множество из Е". Тогда и Х =г1 Х, Й= г! Х. До к аз а тел ьство. Возьмем лгобую точку е е г!Х. Согласно определению 1О тогда существует такое з > О, что О(о, э) паНХ = О(е, э) паН Х с Х с Х. Это значит, что о е и Х, Следовательно, г! Х с и Х. Докажем обратное включение. Возьмем т е г! Х. Тогда существует такое а >О, что О(ю, з) ггаНХ с Х.
Воаьмем какую либо точку о Е г! Х и положим яэ — — ю+ Л(ю — о), Л Е К, Поскольку о ю Е е аН Х = аНХ, то юх е аН Х при всех Л е и. Кроме того, существует такое Ло > О, что юх е Е О(т, з) длЯ всех Л, ]Л] < Ло. Следовательно, юл Е О(ю, а)ГэаНХ СХ, ]Л] < Ло. Из выРажениЯ длЯ Яь следУет, что т = ел+ — — т(о-юл). пРи 0 < л < ло имеем о = 1+ е(0, 1). согласно Л Г+ Х теореме 11 тогда и е г! Х. Это значит, что и' Х с г! Х. Тем самым установлено, что и' Х = г) Х.
Далее, так как г! Х с Х, то г1 Х с Х, Возьмем любую точку и е Х и о е и' Х. По теореме 11 и = и+о(о — о) си'Х при всех о е(0, 1], причем оо — ьн при о-чо, Следовательно, мейХ. Это значит, что Х С йХ. Таким образом, показано, что Х = г! Х. О Некоторые другие свойства выпуклых множеств будут рассмотрены ниже, Упражнения 1. Пусть Х вЂ” некоторое множество из Е", Х вЂ” замыкание множества Х. Если Х выпукло, то можно ли утверждать, что Х также выпукло) 2.
Существует ли невыпуклое множество, удалив из которого одну точку (или несколько точек), могкно получить выпуклое множествоу Рассмотреть пример Х = (м = (щ у) е Е: х > 3. > О, у > О, х+ у < !) О ((О, !)) О ((1, О)). 3. Показать, что равенство и' Х = и'Х для невыпуклых множеств, вообще говоря, неверно (рассмотреть круг с выколотым центром). 4. Доказать, что если А с В, то А сВ, 'ш1 А с1п1 В, но, вообще говоря, не будет включения г) А с и' В даже яля выпуклых А и В, Рассмотреть пример  — куб в Е, А — одна из его э граней. 6.
Если А — выпуклое множество из Е", то аНА = аН(и' А). Доказать, 6. Доказать, что размерность выпуклого множества Х совпадает с максимальной размер- ностью симплексов, содержащихся в Х. 7. Если А,  — выпуклые множества из Е", то А+ В с А + В, и' А + г! В = п(А+ В), г!(ЛА) = Л и' А для любых действительных чисел Л. Доказать. 6, Доказать, что если А,  — выпуклые множества из Е", и' А и г1 В ф яг, то и' А г! г1 В = = п(А гг В).
Существенно ли здесь требование и' А и г! В ф гз]? Рассмотреть пример А = (о =- =(х у)еЕ: х>0), В=(н=(х у)е Е,' х<0). 6. Если Х вЂ” открытое множество, то со Х открыто. Доказать. 1О. Доказать, что со(А + В) = со А + со В. 11. Доказать, что со Х =соХ, где соХ вЂ” пересечение всех выпуклых замкнутых множеств, содергкащих Х. 12, Доказать, что вершины оо, нг,, и т-мерного симплекса Я„, = Ят(оо, мг,..., и ) явля!отса его угловыми точками (см.
апреле™ленив 9, 3.2.1). 13. Доказать, что аффинная оболочка многкества Х состоит из точек вида о!нг+...+о м при всевозможных нг,, м е Х, о! — действительные числа, г = 1,..., т, ог+...Чо =1, и только из них. 14. Пусть А,  — выпуклые замкнутые множества из Е", причем хотя бы одно иэ них ограничено. Доказать, что тогда А +  — выпуклое замкнутое множество. Будет ли А + В замкнутым, если А, В не ограниченыу Рассмотреть примеры! а) А=(а=(х у)сеэ: у=о), В=(ь=(х у)ее ! уае ); б) многкества А, В из рис. 4.14; в)А=(а=(хух)еЕ:х=з=оу4(0),В=(Ь=(х,уэ)еЕ !х +у <2уэу>0).
Э 2. Выпуклые функции 1. В главе 1 были рассмотрены некоторые свойства выпуклых функций одной переменной. Здесь мы продолжим изучение свойств выпуклых функций многих переменных, Определение 1, Функция е(ш), определенная на выпуклом множестве Х, называется выпуклой на атом множестве, если е(аи+(1 — а)и) < ау(и)+(1 — а))(и) при всех и, и Е Х, всех а, О < а < 1. Если в (1) при и ф и равенство возможно только при а =О и а =1, то функция Е(ю) называется строго выпуклой на Х. Функцию Е'(ш) называют вогнутой (строго вогнутой1 на выпуклом множестве Х, если ( — у(ю)) выпукла (строго выпукла) на Х, Если множество Х пусто или состоит из одной точки, то функцию на таком множестве нам будет удобно считать выпуклой (или вогнутой) по определению.
Подчеркнем также, что всюду, если не оговорено противное, будем рассматривать лишь функции, принимающие конечные значения во всех точках области опуеделения. Примерами выпуклои функции на всем пространстве Ю" служат линейная функция е'(ю) = (с, х) и норма е(х) = ]ю], Кстати, линейная функция е(ю) = (с, ю) одновременно является и вогнутой на Е '. В теореме 1.5 было показано, что выпуклое множество Х содержит выя ь пУклые комбинации 2 а!и!, сг! > О, э =1,..., гп, 2; аг =1, любых своих '=! =! точек и„..., и„при любых иь = 2, 3,... Пользуясь индукцией по той же схеме, какая бйла использована при доказательстве теоремы 1.5, нетрудно показать, что для любой выпуклои функции Е'(ю) на выпуклом множестве имеет место неравенство 14енсена )'(~ аью,.) < ~ а,.У(ю,.) (2) длялюбых иьж1,2,...,любых к!аХ, аг>0, з=1!...,гп, 2 а!=1.
г=! 2. Как и в случае выпуклых функций одной переменной, выпуклые функции многих переменных на выпуклом множестве не могут иметь локальных минимумов. Точнее, верна Теорема 1. Лусть Х вЂ” вьтуклое множество, а функ!(ия Е"(х) определена и выпукла на Х. Тогда всякая точка локального минимума 160 Гк 4. ЭЛЕМЕНТЫ ВЪ|ПУКЛОГО АНАЛИЗА Г(х) одновременно является точкой ге глобального минимума на Х, причем множество Х„=(х: х Е Х,Г"(х) =7'„= !и! Г(и)) вьспукло.
Если Г(х) строго выпукла на Х, то Х„содержит нг более одной точки. Д о к а з а т е л ь с т в о. Пусть и, — точка локального минимума функции У(х) на множестве Х. Это значит, что существует окрестность О(и„, г) = = (и: [и — и„~ < г) точки и, такая, что Г(и,) < 7(е) для всех е Е О(и., г) П П Х. Возьмем произвольную точку х Е Х и число сг > О, столь малое, что а[х — и,[ < г. Тогда и. + сг(х — и„) е О(и„, г) Г| Х, и с учетом выпуклости 0 .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
