Ф.П. Васильев - Методы оптимизации (1125241), страница 84
Текст из файла (страница 84)
В силу теоремы 4.6.6 выраженное в теореме 3 требование условия Липшица от функции Т" (х) можно заменить условием ограниченности множества Х. Проксимальный метод заключается в построении последовательности (х„) по следующему правилу: х ь,=рг(хюа„), й=0,1, (12) где начальная точка х и последовательность (а.) > 0 предполагаются заданными. Итерационный процесс (12) основан на известном из анализа [393) методе поиска неподвижных точек сжима>ощих операторов и идейно близок к рассмотренным выше методам проекции градиента н субградиента. В соответствии с определением проксимального оператора на к-м шаге процесса (12) для определения очередного приближения х,„, нужно решить задачу минимизации (3) при х = х„, а = а„: ч>(г«х„а„) = -!г — хь)'+ аь,»(г) «1п1, г Е Х, й = О, 1,...
(13) Если функция >"(х) дифференцируема на Х, то согласно теореме 4,2.3 точка х„+, будет решением задачи (13) тогда и только тогда, когда (Р «(хь „х,а )«г — х„,)=(х„ь,— х +а,Т«(х„«)«г — х „,) > 0 ЧгЕХ. Отсюда, используя характеристическое свойство проекции (неравенство (4.4.1)), получаем, что х„, = 7> (х„— аь г"'(х„,,)), 1с = О, 1,... (14) Таким образом, для дифференцируемых функций проксимальный метод (12) равносилен методу проекции градиента в так называемой неявной форме, когда х„„, явно не выражено через предыдущее приближение х, и должно определяться как решение уравнения (14). Теорема 4.
Пусть Х вЂ” выпуклое замкнутое множество из Е", функция г(х) определена и выпукла на открытом выпуклом множестве И«, содержащем множество Х, и полунепрерывна снизу на Х, >',= ш1>"(х)> — оо, Х„=(хяХ: У(х)=Я~Я, пустьО(7 (а (Г«, жьх к =О, 1,... Тогда последовательность (х„~, определяемая методом (12) при любом начальном приближении х Е Е, сходится к некоторой точке е, = е„(хс) е Х„ Дока з а тел ьс т во.
Применяя неравенство (4.3.3) к задаче (13) имеем 1 21г хь.««~ ~< ч>(г« ~ь«аь) ч>(хь.«««х«"' = -'~г — х„»>-1)х„„,— х„~'+ая(г) — у(х„„)) ЧгеХ, й = 0,1,, (15) 283 $6. ПРОКСИМАЛЬНЫИ МЕТОД 282 г . 5, метОды минимиздцИИ ФУНКций МНОГИХ пЕРЕМЕННЫх .': гь или (18) Возьмем произвольную точку х„ Е Х. и в (15) положим х = х.. С учетом неРавенства 7'(х,) — ахать) < 0 полУчим !х,— хьь![~ ( !х„— х [г — [х„„,— х„[г (!х,— х„[г, й =О, 1,..., ЫхеХ,.
(16) Отсюда видно, что последовательность ([хь — х,!') не возрастает, а (хь) ограничена. Тогда существует подпоследовательность (хь ), сходящаяся к некоторой точке о„причем о,еХ в силу замкнутости Х. Можем считать, что (сгь )- сг, 0< у < сх < ОР Далее, суммируя неравенство (16), имеем [г<! [г ! [г<! [г Ы])7 1 2 Это значит, что РЯд 2 , '!ха о ь — х !' сходитсЯ и, следовательно, !пп [х,„,— а=о Ь оо — х !=О. Тогда подпоследовательность (х, „,) также сходится к о„. Перехо- дя в (15) к пределу при й=й„- со с учетом неравенства ]]пу)'(хь ь)>Т"(е„), получим: 0< сх (у(х) — Т"(в,)) Чх 6 Х.
Это значит, что е, Е Х,. Поскольку по- следовательность Цх„— х,[г) не возрастает при Ых, Е Х„то в частности пйууи х„= и. мы также получим невозраста!ощую последовательность Яхь — о,! ). Тогда*[пи !х„— о,!'= Ощ [х, — о„[э=О. Теорема 4 доказана. С] * Ь оо г оо Для сильно выпуклых функций у(х) несложно получить оценку скорости сходимости мето- да (12) при пь —— ьь > О, й = О, 1,... Те ор е м а 5, Пусть вььполнены условия теоремы 4 и функция 7(х) сильно выпукла на множестве Х с постоянной сильной выпуклости х >О. Пусть последовательность (хь) определена методом (12) при пь — — и > О, й =О, 1,... Тогда' ]хь — х,! (]хе — х,! д, й=0,1,,,4 У= (17) Доказательство. Из теоремы 4.3.1 следует, что при сделанных предположениях за- дача (1) имеет, притом единственное, решение х„, и -г [л — х,]г < У(л) — У"(х„) Ых Е Х.
Кроме того, функция уо(х, х, и) иэ (2) сильно выпукла с постоянной сильной выпуклости 1+ах и иэ (13) имеем 1+ах г ]х — хь „ь ! < Чь(л, ж,, и) — гь(хь ь ь, х,, и), (19) Ых с Х, й = О, 1,... В неравенстве (18) положим х = ха+, и умножим его на и > 0 н сложим с (19) при х= х,. Получим ( ) * "+' ' ь 2 + ' 2 2 +пк)]ххьь!](2]ххьь]2]хьььхьь]ч2]хохьь[йОь1 Отсюдаследует,что]хь ь — х,! <]хь — х„! 4<]хь ь-х,! у «...]то-х„! 4 ь, й=0,1,...
Оценка (17) доказана. П Отметим, что если функция у(х) дифференцируема на Х, то теоремы 4, 5 сохраняют силу и для метода (14). 2. Опишем непрерывный вариант проксимального метода, следуя [25]. Рассмотрим задачу ьр(х,х„ п(г)) †" 2]х — х! + п(г)7(х) -ььп(, х е Х, (20) где и(!) > 0 ыг > О, х — выпуклое замкнутое множество, у"(х) выпукла на х.
тогда ьо(л,ж,п(г)) сильно выпукла с постоянной сильной выпуклости к = 1 и по теореме 4.3.! задача (20) имеет, притом единственное, решение л = рг(х,п(г)). Введем систему диффе- ренциальных уравнений й(г)= рь( (О, п(г)) — х(1), ! >о. (21) Согласно теореме 1 решение х, задачи (1) удовлетворяет уравнению рг(х„п(!)) — х, =0 при Ыг > 0 Это значит, что каждая точка х„е Х„является точкой равновесия (стационарным решением) системы (21).
Моньно о>кидать, что при некоторых требованиях на функции у(х), и(!) траектории х(!) системы (21) при больших ! приближаются ко множеству Х,. Справедлива Те орем а 6 (Антипин [25]). Пусть множество Х и функция у(х) удовлетворяют условиям теорем 3,4, функцил п(г) нвлрврььвна и 0 < уо ( и(!) <Ть Ыг > О. Тогда траектория х(1) системьь (21), выходлщая из любой тоти х(0) = хо, определена при всех г > 0 и сходитсЯ пРи ! — ь+оо к некотоРой точке в, = в,(хо) е х„кРомв того, бш х(г) = О. Доказательство, В силу теорем 2, 3 правая часть рг(х, п(г)) — х уравнения (21) удовлетворяет условию Липшица по х и непрерывна по г, потому все решения системы (21) определены при всех г > 0 (см.
ниже теорему 6.1.!). В силу уравнении (21) имеем рг(х(г), п(г)) = х(!)+ х(!) е Х и по теореме 63.1 — ]х — Рг(х(г)ь п(г))! = 2]х — (х(!)+ х(г))! ( го(л, х(г), п(г))— 1 г 1 — Чь(рг (х(г), п(г)), х(!)ь п(г)) = — ]л — х(г)! — — ](х(г) + х(г)) — х(!)! + + п(г)(у(л) — у(х(г)+ х(г))) Ых Е Х, ! > О. (22) Полагая з (22) л = х, е Х„с учетом неравенств у(х) — у(х(г)+ х(г)) (О, и(!) > 0 получим: [ж(г) -1- х(г) — х,[г = ]х(г)]г -1- ]х(г) — х„]э+ 2(х(!), ж(г) — х,) < ]х(г) — х„]г — ]х(г)]г ]х(!)! + 2 а ]х(г) х ! <О ыг >О ых еХ (23) Интегрируем это неравенство на отрезке [в, г] ь 2 ( ]х(г)! йг+ ]х(!) — х,]г < ]х(т) — ж„]г Ыг > т > О, Ых, Е Х,, Это означает, что функция ]х(!) — х„! не возрастает при всех х„с Х,.
В частности, при г т = 0 отсюда имеем; ]х(!) — х„! < ]хо — х„], так что траектория (х(!), г > О) ограничена и, кРоме того, 1 ]х(г)! дг < со. ОтсюДа слеДУет сУЩествование послеДовательности (гь) — ь шоо о такой, что (х(г,))-ьО, (х(гь)) — ьв„, (п(г ))-ь п, 0< у < и < у . Так как Х вЂ” замкнутое Мисжсетза, Х(г) + Х(г) Е Х, та Я(г )+ Х(г )-ь Е„С Х. ЯаЛЕЕ В (22) ПЕрЕйдЕМ К ПрЕдЕЛу Прн ! = гь — ьоо. УчитываЯ, что 1!ш У"(х(гь)+х(гь)) >У(в„), полУчим 0< и (У(л) — У(в„)) ыл ах. Это значит, что в„еХ,. Тогда функция ]х(!) — в„]г не возрастает. Потому 1пп ]ж(г) — е,]г= ь о = бш ]х(гь) — в„!э=О, т. е, пш х(г)=всю Наконец, из неравенства (23) при х„=в„имеем ]х(г)]г ( — (х(!), х(!) — в„) < ]ж(!)! ° ]х(г) — в„! или ]х(г)! < ]х(г) — е,! Ыг > О, Отсюда следует, что 1пп х(г) = О.
Теорема б доказана. О Для сильно выпуклых функций у(х) можно получить следующую оценку скорости сходи- мости метода (21). Теорема 7. Пусть множество Х и функция 7(х) удовлетворяют условиям теорем 3, 4, функцил у(х) сильно вььлукла с постоянной сильной выпуклости к > О, функцил п(г) > 0 непрерььвна и 1 — [ — ") — йт =+со, пусть х(г), г > О, — любая травкторил систвмьь (21). Тогда о " п(т)" ь ]х(г) — х,! < ]х(0) — х„! ехр( — 1 — — — 2[ — ) — йт) Ыг > О.
(24) о + До каза тел ь от в о. Иэ теоремы 4.3.1 следует, что задача (1) имеет, притом единствен. ное, решение х„и — "]л — *,!' < 7(х) — у(х„) Ых С Х. (25) Функция ьр(ль х, п(г)) сильно выпукла на Х с постоянной сильной выпуклости 1+ п(г)х и из (20), (21) имеем пг(1+п(г)х)]х-(х(г)цх(!))]г < х(л, х(г),п(!))-уо(х(г)-Ьх(!), х(г),п(!)), г > О. (26) 284 г . 5. методы минимизйции Функций многих пеРеменных В (25) положим з = З(г) + х(г), умножим на п(г) > 0 и сложим с (26) при х = х„. Получим 2(1+2а(г)х)([х(г)[ +[х(г)-х„[ +2(х(г),х(г)-х,)) < 2[э(г)-х,[ -2[э(г)[, г > 0 з [ ( ) [г „2п(г)х [ (г),[г<0 г>0, Зг " 1+ 2х(г)х или йг ([х(г) — х„[ехр(1 — +) — зт)) < О, г >в О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
