Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 52
Текст из файла (страница 52)
1 214 ЗЛЕМЕНТЫ ВЬШУНЛОГО АНАЛИЗА тонно возрастает на Х, т, е, ф(х) ) ф(у) для всех х = (х», , хы), у — (у', ..., уы) аз Х, хг > у', » = 1, ..., т. Тогда У»ункция Ф(а) = »р(1(и)), выпукла на И' и ее субдиузудере»»циал имеет вид дФ(и) = 0 ~кд„редут (и), и Е И'. (1Ц р=(р,,, ..,Р»п) аетРМ) (1=1 Для доказательства этой теоремы нам понадобится Лемма 1, Пусть А», ..., Аы — вьтукль»е множества из Е", Р— вы»и ч» иуклое множество ив Еп, тогда м ножество А = () ~ ~~. Р1А1 а=(р» " Рт)ыр 1»=1 выпукло, Доказательство. Возьмем произвольные с», сеыА, аги (О, 1).
По определению А существуют такие ре = (рет, ..., Рстл)гиР с Е", аО е А. »и (1=1, ...,т), что се= ~~ рва»1 (»=1,2). Тогда ас +(1 — а)с 1=1 и» = ~ (ар )а . + (1 — ы) рз.а 1). По условию ргг ) О. Обозначим через 1 мно1=1 жество всех номеров 1 = 1, ..., т, для которых рм .м О или ргз ~ О. Тогда арП ар1+(1 — а)р >О, уа.— +(, ) =(О,1) 1~1. Положим ах = у„а . +(1 — уа.)а при 1 ж 1, ах= а при )за 1, В си лу выпуклости Аз точки а" принадлежит Ад (1 =1, ..., т). Кроме того, Р = (Рг " Ртг= арт+(1 — а) Р ж Р нз-за выпуклости Р,причем здесь Р =О при уты1. Тогда ыс +(1 — ы)с,= ~ (ар .а .-)-(1 — а)р .а»)= Х (арте+ П вЂ” и) Рз») (»ы(а»1 + (1 уи ) а .) = ~ рфаа = ~ рфа"., где бы 1 кнг 1=1 а~а А (1 = 1, ..., т), р ги Р.
Это значит, что ас + (1 — а)с~жА при всех а гн (О, 1), т. е. А — выпуклое множество. Доказательство теоремы 9. Из выпуклости функций 11(и), ф(х) и монотонности ф(х) следует выпуклость сложной функции Ф(и) = = ф(1(и) ) на открытом выпуклом множестве И' — это доказывается тзк же, как и теорема 2Е. Согласно теореме 2 тогда субдифференциал дФ(и) нри каждом и ж Ит представляет собой непустое выпуклое компактноо ьшо- жество. Докажем формулу (11). Обозначим р (и) = Ц ~~'» редут (и1 .
По оыеч<лиВ П=т ' ' ( теореме 2 субдифференциалы д11(и), дф(х) также непусты, выпуклы, ком- пактны н поэтому р(и) чьо (игн И'). Отметим„что дф(х) ел Е+ прп всех х гн Х. В самом деле, возьмем любые х = (х', ..., хы) гн Х, Р = (Р», Р ) ги ~ дф(х). Поскольку множество Х открыто, то при достаточно малом е ~ О точка у = (у', ..., у'"), где у' = хг — е, у» = х» при 1 Ф й принадлежит Х. с учетом монотонности ф(х) тогда О )»р(у) — »р(х) )(р, у — х) = рг( — з), так что рг > О (» = 1, ..., »а). Следовательно, д»р (х)»п Е'»Ы По лемме 1 тог- да множество Р(и) выпукло при каждом и»и И», Покажем, что Р=Р(и), как многозначпое отображение И'-ьП(Е"), полунепрерывно сверху.
Пусть и си Ит, (аь)-пи, (сь) -+с, сь жР(иь). Тогда суВГРАдиент. суВднФФеРенциАЕ 3 61 215 »я найдутся р»ж дф(1(иь)), ст ж дУ»(иь) такие, что е, = ~" р»ье»„. по»=1 скольку сходящаяся последовательность (из) ограпичена, то найдется компаятьое множество 6»: (/, содержащее все точки и, и», ит, ... Аналогично, поскольку в силу непрерывности выпуклых функций 1»(и) последовательность (хь = 1(иь) ) — 1(и) аз Х, то существует компактное множество У ш Х, содержащее все точки 1(и), У(и,), 1(и,), ... (можно взять У=У(6) = =1»(6) Х ° Х У,(6)). По теореме 5 множества дУ,(6), д»р(у) компактны. Поскольку см»н дУ»(и») с дУ»(6), рь»н д»р(1(иь)) щ д»р(у) (5 = 1, 2, ...), то не теряя общности можем считать, что (с»1)-ее», (рь)-~-р.
Из полунепрерывности сверху отображений ду»(и), д»р(х) имеем е»»н дУ» (и), р щ дф(У(и)). »з е» Переходя к пределу в равенстве се — — ~ Р»зг»д, ПОЛУчаем с = ~ р»сы т. е. »=1 » 1 «не" (и). Это значит, что отбражение Р полунепрерывно сверху. Возьмем любые и»н И' н сад(и). Тогда е= ~' р»с» при некоторых »=1 с»»н д1»(и), р = (Рь ..., р )»н дф(1(и)). Учитывая определение субградиента и неотрицательность р», получим Ф (г) — Ф (и) = »р (1 (е)) — »р (1 (и)) ) (р, У (г) — У (и)) =- = Х р»(1» (е) 1» (»»)) ееХ р» (с» е и) »=1 »=1 р»с», е — и = (с, и — и)»/е»и И Это значит, что с щ дФ(и) и, следовательно, Р(и)»= дФ(и) при всех и ж И'. Отсюда, пользуясь утверждениеи б) теоремы 8, заключаем, что дФ(и) = = У'(и) (и»н И'). Формула (11) доказана. С помощью теоремы 9 можно получить более сложные правила субдифференцирования, дополняющие приведенные выше правила 1 — 4.
Ниже прп ссылках на формулу (11) предполагается, что выполнены условия тео. ремы 9. б. Если»р(х) — дифференцируемая функция, то д»р(х) = (»р'(х)) = = ((д»р/дх», ..., дф/дх )), дф(У(и)) = (ф'(1(и))), и из формулы (11) имеем т дФ(»») = Ъ ф ( ( )) д1; (и), и»н И'. дх» »=1 В час»ности, если 1»(и) дифферепцируема и д1» (и) = (1» (и)), отсюда по- лучаем классическое правило дифферепцирования сложной функции. 7. Если ф(х)= ~',я;х (я»)О), то дф(х) =((аг, ..., я )) шН+ »=1 и для функции Ф(и) = ~и~~ я 11(и) (ищи') из (и) имеем дФ(и) = »=1 = ~~ я»д1,.
(и) (и»н И'), »=1 8. Если ф(х) = шах х, то согласно формуле (5) дф(х) = 1С»хт = (р = (рь, р,„): р» ) О, » ш 1(х); р» = О, 1 ф 1(х), р»+... + р = 1), ЭЛЕМЕНТЫ ВЬШУБЛОГО АНАЛИЗА 216 (гл. е где 1(х) =(1)1(1~(ю, шах х)=х)(хек Ем). Отсюда и из (11) для ьа) ля функции Ф(и) = шах 1)(и) имеем )л)лж дФ(и) =(о: с= ~ рве), о) ви д11(и), р)~~0, 1 он 1(1(и)), )ЫЛ т(а)) р)=1)=СО( () д1 (и)), 1(1(и)) = )ыдщаИ ) )еа цща)) =(1: 1~(1(ю, шах 1 (и) =11(и)), ищИт. (12) гагат 9. Если гр(х) =шах(0; х) (хвнЕ'), то согласно (12) ду(0) (с: с= = рг О+ рэ 1 = рг, рг+ рг= 1, рг ~>0, рэ)~0) [О, 1), дч(х) (1) прн х ) О, д~р(х) = (0) при х (О, и для функции Ф(и) = шах(0; 1(и)) (иен )Г) иа (11) имеем дФ(и) = рду(и) (0(р(1) при 1(и) = О, дФ(и) = д1(и) при 1(и) ж О, дФ(и) = 0 при 1(и) ( О.
10. Если гу(х) (шах(0; х))е (р ) 1, х виЮ), то д~р(х) = ($р(х) = = р(шах (О; х))в-') и для функции Ф(и) (шах (О; 1(и)))в (и ач И') имеем дФ(и) = р(шах(0; 1(и)))г-'д1(и), и он И', р > 1. 11. Приведем еще одну теорему, в которой дается обобщение формулы (12). Теорема 10. Пусть А — компактное множество ив Ен, Ит — открытое выпуклое множество иг Е, функция 0(и, а) определена на Ит >< А, полунвпргрывна сверху по а при каждом и еа УР, выпукла по переменной иш Ит при каждом аж А, Тогда функция Ф(и) = шахС(и, а) выпукла аыл на И' и вв суддиффгрвнциал имеет вид дФ(и) =со( () дП(и, а)), П (и) = (а: а вн А, С(и, а) = Ф(и)), иш И'. ~ аын(и) (13) Доказательство может быть проведено по той же схеме, как и теорема 9, и представляется читателю. 12. Если А — выпуклое замкнутое ограниченное множество иа Е", то функции Ф (и) = шах <а, и> (и гн Еп) выпукла на Е", причем, как сле- он А дует из (13), при 6(и, а) = <а, и> имеем дФ(и) = (а: а ш А, <а, и> = Ф(и)).
Более подробно о перечисленных и других правилах субдифференцировавия, о различных свойствах субдифференциала, о различных обобщениях понятий субградиепта и субдифференцнала, о применении этих понятий для исследования и приближенного решения экстремальных задач см., например [2, 15, 18, 21, 27, 123, 132, 133, 148, 156, 166, 195, 214, 219, 235, 255, 264, 306, 334].
Уп9 а ж н е ни я. 1. Найти субдифференцналы функций: а) 1(и~ = и — 1~ (и ш Е'); б) 1(и = и — 1 +(и+Ц (ишЕ'); в) 1(и) = )х+ у[+ )х — у[ (и = (х, у) шЕг); г) 1(и) =шах(й, и+2) (игнЕ'); д) 1(и) = шах()й); )и — 1)) (и шЕ'); е) 1(и) = )<а, а> — Ь! (и ш Е"). 2, Пусть функции 1г(и), ..., 1 (и) (и ш Е") непрерывно дифферевцируемы в некоторой окрестности точки о. Доказать, что тогда функция ,1 (и) шах 11 (и) в точке о имеет проиаводные по любому напраа. да)аж СРБРРАДИИИТ. СРВДИФФИРИИЦИАЛ 3 з) пению е ()е] = Ц, причем ("] = шах (1'(е), с), 1(е) =(1: 1<)я;и, 1 (е) =1(и)]. де ьи де) Установить связь между зтой формулой и формулами (7), (12).
3. Найти субдифференциалы функций 1 (и) = шах ] гз+ хз+ р ], 1(и) )Мг = шах ] х) + р)], 1 (и) = шах ) х+ зу ] (и = (х, р) еи Е ). )циг за)ат 4. Пусть А — замкнутое ограниченное множество иэ Еи, функция д(и, а) непрерывна по совокупности переменных (и, а) на Е" )(А вместе с производной дд(и, а)/ди. Докааить, что тогда функция 1 (и) = = шах д(и, а) во всех точках и ейЕ" имеет проиаводную по любому направ- аыА лению е, ] е) = 1, причем шах ', е, А (е) =(а: а ен А, д(е, а) = 1(и)].
г)1 (и) /ду (и, а) де а А1е) ~ ди о 'Установить свявь между этой формулой и формулами (7), (13). 5. Пусть У(и) — выпуклая функция одной переменной на отрезке [а, Ь]. Доказать, что д1(и) = [1'(и — 0), 1'(и+ОЦ при всех иш (а, Ь), где 1'(и — 0), 1'(и+О) — левая и правая производные в точке и. Покааать, что в точках и = а илн и = Ь субднфференциал может быть пустым (рассмотреть пример 1(и) = — 71 — иг() и] ( Ц).
6. Пусть 1(и) — выпуклая функция на выпуклом множестве УУ из Е". Доказать, что при всех и шп'(У множество д1(и) непусто, выпукло, компактно, причем = шах (с, е) для всех е ш]лп УУ. 31 (и) де сыиг(и) 7 П т функция 1(и) определена на открьпом выпуклом И'<= Е" и такова, что функция Ф(и) = ]1(ии выпукла на Иг. Описать множество дФ(и) (и ~и И'). 8. Описать субдифференциалы функций р(и, (У), б(с, (У), р(и, Щ из упражнений 18 — 20 к $4.2. 9. Пусть 1(и) — выпулая функция на открытом выпуклом множестве Иг иэ Е", пусть субдифференциал д1(и) в некоторой точке и ш И' состоит из единственного элемента с.
Доказать, что У(и) дифферевцируема в точке и, причем 1'(и) = с. 10. Пусть выпуклая функция 1(и) дифференцируема в каждой точке открытого выпуклого множества И'. Доказать, что ее градиент 1'(и) непрерывен на Иг. 11. Пусть 1(и), 6(и) — выпуклые функции на открытом выпуклом множестве ру из Е", причем дУ(и) = дб(и) при всех и ш дг. Доказать, что ~огда 1(и) = С(и) + сопзь (и ш И"). 12. Пусть функция 1(и) выпукла на открытом выпуклом множестве )р из Е". Доказать, что для того чтобы 1(и) была сильно выпуклой ва Иг, необходимо и достаточно, чтобы для каждой точки г ш Иг существовал субградиент с(е) еи д1(е) такой, что 1 (и) — 1(с]~ )(с(и), и — с) -)-к] и — е]э уи аи И', и =сонет) О. 13.
Пусть функция 1(и) сильно выпукла на открытом выпуклом множестве И' иа Е . Доказать: а) (с(и) — с(е), и — е>>2и]и — и)з для всех )Уи, иеиИ", с(и) ен еи д1(и), с(и) ш дУ(и); б) дУ(и) (] д1(и) = и для всех и, и ен И', и ~ с; элвминты выпуклого АнАлизА [ГЛ. 4 в) для любой точки и ы Иг справедливо неравенство ( и — е) ( ( — шш ) с ) для всех и ж М(с) = (и щ УУ: У(и) < У(с)). 1 х сжат[с] Опираясь на зто утверждение, доказать теорему 3.1 для любого выпуклого замкнутого мяожоства П а И". 14. Пусть функцяя У(и) выпукла ва открытом выпуклом множестве И'с Е" и сильно выпукла на выпуклом замкнутом подмволгестве П с И'. Доказать, что тотда б~(У(и) — Уе~ (— лив (с)~, ) и — и„(( — ш[в )с(, 4х сжали] 2х с ву(и] где ие — точка мяялмума У(и) ва [У, ӄ— — У [ие).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
