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