Ф.П. Васильев - Методы оптимизации (1125241), страница 63
Текст из файла (страница 63)
ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА или а(1 — 1/с)р(ст) + ас(1 — ас)р(С) ( а(1 — а)р(сг)+ а(1 — а)г. Поскольку здесь г > 0 — произвольное число, то можем г устремить к -1-О. Будем иметь ас(1 — ас)р(С) < (а/с)(1 — ас)р(сг) Нпи схр(С) < р(сг) д=д(э,г,)»х(и: БХ,! — э~<С,) Из теоремы 2.1.1 следует, что «п1 /(т) = /г > -оо, так что 3 /(и) > /г = /(э) — и, и = /(э) — /г > 0 (3) пРи всех и б Я. Возьмем пРоизвольнУю точкУ и б Х т« Я, т. е. !и — э! ) Со. Тогда, Учитываа доказанную в лемме 2 строгую монотонность р(С) при С > т, имеем О< =(р(со)/р(~и — Щ))1/ <1 При а = ао из (1) получаем (6) ао/(и) > /(э+ со(и — э)) — (1 ао)/(э)+ ао(1 — ао)р(1и Ч) (7) Из (8) и леммы 1 следует р(81) = пор(/и — э!) = пор((1/ао)ао!и — э!) > р(ао/и — э1) или р(со) > р(ао(и — э/). В силу монотонности р(с) зто означает, что ао/и — э/ < со.
тогда э+ + ао(и — э) П Я и согласно (5) /(э+ ао(и — э)) ) /(э) — «га Учитывая эту оценву, йз (7) имеем ао/(и) ) ао/(э) — «'+ ао(! — ао)р(1и — Ч) Отсюда, сокращая на ао > 0 и вспоминая определение (8) величины ао, получаем /(и) > /(э)+(1-ао)р0 -э!)-и/ о- /(э)+р(1и-э!)-т/р(!и — Ю(у/р(со)+и/)/р(со)).
Неравенство (3) для случая 1 < с < 2 доказано. Пусть теперь с ) 1 — произвольное число, 0( сС (сйашХ. Поскольку !!ш ~/с = 1, то найдется Ь (1 ( Ь < 2) такое, что с = 6" при «О некотором натуральном и ) 1. Учитывая, что по доказанному р(ЬС) > Ь р(ф получаем р(сг) = = р(Ь" С) = р(Ь Ь" С)) Ь р(Ь" С) > Ь"р(Ь" С) >и... ~> Ь р(С) =с р(С). П Л е м и а 2. Лусть р(С) — точный модуль вь«луклости равномерна выпуклой функции /(х) на зь«пуклом множестве Х, Тогда: 1) р(С) = О(СС) лра С -» +О; 2) р(С) тО при 0 < С < т = «п((С: р(С) >0), р(С) строго моиотонно растет лри т < С < ( 61аш ХС 3) если д!агпХ =со, то !пп р(С) =со.
Доказательство. Из определения 1 следует, что р(го) >0 при некотором Со, О < Со < < д!аш Х, Поэтому 0 ( т ( б!ашХ, Если т > О, то р(С) тО при 0 < С < т по определению т. Пусть т < С < а < 61ашХ. Тогда с помощью неравенства (3) имеем р(а) = р((а/С)С) > > (а/с) р(с) > р(с) >О, т. е. р(с) строго монотонна при т < с < 61аш х далее, если т > О, то условие р(с) = О(сз) при с -«+О выполняется тривиально. поэтому пусть т = О. Тогда, фиксируя какое-либо Со, 0 < ~ < б!аш Х, для всех 0 < С < Со имеем р(то) = =Р((со/с)с) >(Со/с) Р(с) или Р(с) < Р(со)с~/со — -сапа! с . это и означает, что Р(с)= О(с ) при С -»-1-О.
Наконец, пусть б)аш Х = оо. Тогда р(С) определена при всех С > О. Пусть С > Со > т. Тогда р(с) = р((с/со)со) ) (с/со)~р(со)=сопз1 сз, это значит, что р(с) — »са при с -«оо со скоростью не медленнее, чем ст. П Заметим, что из неравенства 0 < б(С) < р(С), справедливого для любого модуля выпуклости равномерно выпуклой функции, и из леммы 2 следует, что условие б(с) = О(ст) при с — « — «+О является необходимым для того, чтобы некоторая функция 6(С) могла служить модулем выпуклости для какой-либо равномерно выпуклой функции. Доказательство теоремы 1. Если множество Х ограничено, замкнуто, т.
е. Х компактно, то утверждения 1), 2) теоремы следуют из теорем 2,1.1, 2.10, леммы 2.13. Остается рассмотреть случай, когда Х вЂ” неограниченное множество. Тогда д)аш Х = со и точный модуль выпуклости р(С) функции /(т) будет определен при всех С > О, Пусть Со > 0 и р(го) > О. Возьмем произвольную точку э б Х и рассмотрйм шар Применяя к последнему слагаемому неравенство аЬ ( (а + Ьз)/2, будем иметь /(и) > /(э) 1- р0и — э!)/2 — ()/С«(то) + и/~/р(то))х/2 (8) для всех и б х»1Я. на самом деле, неравенство (8) имеет место для всех и б х. Действительно, если и е Я, то р(1и — э1) < 1«(со), а тогда и < ( р(со) + и/т//р(со)) /2 — р(1и — э1)/2. Отсюда и из (5) следует справедливость (8) и для и б д. Для всех и б М(э) из (8) им~еем (1и — э!)/2 — ( /р(Со) + и/)/р(то)) /2 < /(и) — /(э) < О, т.
е. Р(/и — э!) < (У'Р(со) -ь и/~/Р(со)) пРи л«обом и б м(э). посколькУ Р(с) -«оо пРи с — » оо и только в этом лучае, то з последнего неравенства следует ограниченность мно»кества М(э). Выпуклость М(э) следует из теоремы 2,10, а замкнутость М(э) — из леммы 2.1.1. Из теоремы 2.1.2 имеем, что / > -оо, Х« та 1Э. Докажем неравенство (2).
Поскольку любой модуль выпуклости б(С) < р(С), то неравенство (2) достаточно доказать двя р(С). Возьмем любую точку и, б Х„, Тогда 0 < /(аи + (!в — а)и,) — /(и ) < а(/(и) — /(и„)) — а(1 — а)р(/и — э1) или а(1 — а)р(1и-и,!) < а(/(и) — /(и,)), 0 < а < 1, и б Х. Деля на а > 0 и устремляя а — »+О, отсюда получаем йеравенство (2). Наконец, пусть функция /(х) строго равномерно выпукла на Х. Тогда она строго выпукла на Х и согласно теореме 2.1 множество Х, будет состоять из единственной точки и„. Возьмем произвольну«о минимизирующую последовательность (иь).
Полагая а (2) и = иь и устремляя й -«оо, получаем 6((иь — и,!) — » О, Это возможно только при 1иь — и,!-«О, так как /(х) строго равномерно выпукла, 2. Остановимся на некоторых необходимых, а так»ке достаточных условиях равномерной выпуклости функции. Теор ем а 2. ЛугтьХ вЂ” открытое аьтуклог множество из В", пусть функция /(х) равномерно выпукла на Х с модулем выпуклости б(С). Тогда необходимо выполняются неравенства /(и) ) /(э) + (с(э), и — э) ч- б((и — э!), (9) (с(и) — с(э), и — э) > 26(1и — э!) (10) лра всех с(э) б д/(э), с(и) б д/(и) а всех и, э ОХ. Д о к а з а т е л ь с т в о. Поскольку равномерно выпуклая функция является и просто выпуклой, то из теоремы 8.1 следует, что д/(и) ~ к1 при всех и б Х. Возьмем произвольные и, э б Х, с(э) б д/(э).
Из определения субградиента и из (1) при всех а, 0 < а < 1, имеем а(с(э), и — э)+/(э) (/(аи+(1 — а)э) ( а/(и)+(1-а)/(э)-а(1 — а)б(1и-э!) или(1-а)б(1и-э1)Ч- <с(э), и-э ></(и) — /(э). Отсюда при а — » ЧО получим неравенство (9), Меняя в (9) переменные и и э ролями, будем иметь /(э) > /(и) ь (с(и), э — и)+ 6(!и — э!), с(и) е д/(и). Складывая это неравенство с (9), приходим к (10). П Приведем одно достаточное условие равномерной выпуклости функции. Теорема 3.
Лусть Х вЂ” выпуклое множество, /(х) бО1(Х), и пусть для некоторой непрерывной неотрицательной функции 6(с), 0 < С < й!аш Х, 6(С) = О(сз) при С вЂ” »+О, 6(С) тО, выполняется неравенство (/ (и) — /«(э), и — э) ) 6((и — э!) (11) при всех и, э б Х. Тогда функция /(х) равномерно выпукла на Х с модулем выпуклости 1 6(С) = ((8(С)/т)йт. о До каза тельство.
Из формулы (2.1) и условия (11) имеем а/(и) + (1 — а)/(э) — /(аи -1 (1 — а)э) = 1 1 (! ) г(/«( ) /«( ) )йт > (1 ) «с(! ~)дт о ! = а(1 — а) ) 6(т)и — э!) — = а(1 — а)б((и — э!), и, э б Х, а б(0, 1)» дт о 211 210 Гл. 4. ЭЛЕМЕНТЫ ВЫПУКЛОГО АНАЛИЗА $7. РАВНОМЕРНО ВЫПУКЛЫЕ ФУНКЦИИ 9 8. Обоснование правила множителей Лагранжа что и требовалось. Г) Доказанная теорема 3 может быть использована для установления равномерной выпуклости конкретных функций, Теорема 4. Функция /(х) = ~х[г строго равномерно выпукла ни Е при всех р >2.
До к а за т ел ь ство. Покажем, что (/'(и) — /'(а), а — о) > Е2 псья(1; 2 "Яа — а[", гь а е Е" (12) Здесь /'(х) = р)х[т гх. Тогда (/'(а) — /'(а), и — а) = (р~а[г и — р[а[с' а, и — а) = ~г+ ~„~р („)([„[р-г+ ~ ~р-г)1 р р 'и[ + а[ — и — а! „г р г)1 ец [р — г [ ~г — г)(~ ~г ~„[г)+ [ „[г(~ ~т — г+ ~„~т — гВ > -а['([ !' '-! [о[" ') (13) Покажем, что [и!г -! [а[г > [и — а[" г щ!п(1; 2 "), и, о е Е". (14) Рассмотрим функцисо р(х)=(хь Р1)/(х+1) прим>1, сг>О,Имеем р(х)=х(х~ с — 1)(х+ +!) ~ с.
Если х >1, то р'(х) > О, и р(х) > р(1) =2~ для всех х>1. Если 0< а < 1, то р'(х) <Ои р(х)> р(со)=1 при всех х>1. Следовательно, р(х) >А =пни(1;2' ) Ух>1, или (15) А„(х+1) <х" +1, х>1, а>0 далее имеем [и-о[г <([а[-ь[а))т г. Без ограничения общности мажем считать |и) > [а[ Тогда с помощью неравенства (!5) получим [г — г < [ [г — г([ [/[ [ + !)р — г < 1-1 (([ [/[ [)г — г + 1)[ [г — г 26(с) < ср[(х-! 1) ' — хг '[, и>к О, с >0 С помощью формулы конечных превращений отсюда имеем 26(с) < сгр(р — П( +ус) г < сгр(р — П а г, х>0, г >О Зафиксируем здесь произвольное с > О, а х устремим к са. Получим 6(г) и 0 при всех с > О.
Таким образом, функция /(х) = [в[" при 1 < р < 2 не является равномерно выпуклой на Е Можно, однако, показать, что эта функция строго равномерна выпукла на любом выпуклом ограниченном множестве из Е" [191). что равносильна (14). Из (13) и (14а) следует неравенство (12). С помощью теоремы 3 отсюда заключаем, что функция /(х) = [х[ при р > 2 равномерно выпукла на е" с модулем 6(г) = = Сгщ!п(1;2 г)/2. П Более тонкие оценки показывают, чта функция Лх) = [х[" при р > 2 имеет точный модуль выпуклости и(с) = са/2г г, г > О, Будет ли функция /(х) = [х~г равномерно выпуклой на Е" при 1 < р < 2? Оказывается, не будет. Чтобы убедиться в этом, достаточно показать, что функция р(х) = х" одной переменной прн 1 < р < 2 не будет равномерно выпуклой на полуоси х > О, поскольку функция /(х) =[к[а вдаль лучей х = се, [е[ = 1, ведет себя как функция с" одной переменной.
Если бы функция р(х)=х", 1 <р< 2, была равномерно выпуклой при х>1 с некоторым модулем выпуклости 6(С), то согласно теореме 2 необходимо выполнялось бы неравенство (10). В данном случае неравенство (10) имеет вид Пользуясь теоремами отделимости выпуклых множеств и теорией неявных функций из классического анализа, мы уже в состоянии дать строгое обоснование правила множителей Лагранжа, изложенного в $2.3, Более того, мы получим необходимые условия экстремума первого порядка для несколько более общей задачи: 7(х) ч (п[, х Е Х, (1) Х=(хеХо: д(х)<0, г=1,...,т; д(х)=0, г=т+1,...,в).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
