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