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