Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 63
Текст из файла (страница 63)
Если /(х) равномерно выпукла с модулем 6(1), то функция д(х) = с/(х) при любом с = сопз| > 0 также будет равномерно выпуклой с модулем сб(1), Если /с(1) — точный модуль выпуклости равномерно выпуклой функции /(х) на Х, то любая функция 6(1) < /л(1), О < 1 < Йагп Х, неотрицательная, нетождественно равная нулю, б(1) =О, будет модулем выпуклости функции /'(х) на Х. Следующая теорема является обобщением теоремы 3.1. Т е о р е м а 1.
Лусть Х вЂ” выпуклое замкнутое множество из Е" (например, Х = Ж"), а функция /(х) равномерно выпукла и полунвпргрывна снизу на Х. Тогда: /) множество Лгбгга М(п) = (и: и Е Х, /(и) < /(и)) выпукло, замкнуто и ограничено при всех и Е Х; 2) /; = 1п(,/(и) > — со, Х„= (и: и Е Х, /(и) = Я ф (с),' 3) имеет место неравенство 6(!и — и,!) < /(и) — /(и,) (2) при всех и е Х, и„е Х.; 4) если, кроме того, /(х) строго равномерно вьтукла на Х, то Х„ состоит из единственной точки и, и всякая минимизиругои(ая последовательность (иь).
'(и ) е Х, 1пп /(иь) = /„сходится к томке и,. Для доказательства этой теоремы нам понадобятся следу(ощие две леммы о свойствах точ. ного модуля выпуклости. Л е м м а 1. Пусть М(() — точный модуль аьспуклостн равномерно еыпуклой функции /(м) нс зьтуклом множестве Х. Тогда м(с() > с~и(ь) (3) для всех с > 1, ( >О, О< с( <б(атХ. Доказательство. Сначала рассмотрим случай ! < с < 2.
По определению р(с|) для л(обого з > О существуют точки о(, цз е х и число а, О < а < 1, такие, что )и( — иг! = сь н р(с() « ' р(с() -1- г, где и = ссм(+(1 — а)оя. Отсюда имеем а/(и() + (1 — а)/(ссх) — /(мь) < а (1 — а )н (сс) -(- а (1 — а) г. (4) Можем считать, что О < а < 1/2, так как в противном случае в (4) точки и( и оэ мох(но поменять ролями. Тогда с учетом 1 < с < 2 можем сказать, что О < а < ас < 1. Кроме того, 1/2<1/с <1, поэтому оэ — — (1/с)о(ч(1-1/с)охе х, причем |пэ — ох|=|о( — мя|/с= с. заметим также, что н = асов+ (1 — пс)оэ. Тогда /(оэ) < (1/с)/(е() + (1 — 1/с)/(ня) — (1/с)(1 — 1/с) р(с(), /(мь) < ссс/(ог) + (1 — пс)/(~) — ссс(! — ас)р(2).
Умножим первое нз этих неравенств на ас и сложим со вторым. Учитывая неравенство (4), получаем пс(1/с)(! — 1/с)р(с() + пс(1 — пс)р(() < < а/(и() + (ас — а)/(и ) — (1 — ас)/(оэ) — /(м ) = = а/(и()-1-(1 — п)/(ох) — /(и„) < а(1 — а)(4(сь) + а(1 — сс)г 209 208 $7.
РАВНОМЕРНО ВЫПУКЛЫЕ ФУНКЦИИ Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА )!' Е (8) д = Я(е, со) = (о: о б Х, !и — о/ ( со) У(о))/г=/(е) — В и=/(е) — Уг)0, (5) (6) или а(! — 1/с)р(сс) + ас(! — ас)р(С) < а(! — а)р(сС) + а(! — а)г. Поскольку здесь е > 0 — произвольное число, то можем г устремить к +О. Будем иметь ас(! — ас)р(С) ( (а/с)(! — ас)р(сс) или с р(С) ( р(сз) Неравенство (3) для случая ! ~ (с < 2 доказано. Пусть теперь с ) ! — произвольное число, 0 < с! (д!авХ.
Поскольку йш 1/с= 1, то найдется Ь (! (~ Ь <2) такое, что с =Ь" при некотором натуральном п ) !. Учитывая, что по доказанному р(ЬС) > Ьзр(С~, получаем р(сг) = = р(Ь"С) = р(Ь ° Ь" С)> Ьэр(Ь" 'С) > Ьгр(Ь" С) »... ЬЗ"р(С)=с р(С). !З Л е и и а 2. Пусть р(С) — точный модуль выпуклости равномерно гыпуклой функции У(х) но выпуклом множестве Х. Тогда: 1) р(с) = О(сз) при с — +о; 2) р(С) тО при 0< С < т= Сп((С! р(С) >О), р(С) строго монотонно растет при т < с < < д!ав Х; 3) если д!ав Х = оо, то !пп р(С) = со, С ь« Доказательство. Иэ определения ! следует, что р(го) >0 при некотором Со, 0< Со < < 61ав Х.
Поэтому 0( т < й!ав Х. Если т > О, то р(С) тО при 0 ч С < т по определению т. Пусть т < С < о < 6!ав Х. Тогда с помошью неравенства (3) имеем р(о) = р((о/С)С) > > (о/С) р(С) > р(С) > О, т. е. С«(С) строго монотонна при т < С ( д!ав Х. Далее, если т > О, то условие р(С) = О(СС) при С -«+О выполняется тривиально.
Поэтому пусть т = О. Тогда, фиксируя какое-либо Со, 0 < ~ ~ (д!ав Х, для всех 0 < С < Со имеем р(Со) = = р((со/с)с) ) (со/с)~!«(с) или р(с) ( р(со)сз/со — — сонэ! сз, Это и означает, что р(с) = О(с ) при С -«40. Наконец, пусть д!ав Х = оо. Тогда р(С) определена при всех С > О. Пусть С ) Со > т.
Тогда р(с)=р((с/со)со)э)(с/со) р(сс)=сонэ! с . это знечит, что р(с) — «сопри с — «со со скоростью не медленнее, чем Сз. П Заметим, что из неравенства 0 < 6(С) < р(С), справедливого для любого модуля выпуклости равномерно выпуклой функции, и из леммы 2 следует, что условие 6(С) = О(сз) при с -« -«+О являетсн необходимым для того, чтобы некоторая функция б(С) могла служить модулем выпуклости для какой-либо равномерно выпуклой функции. Доказательство теоремы 1. Если множество Х ограничено, замкнуто, т. е. Х компактно, то утверждения !), 2) теоремы следуют иэ теорем 2.1.1, 2.!О, леммы 2.1.1.
Остается рассмотреть случай, когда Х вЂ” неограниченное множество. Тогда 41ав Х = со и точный модуль выпуклости р(С) функции У(х) будет определен при всех С > О. Пусть Со > 0 и р(го) > О. Возьмем произвольную точку о б Х и рассмотрим шар Иа теоремы 21.! следует, что !п1/(х) =Уз > — оо, так что г при всех о б Я. Возьмем произвольную точку о б Х ! Я, т. е. 1и — о~ > Со.
Тогда, учитывая доказанную в лемме 2 строгую монотонность р(С) при С > т, имеем 0 ( ао — — (р(го)/р(!н — е!))С/з ( ! При а = ао из (1) получаем ао/(н)) У(о+'со(о — о)) (1 «о)У(е)+по(1 — со)р0и — о0 (7) Из (6) и леммы ! следует р(го) = агбар(!и — е0 = пор((1/ао)ао!и — о0 > р(ао«!и — Ц) или р(С«!) Э р(ао!«о Ц). В силу монотонности р(С) это означает, что ао««м — о) < <С!. Тогда о + 4 аз(и — о) б Я и согласно (5) У(о+ по(и — е)) Э)У(е) — ш Учитывая эту оценку, йз (7) имеем аоУ(о) > ао/(е) и+ ао(! ао)р()и о1) Отсюда, сокращая на ао > 0 и вспоминая определение (6) величины ао, получаем У( ) >У( )+(1- о)р(! -~!)-./ о=У( )+р0.— !)-/р0 -Ю()/р(4)~-./~/р(со)) Применяя к последнему слагаемому неравенство оЬ < (оз+ Ьз)/2, будем иметь У(и)>У( )+р(! — Ч)/2 — ()/р(со)+ /~/р(со))'/2 для всех и й Х ! Я.
На свмом деле, неравенство (8~ имеет место для всех и б Х. Действительно, если м б Я, то р(|и — е!) < р(го), а согда и < (~С!«(Со) т и/Ь/р(го))~/2 — р()м — о!)/2. Отсюда и из (5) следует справедливость (8) и для о б Для всех о ц М( иэ (8) имеем м(|и — о!)/2 — (/р(го)+ и/«/р(го)) /2 < <У(о) — У(е) < О, т.е. р(!о-о!)<(у'р(со)+ ы/~/р(со)) при любом о ем(е), поскольку р(с)-«сопри с — «со и только в этом лучае, то з последнего неравенства следует ограниченность множества М(о).
Выпуклость М(е) следует из теоремы 2.10, а замкнутость М(о) — из леммы 2.1.1. Из тео емы 2.1.2 имеем, что У > -со, Х„ ф Сбг. ока«кем неравенство (2). Поскольку любой модуль выпуклости 6(С) < р(С), то неравен. ство (2) достаточно доказать для р(С). Возьмем любую точку о, ц Х„. Тогда 0 < У(ам+ (!— — а)о,)-У(о ) < а(У(о)-У(и,))-а(! — а)р0и — е1) или сс(! — а)р(1о-о„!) ( а(У(о)-У(о, )), 0 < а < 1, м й Х. Деля на а > 0 и устремляя а -«+О, отсюда получаем йеравенство (2). Наконец, пусть функция У(х) строго равномерно выпукла на Х.
Тогда она строго выпукла на Х и согласно теореме 2,1 множество Х, будет состоять из единственной точки и„. Возьмем произвольную минимизируюшую последовательность (оь). Полагая в (2) н = оь и устремляя Ь -«оо, получаем 6(1мь -и1) -«О.
Это возможно только при |иь — и!-«О, так как У(х) строго равномерно выпукла. 2. Остановимся на некоторых необходимых, а также достаточных условиях равномерной выпуклости функции. Те о р е и а 2. Пусть Х вЂ” открытое гылукгое множество иг Еь, пусть функции У(х) равномерно выпукла но Х с модулем выпуклости 6(С). Тогда необходимо гылогнлютсл неравенства У(м) > У(е) -1- (с(о), о — е) + 6()и — о!), (9) (с(и) — с(о), о — е) > 26 (!и — ь!) (ГО) лри всех с(ь) б д/(о), с(и) б д/(о) и всех и, е б Х .
Доказательство. Поскольку равномерна выпуклая функция является и просто выпуклой, то иэ теоремы 6.1 следует, что д/(о) ф йг при всех и и Х. Возьмем произвольные с:„е 6 Х, с(о) и д/(е). Из определения субградиентз и иэ (1) при всех а, 0 < а < 1, имеем а(с(е), м-о)+У(о) ( У(ао+(1-а)о) < а/(и)+(1-а)У(о) — сс(1-а)6(!о-е0 или (1-а) 6(!и-о!)+ < с(е), и-о >( У(о)-У(е). Отсюда при а -«+О получим неравенство (9). Меняя в (9) переменные о и о ролями, будем иметь У(о) > У(о) + (с(о), е — о) + б()о — ь!)«с(и) б д/(и). Складыван это неравенство с (9), приходим к (10).СЗ Приведем одно достаточное условие равномерной выпуклости функции. Теорема 3. Пусть Х вЂ” еьтуклое множество, У(х) и С'(Х), и пусть для некоторой непрерывной неотрицательной функции 6(С), 0 ( с ч й!авХ, 6(С) = О(Сз) лри с -«+О, 8(С) ЮО, гыпогняется неравенство (У'( )-У'(о),о- »8(( -М) (11) при всех о, ь н Х.
Тогда функция У(х) разномерно выпукла на Х с модулем гьтуклости ! 6(С) = 1(С(тг)/т)дт. о Доказательство. Из формулы (2.7) и условия (11) имеем а/(о)+(! — а)У( ) — У( +(1 — а)о)= ! «"(1 с") С(У(г!) У(гз)«г! гз) т «"(1 «") ! ч0х! х20 г о о ! = а(1 — а) ) 8(т)о — о0 — = а(1 — а)6(«!о — о«!), и, об Х, а й[0,1], о 210 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА что и требовалось. П Доказанная теорема 3 может быть использована для установления рааномерной выпуклости конкретных функций. Теорема 4. Функция /(х)= ~а[" строго разномерно выпукла но и" лри асах р) 2.