Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 59
Текст из файла (страница 59)
Доказать, что Х имеет хотя бы одну угловую точку тогда и только тогда, когда Х не содержит прямых. 8. Докаэатьч что выпуклое замкнутое ограниченное множество А из Е" является выпуклой оболочкой своих угловых точек. Показать, что без требования ограниченности множества А э. это утверждение неверно. Рассмотреть пример А =(о=(х, у) си: у >]х]).
9. Если А!, .. ч А — выпуклые множества из и", причем (] пА! ~ Я, то П А! = ч=! ! ! = П Ач; п( П А!) = Й (г! А!); ан( П А!) = Д (а1!А,.). Доказать. ч=! ! ! ч=! ч=! ч=! 10. Пусть К вЂ” произвольный конус из Е". Доказать, что тогда конус К' будет замкнутым и выпуклым, 11. Доказать, что если К вЂ” выпуклый конус, то конусы К, и'К также выпуклы и К' = =(К) =(г!К)1. 12.
Доказать, что если К вЂ” замкнутый выпуклый конус, то (К*)' = К. 13. Пусть К вЂ” выпуклый конус. Доказать, что для ограниченности снизу линейной функции (с, и) на К необходимо и достаточно, чтобы с е К*. 14. Пусть К вЂ” выпуклый конус, !п1 К ~ Я. Тогда (с, и) > 0 для всех м е !п! К при любом выборе с е К* (с Ф 0). Доказать. 15. Докаэатчч что если К, .. ч К выпуклые конусы, то К = К! +... + К вЂ” выпуклый конус, причем К = со(К! ы?ьэ!1...оК ). Мох<но ли утверждать, что еслибы'„...,К выпуклые замкнутые конусы, то К вЂ” выйуклый замкнутый конус? (см, упражнение 1.!4, в)). 16. Доказать, что (К! 4... + К )* = К!'й...й Л", где К!,..., К вЂ” конусы из Е", 17.
Пусть Кп Кз — выпуклые замкнутые конусы. Доказать, что (К, й Кэ)* = К,*+ К*. 18. Пусть Ко, К!,..., К, — выпуклые конусы, пусть Кой!и! Л"! й... й1п! К,„~ И. Тогда ( *=" !] К!) =Ко+К!*Ч-...+К'. Доказать. г=о т 19. Пусть Ко, К!, .. ч Л' — выпуклые конусы.
Тогда либо ( П К ) = Ко -! К!' ч-... ч- К*, =-о либо существуют ие все равные нулю векторы с е Л;*, ! = О,..., гн, такие, что со+ с +... ...+ с„= О. Доказать. ! 20. Для того чтобы выпуклые конусы Ло, К! были неотделимы, необходимо и достаточно, чтобы 0 е !и! (Ко — К!). Доказать. 21. Доказать, что даа выпуклых конуса Ко, К! неотделимы тогда и только тогда, когда одновременно выполнены два условия: и' Кой!! К! Ф И, 1.'ш Ко+ Ни К = Е". ! 22.
Для того, чтобы два непустых выпуклых множества А, В из Е" были сильно отделимы, необходимо н достаточно, чтобы 0 (1 А-В. Доказать. 23. Доказать, что два непересекающихся многогранных множества сильно отделимы. 24. Множество А* = (с с Е"; (с, и) < 1 Чи е А) называется полярой множества А. Найти поляры множеств А, если А = (0); А = (о Ь] с Е'; А =(о е и": н = се, 0 < с < оо, е ~ 0); А = (н е Е"; (с, и) < т); А — шар; А — конус с вершиной в нуле. Выяснить связь между полярой конуса и двойственным конусом. мм 6.
Субградиент. Субдифференциал 1. Дпя выпуклых дифференцируемых функций на выпуклом множестве выше было доказано неравенство (см. теорему 2.2) 7(и) ) 7'(и) + (7"(и), и — и) чуи Е Х. (1) К сожалению, выпуклая функция может не быть дифференцируемой даже во внутренних точках множества, и в этом случае полезное во многих случаях неравенство (1) не будет иметь смысла. Тем не менее, оказывается, для выпуклых функций это неравенство можно сохранить, если надлежащим образом обобщить понятие градиента, Определение 1. Пусть функция у(х) определена на множестве Х из Е'.
Вектор с = с(и) е Е' называется субградиентом функции 7'(ю) в точке и Е Х, если Г'(и) ) Г'(и)+(с(и), и — и) Чи ЕХ. (2) Множество всех субградиентов функции 7"(х) точке и называют субдифференг(и- алом этой функции в точке и и обозначают через ду(и). Неравенство (2) имеет простой геометрический смысл и означает, что график функции Т= ](и),иеХ в пространстве переменных (и, 7) лежит не ниже графика линейной функции Т=]'(и)+(с(и), и — и), Рис.
4.!8 и е Х, причем в точке и=и оба графика пересекаются (рис. 4.18). Для гладких выпуклых функций, как показывает неравенство (1), суб- дифференциал непуст и градиенты этих функций являются их субградиен- $ 6. СУВГРАДИЕНТ. СУВДИФФЕРЕНЦИАЛ 199' Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА тами. Во внутренних то«)ках множества гладкая функция, оказывается, дру- гих субградиентов, .кроме градиента, иметь не может.
В самом деле,,пусть е Е !и! Х, с(е) Е д1(е). Поскольку «/(и) Е С(Х), то Ци) = /(е)+ (1(е), и— — е) *и(]и — е]), и Е Х. Отсюда,и из (2) следует, что '(ТО(е) — с(е), и — е) > > о(]и — е]), и,Е Х. Поскоиьку еяЕ )п! Х, то и = е — г(/'(е) — с(е)) Е Х при всех е,'О< е с з,. Подставив эту точку в предыдущее неравенство получим — к] / (е) — с(е)]х > о(е), 0 < к < во. Деля на с > 0 и устремляя е —.«+О, отсюда будем иметь — ]11«(е) — с(е)]х > О, т.
е. с(е) = /"(е). Тем самым показано, что для гладкой выпуклой функции д1(е) = Т/',(е)) при воех е Е !и! Х. Существуют функции, которые недифференцируемы в точке, но тем не менее субдифференциал в этой точке непуст. П р и м е р 1. 'Функция «Г(и«)=]д(и)], иеХ в точке е, где д(е)сиО, всегда имеет субградиент с(е) = О, так как ]д(и)] — ]д(е)] = ]д(и)] > О = (О, и — е) для всех и е Х. |В то же в))емя в точках е, где д(е) фО, эта функция может быть недифференцируемои и не имеющей субградиента.
Пример .2.,Пусть /(и) = !и], и е Е". В точке и=О эта функция недифференцнруема, но для нее верно соотношение ,Г(и) — Г(0) = ]и! > (с, и — 0) = (с, и), и Е Е для всех с, ]с! <'1.'Это значит, что д(]и))~ = д/'(О) = (с Е Е": !с] > 1)— )ь=о единичный шар с центром в нуле. Если е фО, то О/(е) = (е/]е] =/'(т))). Заметим, что в примере 2 функция /(и) =]и! выпукла на .Е". Оказы- вается, если совсем отказатьея,от выпуклости функции, то даже гладкая функция может;не иметь субградиента ни в одной точке.
Например, для функции 1(и)-= и' на Е' субдифференциал пуст во всех точках, В то же время эта функция /(и) = и' на множестве Х = (и е Е'. и > О) выпукла и во всех точках,е е Х имеет на Х непустой субдифференциал. Ниже увидим, нто это не случайно. 2. Следующая;теорема показывает, что понятия субградиента и субдифференциала являют- ся естественными для выпуклых функций.
Те о р е м а 1. Пусть Х открь«тое выпуклое множество на Е" (например, возможно, Х шЕ" ). Тогда для того чтобы функция /(х), определенная на Х, имела непустой субдифференциал во всех точках Х, необходимо и достаточно, чтобы /(х) была выпукла на множестве Х. Доказательство. Необходимость. Пустьдля некоторой функции/(х) субдифференциал д/(и) уг й) при всех и е Х. Покажем, что /(х) выпукла на Х. Возьмем произвольные и, о е Х, а е [О, 1] и положим и„= пи 4(1 — а)о.
Пусть с = с(и ) е д/(и„). Тогда /(ц) — /(Ч ') > (с, и — и ), /(е) — /(и„) > (с, о — и ). Умножим первое из зтих нерзвенств на а, второе на 1 — а и ело«ким. Получим а/(и) + + (1 — а)/(о) — /(и ) >'(с, и — и ) = 0 при всех и, о е Х, а а [О,!], Выпуклость /(х) на Х доказана, Достаточность.
Пусть/(х) выпукла на открытом выпуклом множестве Х. Пусть хв произвольная точка на Х. Покажем, что д/(а) я'к). Возьмем некоторый единичный вектор е, ПосколькУ Х вЂ” откРытое множество, то и-Ь Се Е Х пРи всех г, 0< г < то, ~ > О. По теоРеме 2.14 существует производная д/(о)/де по направлению е. В пространстве Е"+ переменных (и, т) введем два множества А =((и, у) е Е" "; и еХ, у >/(и)), В =((и, т) ЕЕ" ', и = о+ 1е, т =/(е)+ с+), 0д (1 < гс). Нетрудно показать, что множество А выпукло — зто делается так же, как доказывалась выпуклость'надгрзфика, выпуклой функции в теореме 2В (кстати, в данном случае А =)п1 (ер« /)). Множества В является отрезком прямой в* Е" ~ ' и тоже выпукло.
Покажем; что множества А и В не имеют общих точек. В самом деле, пусть (и, у) е А.. Имеются две возможности: 1) и ф'о,+ ге при всех г, О ( г < < го — тогда заведомо (и, т) б В; 2) при некотором 1, 0 ( г < го, оказалось, что и = о+ сев тогда а учетом неравенства (1 8 4) и т > /(и)«= /(о«+ ге) имеем у — д(о)»я(а и ге) — я(о)» ) гдй(Ь)/де, т: е. у > /(о)+ гну(ф)/де, и снова (и, у) ф В. Итак, множества А и В выпуклы, А г) В = )3), По теореме 5.2 тогда существует гиперплоскость с нормальным вектором (д, и) г«О, отделяющая А и В, т. е.
()й и) -)- иу > (д, а+ ге)-)- и1/(и)+ 1- д(=)/« (3) пРи всех т >У(и), и ЕХ, 0(1( го. В частности, пРи и= о, 1=0 ив«(З) имеем и(У вЂ” /(о)) ) 0 для всех,.у > /(х) Отсюда следует, что и > О. ДЬпУстим, что и = 0«Тогда из (3)' имеем (д, и) > (д, х т те) длЯ всех и Е Х, 0 <, т( го. ПЬложим здесь и = о + а1, С = 0 — так можно делать, ибо е ц гй Е Х пРи всех г, 0 < ]г]'< ео в силУ откРытости Х.
ПолУчим (д«о+ сд) > (д„о), или е]д]х ) 0 пРи всех г, 0 <]с] <'ео, что возможно только при й = О. Однако (д, и) я'0 по построению. Полученное противоречие показывает, что и = 0 не может быть. Итак, и > О. Поделим (3) на и > О. Обозначая с = -д/и и устремляя т -« /(и)гй О, из. (3) получаем /(и) — /(о) + 1(с, е) ) (с,и — о) + 1 + (4) ПРИ ВСЕХ и Е Х И ВСЕХ 0)< 1 < га, Папатаа ЗДЕСЬ 1 = О, бУДЕМ ИМЕТЬ /(и) — /(а) > (с, и — х) Уи е Х.
это означает, что с а д/(о), т. е. д/(о) т' е). и В следующей теореме изучаются некоторые свойства субдифференциалз выпуклой функции. Те о ре ма 2. Пусть Х вЂ” открытое вь«пуклое множество из Е"'(напримвр, Х=Е"), /(х) — вьтуклая функция на Х. Тогда субдифференциал д/(е) при всех а е Х является неп сть«м выпукль«м, замкнутым и ограниченным множеством. о к а з а т ел ь с т в о. Непустота субдифференциала доказана в.теореме 1, Покажем:выпуклость д/(о)..Пусть с), с е д/(х), т, е. /(и) — /(х) ) (с),и — е), /(и) — /(о) ) (сг,и — а), и Е Х Возьмем а е 10, 1]. Умножая первое неравенство на а, второе на 1 — а и, складывая, получаем /(и) — /(и) > (ас) + (1 — а)сг, и — о) при всех и е Х.
Это значит, чтшао)«*(1 — а)сз е д/(х) для л)обых а е !О, 1). Выпуклость д/(о) доказана. пУсть с — пРедельнаЯ точна мно«кества д/(о), пУсть (сь) с д/(Р) и оь — «с пРи ь -«оо, из сь яд/(о) следует, что/(и) — /(о)) (сь, и-о) «/ие Х. При Ь вЂ” «оо отсюда получим сед/(а). Замкнутость д/(о) доказана. Покажем ограниченность д/(а).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
