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