Ф.П. Васильев - Методы оптимизации (1125241), страница 59
Текст из файла (страница 59)
Доказать, что если К вЂ” замкнутый выпуклый конус, то (К ) = 13. Пусть К вЂ” выпуклый конус, Доказать, что для ограниченности снизу линейной функции (с,и) на К необходимо и достаточно, чтобы с а К". 14. Пусть К вЂ” выпуклый конус, !и! К ф И. Тогда (ц и) >0 для всех и е !п! К при любом выборе с й К* (с ~ 0). Доказать 15. Доказать, что если К,..., К выпуклые конусы, то К = К! +... + К вЂ” выпуклый ичем К = со(К О гь О...ОК ). Можно ли утверждать, что если „...,К выпуклые замкнутые конусы, то К вЂ” выпуклый замкнутый конус (см. упраж ., )). пение 1 14 в 16. Доказать, что (К!+... + К )* = К!*г!... П К,*„, где К!,..., К вЂ” конусы из Е".
17. Пусть К!, Кэ — выпуклые замкнутые конусы. Доказать, что (К! г! Кз)* = К!*+ Кг'. 18. Пусть Ко, К„..., К вЂ” выпуклые конусы, пусть Ко О !п! К! г!... г! !п! К ф Я. Тогда ( П К, ) * = К! + К!' +... + К" . Доказать. «=о 19. Пусть Ко, К!,..., К вЂ” выпуклые конусы. Тогда либо ( П К ) = Ко + К;+...
4 К*, о либо существуют не все равные нулю векторы с; з К;*, !' = О,..., т, такие, что со+ с! +... +с 0 Доказать 20. Для того чтобы выпуклые конусы Ко, К! были неотделимы, необходимо и достаточно, чтобы 0 с 'ш! (Ко — К!), Доказать. 21. Доказать, что два выпуклых конуса Ко, К! неотделимы тогда и только тогда, когда одновременно выполнены двв условию г! Ко и г! К! ф Я, 1.!и Ко 4 (.ш К! — — Е", 22.
Для того, чтобы два непустых выпуклых множества А, В из Е" были сильно отделимы, необходимо и достаточно, чтобы 0 !( А — В Доказать, 23. Доказать, что два непересекающихся многогранных множества сильно отделимы 24. Множество А*=(с с Еь: (с, и) <1 то з А) называется лолярой множества Л. Найти поляры множеств А, если А = (0); А = (о Ь] с Е!! А = (и с Еч! и = ге, О < г < со, г рО)! А = (и е Е": (с, и) < т)! А — шар; А — конус с вершиной в нуле. Выяснить связь между полярой конуса и двойственным конусом.
ыд 6. Субградиент. Субдиффсренцнал 1. Для выпуклых дифференцируемых функций на выпуклом множестве выше было доказано неравенство (см. теорему 2.2) 7" (и) > Г" (е) + (7"'(е), и — е) !ги Е Х. (1) К сожалению, выпуклая функция может не быть дифференцируемой даже во внутренних точках множества, и в этом случае полезное во многих случаях неравенство (1) не будет иметь смысла.
Тем не менее, оказывается, для выпуклых функций это неравенство можно сохранить, если надлежащим образом обобщить понятие градиента. О и р е д е л е н и е 1. Пусть функция 7" (х) определена на множестве Х из Е". Вектор с = с(е) е Е" называется субградаентом функции 7'(х) в точке е е Х, если 7(и) ) 7" (е)+ (с(е), и — е) !ги е Х.
(2) Множество всех субградиентов функции 7(х) точке е называют субдифферен!(калом этой функции в точке е и обозначают через ду'(е). Неравенство (2) имеет простой геометрический смысл и означает, что график функцииТ=Т(и),иЕХв пространстве переменных (и, у) лежит не ниже графика линейной функции Т=~(е)+(с(е), и — е), и е Х, причем в точке и=е оба графика пересекаются (рис. 4.18). Для гладких выпуклых функций, как показывает неравенство (1), суб- дифференциал непуст и градиенты этих функций являются их субградиен- Ц 6, СУВГРАДИЕНТ.
СУБД)4ФФЕРЕНЦИАЛ 198 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА тами. Во внутренних точках множества гладкая функция, оказывается, других субградиентов, .кроме градиента, иметь не может. В самом деле, пусть е Е!и! Х, с(е) Е д/(е). Посколыку Яи) ЕС|(Х), то /(и) = /(е)+(/'(е), и— — е) *о(~и — е~), и е Х. Отсюда и из (2) следует, что (уч(е) — с(е)) а — е) > > о([и — е[), иЕ Х. Поскскыку еЕ[п! Х, то и =э — г(/'(е) — с(е)) ЕХ при всех г, '0< а < г .,Подставив эту точку в предыдущее неравенство получим — г~У(е) — с(е)Г> о(г), 0 < г < го. Деля на г >0 и устремляя г- +О, отсюда будем иметь — [,г((е) — с(е)[э > О, т. е. с(е) =1'(е).
Тем самым показано, что для гладкой выпуклой функции д/(е) = Т1',(е)) при всех е е |п! х. существуют функции, которые недифференцируемы в точке, но тем не менее субдифференциал в этой точке непуст. П р и м е р 1, Функция /(и) =[у(и)), и Е Х в точке е, где д(е) =О, всегда имеет субградиент с(е) = О, так как [д(и)/ — !д(е)) = [д(и)/ > 0 = (О, и — е) для всех и Е Х. 'В то же время.в точках е, где д(е) ~о, эта,функция может быть недифференцируемой и не имеющей субградиента. Прим~с,р 2.
Пусть /(и) = [и~, и ЕЕ". В точке э=О эта функция недифференцируема, но для нее верно соотношение /(и) — /1(0) = [и! > (с, и — 0) = (с, и), и Е Я", для всех с, !с) <'1.гЭто значит, что д([и))~ =д/(0)=(с ЕЕ": [с[> 1)в ~э=е единичный шар с центром в нуле. Если е фО, то д/(е) = (е/[е)=1'(е)у. Заметим, что:в приморе 2 функция 1(и) = [и! выпукла на Е'".
Сказывается, если совсем отказаться от выпуклости функции, то даже гладкая функция может:не иметь субградиента ни в одной точке. Например, для функции 1(и) = и' на Е' субдифференциал пуст во всех точках. В то же время эта функция /(и) = иэ на множестве Х = (и Е Е '. и > Оу выпукла и во всех точках,е ЕХ имеет на Х непустой субдифференциал. Ниже увидим, что это не случайно. 2. Следующая теорема показывает, что понятия субградиента и субдифференциала являются естественными для выпуклых функций.
Теорема 1. Пусть Х открытое выпуклое множгстао на Е" (напрамер, аоэмохгно, Х ы Е" ). Тогда длл того чтобы функция /(х), определенная на Х, имела непустоа субдифференциал го всех точках Х, необходимо а достато ~но, чтобы /(х) была выпукла на множестзг Х. Доказательство, Необходимость, Пусть для некоторой функции/(х) субдифференциал д/(и) ф к1 при всех и Е Х. Покажем, что /(х) выпукла на Х. Возьмем проиавольные и э е Х, а с [О, 11 и положим и„= хи+(1 — а)е.
Пусть с = с(и ) е д/(ич). Тогда /(и) — /(и ') > (с, и — и ), /(э) — /(и ) «(с,е — и ). Умнов<им первое из этих неравенств на а, второе на 1 — а и сэогким. Получим а/(и) + + (1 — а)/(е) — /(и ) > (с, и — и ) =0 при всех и, е е Х, а а[0, 11. Выпуклость /(х) на Х доказана, Достаточность. Пусть/(х) выпукла на открытом выпуклом множестве Х. Пусть ив произвольная точка на Х. Покажем, что В/(э) ф кг. Возьмем некоторый единичный вектор с.
ПОСКОЛЬКУ Х вЂ” ОтКРЫтОЕ МНО1иаетВО, та э+гс Е Х ПРИ ВСЕХ г, 0 < г Д <го, те >О. ПО ТЕОРЕМЕ 2 14 существует производная д/(э)/де по направлению е. В пространстве Е" ~ переменных (и, т) введем двв многкества А=((и,т)еЕ"; иеХ, т>/(и)), В = ((и, т) Е Е"+: и = е + ге, т = /(е) + г — (-), 0 < г < ге). Нетрудно показать, что множество А выпукло — это делается так же, как доказывалась выпуклость' надграфика, выпуклой функции в теореме 2.9 (кстати, в данном случае А =|п1 (ер[ /)) Множество В является отрезком прямой в.
Е" ~ ' и тоже выпукло. Покажем, что множества А и В не имеют общих точек, В самом деле, пусть (и, т) еА, Имеются две воэможности: 1) вы/э+ ге при всех г, О( г ( < го — тогда заведомо (и, т) к В; 2) пРи некотоРом г, 0 < ! < го, оказалось, что и = е+ сев тогда е уэстом неравенства(134) из >/(и)~=.Я(е+ ге) имеем т — л(е)»/1(е ж ге) — й(э) > > гдуу(э)/Ие, т,. е. т > 1(э) т Щ(У) /де, и снова (и, у) ф В. Итак, многкЕСтва А и В выпуклы, А гэ В = !Э. По теореме 5.2 тогда существует гиперпло- скость с нормальным вектором (д, и) т'О, отделяющая А и В, т.
е. (д,и)+ от > (гце+ гг)-~-и[/(э)-Ь г — д[ — ))' (3) пРи всех т >Р(и), и е х, 0 < г < го. В частности,.пРи и = е, г = 0 иа(5)~имеем э(т — /(е)) > 0 для всех у >/(ь) Отсюда следует, что э > О. ДопУстим, что э = О. Тогда иэ (3)' имеем (д, и) > (Д э+ ге) дла всех и Е Х, 0<. г'( го, Положим, здесь и = е + гд, С =.Π— так можно делать, ибо е + гд е Х при всех г, 0 < [г [>< г„ в силУ откРытости Х, ПолУчим (Де+ гд) > (а, э), или г[д)~ > 0 пРи всех г, 0 < [э[ <:го, что возможно только при д = О. Однако (д, и) я'0 по построению. Полученное противоречйе показывает, что э =0 не может быть. Итак, э > О. Поделим (3) на э > О.
Обозначая с = — д/э и устремляя т -~ /(и);.+О, иэ (3) получаем 1(и) — 1(э) + г (с, е) > (с, и — е) + г (4) при всех и е Х и всех О~д г < го, Полагая здесь 1 = О, будем иметь /(и) — /(е) > (с,и — е) тее Х Это означает, что с Е Вй(е), т. е. д/(э) я'Я. Г| В следующей теореме изучаются некоторые свойства субдифференциала выпуклой функции. Теорема 2.
ПустьХ вЂ” открытое гыпуклоемножгстго изЕ"'(например, Х=Е"), /(х) — гьспуклая функция на Х. Тогда субдэфференциал д/(э) пра всех е еХ является неп стым гыпуклым, замкнутым и ограниченным множеством. оказ атель ство. Непустота субдифференциала доказана а теореме 1. Покажем:вы. пуклость д/(э). Пусть с~, аг е д/(э), т, е.
/(и) — /(е) > (см и — е), /(и) — /(е) > (ог, и — е), и Е Х Возьмем а е [О, 11: Умножая первое неравенство на а, второе на 1 — а н, складывая„получаем /(и) — /(э) > (ас| + (1 — а)сэ, и — э) при всех и е Х.
Это значит, что~ао|св(! — а)сэ е д/(э) для любых а б [О, 1[, Выпуклость д/(э) доказана. Пусть с — предельная точка множества д/(э), пусть (сь) е В/(э) и сь -ч с при Ь -~ со, Из сь е д/(э) следует, что /(и)-/(е) > (сь, и - в) ти е Х. При Ь -~ со отсюда получим с и О/(э). Замкнутость д/(э) доказана. Покажем ограниченность д/(ьэ). Возьмем любой вектор с Е д/(э), Поскольку Х вЂ” открытое множество, то Я(э, г) =(и е Е:)и — е~ ( г) с Х при достаточно малом г > О.
Далее, в силу теорем 2 15 и 2 1 4 эцр /(и)=Г (Я) <со. Положим в неравенстве (2) и=э+ге/[с[ад(э, г). г|э, г) Получим /с [ < (/(э + гс/[с /) — /(э))/г < (/*(Я) — /(е)) /г < оо при асах:с е В/(е). П 3. Теоремы 1, 2 не дают конструктивного описания субдифференциала выпуклой функции. Такое описание удается получить лишь в немногих случаях. Пример 3. Пусть /(и) = шах и', и = (и',....и" ) е Е", 1 = (1,,, е и). Согласно теоре. гаг ме 2.7 функция /(и) выпукла на Е". Покажем, что д/(е) = (с = (сы..., с„): с, > О, ! е 1(е), с; = О, т ф 1(е); с! +...
Ч- с„= 1), (5) где 100 =(г е|: эрах ег = э|). Множество, определяемое правой частью формулы (5), обо- 1' е 1 значим через А (е). Пусть с е А(е). Умнож им неравенство /(и) — /(в);- шах иг - ег > ит — е', га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}
