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