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