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