XIV Аттетков и др. Методы оптимизации (1081420), страница 21
Текст из файла (страница 21)
разность ср(1) — ср(0) совпадает с левой частью неравенства (3.29). Тем самым доказано, что это неравенство выполняется с параметром у = 0,5р. ~ (Н( )Р Ь) > ~У ~2 (3.30) где Н (х) — матрица Гессе функции 1 (х) в точке х. Теорема 3.17.
Для того чтобы функция 1(х), дважды непрерывно дифференцируемая на открытом выпуклом множестве й с Б'."', была сильно выпуклой, необходимо и достаточно, чтобы существовала константа р > О, для которой при любых х Е Й и Ь Е 1с"' верно неравенство 3.5. СильнО выпуклые функции м Необходимость. Пусть х — — точка открытого выпуклого множества й и Ь е Кп. Тогда при достаточно малом св > 0 имеем х+ еЬ Е й при ~е~ ( св и функция г)гЯ = (р.ас11(х+ ~Ь), Ь) определена и дифференцируема на некотором отрезке ~0, т), т > О. К этой функции можно применить формулу конечных приращений: ф(т) — ф(0) = г)г''гдт)т., д Е (О, 1).
Непосредственным вычислением с помощью правила дифферен- цирования сложной функции получаем г (" ес~ .-гьс ) г=1 и и оиэ О=1 г=г где Ь = (60 ..., 6„). Таким образом,. (дгас1 )(х+ тЬ) — ягас11(х), Ь) = (Н(х+ дтЬ)тЬ, Ь), (3.31) где д Е (О, 1). Если функция ~(х) сильно выпукла, то для нее выполняется неравенство (3.28). Используя это неравенство для точек хг = = х+тЬ, х~ = х, находим (Н(х+ дтЬ)Ь, Ь) = — (рас11(х+ тЬ) — рас1 ~(х), тЬ) > д~Ь~~.
Переходя в этом неравенстве к пределу при т — ) О, получаем неравенство (3.30), Достаточность. Покажем, что если для произвольных х Е й и Ь Е К верно неравенство (3.30), то для произвольных 3. ыииимизлция Выпуклых Фуггкций 138 точек х',х~ Е й верно неравенство (3.28). Согласно теореме 3.16, .это и будет овна сать, что функция 1'(х) сильно выпукла. Выберем произвольные точки хс, хз е й. Тогда, преобразуя равенство [3.31), .которое выполняется для любой функции Дх), дважды дифференцируемой на отрезке [х, х+ тЬ~, можем записать (8гас1Дх') — 8гай1[х~), Ь) = (Н(х~+ дЬ)Ь, Ь), (3.32) где в данном случае Ь = х' — хз.
Используя неравенство (3.30) при х = хе+ дЬ и Ь = х' — х~, заключаем, что (8гас1) [х ) — 8гас1Дх ), х — х ) > р~х — х[, т.е. выполняется неравенство (3.28). ~ Пример 3.14. Убедимся в том, что функция 1(х) = ~х — у[з является сильно выпуклой на множестве гс" (здесь у Е Б'." произвольная фиксированная точка). Вычислим градиент функции 1(х) = (х — у, х — р): ягас1 )'(х) = 2(х — у). Используя это выражение, можем записать (8гас1Дх ) — 8гасс)[х ), х — х ) = = (2(х" — у) — 2(хв — у), х' — х") = 2~х' — х ~". Отсюда видно, что неравенство (3.28) будет выполнено, если выбрать параметр сс из интервала (О, 2).
К тому же выводу можно прийти, если вычислить матрицу Гессе функции и применить теорему 3.17. 1(х) — 1(х') "с' (3.33) Теорема 3.18. Пусть функция 1" (х) сильно выпукла на выпуклом множестве й С Бв. Если х* е й -- точка локального минимума функции Дх), то для любого х Е й справедливо неравенство 139 З.о.
Сильно выпуклые функции где у — параметр сильной выпуклости. Если к тому же функция Дх) непрерывно дифференцируема на Й, то для любого х Е Й выполнены неравенства 7~х — х'~' < (дг а~(х), х — х*), у)х — х'! < (дгае1~(х)(, (3.34) О < 71х) — 71х') < — )дгас1~(х)(~. 'у ~ Отметим, что точка локального минимума выпуклой функции является точкой ее наименьшего значения (см. теорему 3.14). Поэтому для любой точки х Е й выполняется неравенство Дх) ) 7" (х*).
Из неравенства (3.27) при х1 = х, хв = х* и сь = 1/2 имеем 7" (х/2+ х'/2) < 1(х)+1(х ) у * 2 2 4 — — (х — х(. Отсюда, учитывая, что 7'(х*) < ~(х~2+ х*/2), приходим к неравенству (3.33). Если функция 7"(х) дифференцируема на й и сильно выпукла, то для ее точки х' локального минимума, согласно теореме 3.15, справедливо неравенство (дгас17" (х*), х — х*) ) О. С учетом этого неравенства из соотношения (3.28), в котором, согласно доказательству теоремы 3.16, можно положить д = у, при Ь = х — х* находим у~х — х ~ < (3гас17(х) — рае171х ), .х — х ) = = (~гае17(х), х — х*) — 13гас1 ~(х'), х — х*) < (угайу (х), х — х*), что равносильно первому неравенству в (3.34).
Применяя к его правой части неравенство Коши Буняковского, получаем у/х — х'/~ < (3гас17(х), х — х') < /3гас171х)! /х — х'!. (3.35) 140 3. МИНИЛ4ИЗЛЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ Это приводит ко второму неравенству в (3.34). Наконец, используя неравенства 13.20) и (3.35), заключаем, что 1'(х) — )'1х*) < (Ксану(х)., х — х') < < ~рас1у(х)~(х — х'~ < — ~дгас1у(х)~ . 7 Записанные неравенства в сочетании с неравенством 0 < у1х)— — у(х") дают третье неравенство в (3.34).
~ Теорема 3.19. Функция ~(х), сильно выпуклая и непрерывная на замкнутом выпуклом множестве Й с н,", достигает своего наименыпего значения на Й. М Выберем произвольную точку х~ Е Й и рассмотрим множество Хе = 1 х Е Й: ) (х) < 1 (хе) у. Если функция у'(х) достигает на Хе наименьшего значения в некоторой точке х*, то эта точка будет и точкой наименьшего значения функции на множестве Й, так как длЯ любой точки х Е Й'1 Хв выполнЯютсЯ неравенства у(х*) < 1'(хв) < у(х). Чтобы доказать, что на Хе функция у1х) достигает наименьшего значения, достаточно (с учетом непрерывности функции) доказать, что множество Хв замкнуто и ограничено, т.е. компактно [Ч). Множество Хе замкнуто в силу непрерывности функции у(х) на множестве Й.
Действительно, пусть х предельная точка множества Хе. Поскольку Хв с Й, а Й замкнутое множество, то х е Й и функция у(х) непрерывна в точке х. Выберем последовательность 1х") точек множества Хе, сходящуюся к точке х. В силу определения множества Хв верно неравенство 1(хя) < 1(хв). Переходя в этом неравенстве к пределу при п — ~ ос, получаем ) (х) = 11ш 1 (х ') < ) (х ), что равносильно соотношению х Е Хв. 3.5. Сильно выпуклые функции Множество Хо является выпуклым. В самом деле, выберем произвольные точки х~, хз е Хо. Тогда для любого а е [О, Ц точка ах + (1 — а)х принадлежит Й и 1(ах +(1 — а)х ) <ау(х )+(1 — а)у(х ) < < )( о)+(1 )~( 0) ~( о) т.е. ах~+ (1 — а)х~ Е Хо.
Докажем, что множество Хо ограничено. Используя неравенство (3.27) для точки хо и произвольной точки хУ из выпуклого множества Хо, заключаем, что о~о < < ау(х )+(1 — а)1(х ) — 1(ах +(1 — а)х ) < < 1(')+(1 — )Пх') — П '+(1 — а) ') = =~(х")- У(ах'+(1-а)х'). (336) Так как функция у'(х) непрерывна, то можно указать такую окрестность точки х, что в пересечении этой окрестности с Й функция будет ограниченной. Следовательно, для некоторого числа д > О и некоторого М Е К выполняется неравенство Дх) > М при )х — хо~ < д, х а (1. Предполагая, чтоб < ~х' — хо(, е выберем а =, „.
Тогда для точки х = ах~ + (1 — а)хо хе) ' имеем (х — хо! = а)х' — хо! < б и 1(х) > М. Из неравенств (3.36) получаем а(1 — а)у~х — х ~ <1(х ) — М. Так как при б < ~х' — хо~ выполняются соотношения а(1 — а) у(х — х ~ > — "у~х — х ( = — ~х — х ~, оз и 1 оз 0'У о 2)х — хо( 2 заключаем, что 0)<ш л ( ( ) 142 3. МИНИМИЗЛЦИЯ ВЫПУКЛЫХ ФУНКЦИЙ Это означает, что множество Хв целиком попадает в и-мерный шар с центром в точке х и радиусом 4У(хо) Ы) ду т.е.
оно ограничено. На замкнутом ограниченном множестве Хв непрерывная функция Дх) достигает своего наименьшего значения ~У) в некоторой точке х'. Так как при х е Й ~ Хв выполняются соотношения ~(х) ) 1(х ) > 1 (х*), точка х' является точкой наименьшего значения функции и в пределах множсства Й. ~ Замечание 3.5. Теорема 3.19 перестает быть верной, если в ней условие сильной выпуклости заменить условием выпуклости или строгой выпуклости: строго выпуклая (в частности, выпуклая) функция может и нс достигать своего наименьшего значения на замкнутом множсстве.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
