Ф.П. Васильев - Методы оптимизации (1125241), страница 60
Текст из файла (страница 60)
(5) |е1 |е1 201 6 6. СУВГРАДИЕНТ. СУВДИФФЕРЕНЦИАЛ 2ОО Гл. 4, ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА !! р-;: (с„и — и„)>0 ЧибХ (8) и,=угх(и« вЂ” ос,) )/и >О Возьмем в (6) и = ие —— (и! х 1,..., в" х Ц. Тогда /(ие) — /(е) = х! и из (6) получим х! > (с, ие — и) = х ~„сг, что воэмохгно лишь при 2" с; = 1. Далее, в (6) возьмем и, = г=! г=! =(и!,..., и"), где и! =в! — е при некотором ! 6 Х, и! = о! при Х~«, г>0.
Тогда /(и«)(/(о) и из (6) получим 0 ) (с, и, — и) = сэ(-е), так что с; ) О, ! = 1,..., и, Далее, пусть ( б Х(с). Тогда и! </(е) и можно выбрать г > 0 так, что и!+а < /(и), Положим и, = (и',..., и"), где иг = и' 4 г, и! = е/ при /' Н' !. Тогда /(«) = /(и,), и из (6) получим 0 > (с и, — о) = гсэ, т. е. с,. (О, ! э Х(и). Сравнивая это неравенство с уже доказанным с! > О, получаем сг = О, ! ф Х(«), Это значит, что с 6 А(в), так что д/(и) с А(е). Равенство (5) установлено.
4. Установим связь между производными по направлени!о и субдифференциалом выпуклой функции. Теорема 3 Пусть Х вЂ” открытое выпуклое множество иэ Е", /(х) — гь!лукаса функция на Х. Тогда го всех точках «6 Х лроиэгодная функции/(х) по любому налраг- лению г, [с[=1, сущестгует, примем — шах (с, е). (7) е г/(«) Доказательство. Существование производной д/(и)/де установлено в теореме 2.14. Докажем формулу (7).
Из (2) имеем (/(«+ (е) — Х(е))/г ) (с, е) при всех с е д/(и) и всех достаточно малых ( > О. Ото!ода при ( -«+О получим д/(в)/де ) (с, е) для любого с 6 д/(о), так что д/(е)/де ~ )зпр (с, е). С другой стороны, при доказательстве теоремы'! был построен «е г/(«) специальный субградиент с, для которого выполняется неравенство (4). Полагая в (4) и = о, будем иметь д/(и)/де ( (с, е), с 6 д/(в), Сравнивая это неравенство с предыдущим, приходим к формуле (7). Попутно показали, что максимум в правон части (7) достигается именно на том субградиенте, который был построен в теореме 1. П Формула (7) обобщает известную формулу д/(е)/дг = (/'(в), е) для гладких функций.
5. С помощью субдифференциала можно сформулировать критерий оптимальности, обоб- щающий теорему 2.3 на случай негладких выпуклых функций. Теорема 4, Пусть/(х) — выпуклая функция на открытом гылуклом множестве И' иэ Е", Х вЂ” гыпуклое лодмножестго множестаа И', Тогда для того чтобы функция /(х) достигала сгоеа нижней грани на множестге Х г точке и„б Х, необходимо и достаточно, чтобы сущестгогал субградиеат с, = с(и,) а д/(и,) такой, что Если и, 6 )п( Х, то г (8) с, = О, Необходим ость.
Пуст~ и, а Х, =(и 6 Х; /(и)=!и(/(и) =/, > — оо). Так как /(х) х выпукла на открытом выпуклом множестве И', то по теореме 2.14 существует производная д/(и«) — 3 — "- по всем направлениям е = (и — и«Ии — и,[, и 6 Х, и фи,, Согласно теореме 2.12 -! йО. Отсюда и из формулы (7) следует: — 3-л — = шах (с, е) йО. Возьмемус«бд/(и,), , д/('и.) де е а е г/(«,) для которого гпах (с, с) = (с„е).
Тогда (с„, е) = (с„и — и,)[и — и,[ ) 0 !/и 6 Х, и ~ и„, «е г/(«,) откуда вытекает неравенство (8), Если и„ 6 )п( Х, то и = и, + гс« б Х при всех г, 0 < ~г[ < гс, и из (8) получим (с„, гс,) = = г[с [ РО, 0 < !г) < го, Это возможно лишь при с, =О, Достаточность. Пусть для некоторой точки и, ЕХ выполнено неравенство (8) при каком-либо с„б д/(и,), По определению субградиента тогда /(и) — /(и„) ) (с„и — и„) ) 0 при всехибХ,т.
е, и,бХ,.О 3 а м е ч з н и е 1. Вариационное неравенство (8) можно записать в эквивалентном виде: Доказательство этого равенства проводится совершенно также, как и теоремы 4.4,4, и предоставляется читателю. Следующие примеры показывают, что субградиент с, иэ (8) в общем случае определяется неоднозначно, П р и м е р 4, Пусть /(и) = [и[, и 6 И' = Е'. Если Х = Е!, то Х, = (0), д/(0) = [-1, Ц и неравенство (8) выполняется лишь при с, =О. Если Х =(и а Е; и РО), то Х, = [О) и (8) выполняется для всех с, 6 [О, Ц С д/(0). * П р им ер 5. Пусть /(и)=шах[и;0), и 6 И'=Е'.
Если Х =Е, то Х„=(0), д/(0)=[0, Ц и (8) имеет место лишь для с, =О. Если Х =(и 6 ГЦ и ) О), то по-прежнему Х, = (0), но неравенство (8) здесь выполняется для всех с, 6 В/(0) = [О, Ц. 6. Определение 2. Пусть Е", Š— евклидовы пространства, )У с Е", П(Ех)— множество всех непустых множеств из Е~. Говорят, что на И' задано многоэначное отображение Г: Иг -«П(Ех), если каждой точке и 6 И" поставлено в соответствие некоторое множество Г(и) С П(Е ). Определение 3. Многоэначное отображение, которое каждой точке и иэ открытого выпуклого множества Иг С Е" ставит в соответствие субдифференциал д/(и) некоторой выпуклой на И' функции /(и), называется субдифференциельныи отобрархенлем н обозначается через д/ (здесь и! = и), Субдифференциальное отображение обладает рядом замечательных свойств [264; 604; 605; 617; 670[; на некоторых из них мы здесь кратко остановимся.
Определение 4. Пусть Иг — множество из Е". Многознвчное отображение Г; )У -«П(Е~) называется: Ц компактным, если для любого компактного множества У с Иг множество Г(У) = [) Г(и) компактно «еи 2) монотоннв!м, если (с(и) — с(и), и — е) ) О при всех и, о 6 Иг, с(и) 6 Г(и), с(о) б Г(и) (здесь подразумевается что и = т) 3) гыпуклозначным, если Г(и) — выпуклое множество при каждом и б Иг; 4) замкнутьгм (погунелрерыгным сггрху) в точке о 6 И', если из того, что («ь) -! е, и), 6 И', и (сь) -«с, сэ 6 Г(оь), й = 1, 2,...
следует с 6 Г(о). Теорема 5. Пусть /(х) — гетуклая функция на откр«ппом г«тухлом множестге Иг лз Е". Тогда субдцффгренциальное отображение д/: И'«П(Е") гылуклоэночно, монотонно, замкнуто, компактно. До к аз а тел ь от в о. Выпуклозначность отображения д/ следует из теоремы 2. Возьмем произвольные и, е 6 Иг, с(и) 6 В/(и), с(е) 6 д/(и). Тогда согласно (2) /(и) — /(«) ) (с(и), и-и), /(о) — /(и) > (с(и), « — и). Сложив эти два неравенства, получим (с(и) — с(о), и — «) >О. Монотонность д/ Установлена. Далее, пУсть об ИГ, (еь) «и, е! 6 Иг, пУсть (сь)-«с, сь а 6 д/(оз ), Это значит, что /(и) - /(еь ) Р (сь, и — «з ) пРи всех и 6 )У.
ПосколькУ фУнкциЯ /(и) непрерывна на Иг (см. теорему 2.15), то, йереходя к пределу в этом неравенстве при й « со, приходим к неравенству (2), Это значит, что с 6 д/(и). Замкнутость доказана. Наконец, возьмем произвольное ограниченное замкнутое множество У С Иг. Поскольку Иг — открытое множество, то все точки У являются внутренними для И' и найдется такое число 6 > О, что ограниченное замкнутое множество Уг = [и 6 Е"; [и — и[( 6) и 6 У), представляющее собой 6-раздутие множества У, принадлежит Йг. В самом деле, если И(ж Е", то У СЕ" при любом 6 >О.
Если же И фЕ", то граница Гр Иг выпуклого мнохгества непуста и р(и Гр И ) = 'ш( !в-ю[> О при всех «6 У, В силу леммы 2 1 2 функция р(и Гр И ) непре«ЕГр (У рывна на компактном множестве У и согласно теореме 2,1.1 найдется такая точка е, 6 У, что !п( р(с, Гр И') = р(в„Гр Иг) = 26 >О. Это значит, что Уг С И', Функция /(и) непрерывна «еи на компактном множестве Уг, поэтому зпр /(и) = /г < оо (теорема 2,1.4). и, Возьмем любые и 6 У, с 6 д/(и).
В неРавенстве (2) положим и = о + дс/[с[ С Уг С Иг. Получим [с) ([/(и+ 6с/[с[) — /(о)]/6 (2/г/6 = АХ < со для всех с 6 д/(в), «6 У. Таким образом, зпр знр [с) = аир [с[< АХ < оо, т. е. множество д/(У) ограничено. Докажем «еуаег/(«) «ег/(о) замкнутость д/(У). Пусть (с, )-«с, сь 6 д/(У). Это значит, что существует такая точка еь 6 У, что с, 6 д/(оь).
Поскольку У вЂ” компактное множества, то без ограничения общности считаем, что (оь ) -«в С У. В силу замкнутости отображения д/ тогда с 6 д/(е) с д/(У). Следовательно, д/(У) — замкнутое множество. Компактность отображения д/ установлена. П Опираясь на теорему 5, можем уточнить свойства непрерывности и дифференцируемости выпуклых функций на открытом множестве, в частности, обобщить теорему 1.8.3 на многомерный случай. Те о р е и а 6. Пусть /(х) — выпуклая функция нс открытом гылуклом множестге Иг иэ Е", Тогда на любом компактном множестге 0 с Иг функцсл /(х) удоглетеорлет 203 6 6. СУБГРАДИЕНТ СУБДИФФЕРЕНЦИАЛ 202 Гл.
4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА условию Лапшаца, т. е. существует такая постоянная 5 = 6 (О) >О, что ]7(и) — у(в)] ( <Е]и — в], и, вц П. До к а за т ель от е о. Возьмем У = со Π— это выпуклая оболочка компактнога множества О, В силу теоремы 1.8 У вЂ” выпуклое компактное множество, У с Иг. Тогда у(и) — 7(в) > > (с(в) и — в) > — 5]и — в], и в 6 У, где Е = зор ]с] < со а силу теоремы 5. Поменяв здесь вЛа) и, в местами, имеем 7"(в) — у(и) > — 5]и — в], и, в 6 У. Отсюда следует утверждение теоремы (см.
упражнение 2.29). П Теорема 7. Если функцая 7(х) выпукла и дифференцаруема в каждой )почке открытого выпуклого множества ИГ С Е", то ев градиент 7'(х) непрерывен на Иг. До к аз а тел ь от в о. Вначале параграфа мы установили, что субградиент выпуклой днфференцируемой функции совпадает с градиентом, так что ду(и) =()ч(и)) Чин Иг. Возьмем произвольную точку в 6 Иг и последовательность (вь) 6 Иг, (вь) -ь в. Множество У = (и = вь, й = 1,2,...) О (в) компавтно и У С Иг.
Тогда в силУ теоРемы 5 множество дР(У) = (с„. = 7'(вь), й = 1, 2,...) компактно. Пусть с — произвольная предельная точка множества аР(У). тогда существует подпоследовательность сь — — 7"'(вь ) ь с. ив замкнутости субдифференцизльного отображения следует, что с 6 дг(в) = (7"'(в)), т. е. с = 7'(в). Это значит, что последовательность (у'(вь)) имеет единственную предельную точку, совпадающую с 7"'(в). Отсюда и из произвольности точки в и последовательности (вь) -ь в следует непрерывность градиента 7~(х)на И).П Для получения интересных экстремальных свойств субдифференциального отображения нам понадобится Л е и м а 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
