Ф.П. Васильев - Методы оптимизации (1125241), страница 85
Текст из файла (страница 85)
1+ 2о (т)х Интегрируя это неравенство на отрезке [О, 11, придем к оценке (24). П Замечание 2. При п(г) ю и =сонэ! >0 требование условия Липшица от функции 7(х) в теоремах 6, 7 излишне. Зто требование нужно было в теореме 3 при доказательстве непрерывности рг(х,х) по совокупности (х,п), что в свою очередь обеспечивало непрерывность правой части системы (21) по г и продолжимость траекторий х(г) на всю полуось г > О. Однако при п(г)ш х правая часть (21) от г не зависит и для продолжимости траектории достаточно условия (9).
3 а и е ч а н и е 3. При доказательстве теорем 4-7 для нас не было существенно, каким методом решаются вспомогательные задачи (З),(13), (20) для определения значений проксимального оператора в требуемых точках (х„п). Однако ясно, что проксимальный метод имеет смысл применять лишь тогда, когда имеется удобный быстро сходящийся метод для решения упомянутых вспомогательных задач. В этих задачах, в отличие от исходной задачи (!), минимизируемая функция сильно выпукла благодаря слагаемому [э — х[, что обеспечивает их 1 однозначную разрешимость и, можно надеяться, улучшает сход»месть используемых методов их решения, повышает устойчивость этих методов к погрешностям вычислений. Различные варианты проксимального метода, вычислительные аспекты этого метода исследованы, например, в 125; 26; 30; 799; 803; 8! 31.
В следующем параграфе рассматривается метод, который можно истолковать как некоторое развитие проксимального метода. Упражнении 1. Реализовать один шаг проксимального метода для задач из упра»снений 4.6.1, 4.6.3, 5.2 5,3 при различных начальных приближениях.
2. Опираясь на теоремы! -3, доказать, что проксимальный оператор является монотонным замкнутым, компактным отображением. 9 7. Метод линеаризации Этот метод на каждой итерации использует линейные аппроксимации минимизируемой функции и функций, задающих ограничения. Опишем его для задачи ,7(х)т[п[, хюХ=(хюХо: д(х)<О,...,д (х) <О), (1) предполагая, что Хо — выпуклое замкнутое множество из Е" и функции У(х), дг(х) ю С'(Хо). Пусть х — начальное приближение, х е Х, Предполо>ким, что )с-е приближение хь е Х, при некотором )с > 0 уже известно.
Введем функцию ! Ф„(х)= 2~х — хь~ + сгь(7'(хь), х — х„), сгь >О, (2) и множество И'„= (х Е Хо. д,(х„) + (д,'(хь), х — хь) < О, г = 1,..., пг). (3) Пусть И'г ~ И. В качестве А + 1-го приближения х,„, возьмем решение следующей задачи минимизации; Ф„(х) — ~ 1П[, х Е Игь.
(4) у х, е Игь: Ф (х,) ( т[Ф„(х) + е„, г„> О. (5) н; Если Х, многогранное множество, то задача (4) представляет собой задачу квадратичного программирования и может быть решена конечношаговым методом (см. ниже $7). Если И' — ограниченное множество, то для решения задачи (4) может быть использован, например, метод условного градиента, который будет сходиться и при е„> 0 позволит определить точку х„„, из (5) за конечное число шагов, В общем случае задача (5), конечно, не всегда просто решается. Метод линеаризации (5) обычно используют лишь в тех случаях, когда определение точки х„, из (5) не требует большого объема вычислений. Полезно заметить, что задача (4) равносильна задаче (оь(х) = — [х — (хь — гг 7" (х ))[~ — ь >п( х ю Игь, так как р (х) — Ф.(х) = стэг[7"(хь)[г =сопз1, х е Е".
Это значит, что точное решение пь задачй (4) представляет собой проекцию точки х„— сгь7'(хь) на множество И'„, а точка х„,, из (5) является приближением для нь. Отсюда следует, что если в (1) ограничения д,(х) < 0 отсутствуют (тп =0), то Х = = Х, = Иь и метод линеаризации превратится в метод проекции градиента.
Т е о р е м а 1. Пусть Хо — выпуклое замкнутое множество из Е", !п( Хо ~ И (е частности, возможно Х, = Е"); функ>4ии,)'(х), дг(х) Е е С'(Хо), выпуклы на Хо и тахЯси) — Г(п)[; так [ду(и) — д,.'(пЦ ~ ~Ь !и — п~ туз, " ~ Хо) выполнено условие Слейтера, т. е. существует такая точка хе Х, что , (8) д,(х) < О,..., дх(х) <0; 7; >-со, Х. фИ; числа сг„, е. з (2),(5) такоеьг, что еь >О, Я г/еь <оо, 0<То(схь (сг, (7) ь=о где сг определяется ниже формулой (22).
7огда множество (3) непусто при всех й > О, последовательность (х„), определяемая методом (5), сходится к некоторой точке и, ~ Х,. До к аз а те л ьст во, Согласно теореме 4,2 2 дг(хь)+ (дд(хь), х — хь) < дг(х) »хе хо. (8) Отсюда следует, что если х Е Х, то х Е Иь, так что Х с Иь. По условию Х ф Я, поэтому Игь ~ Я, й = О, 1,.... Таким образом, при каждом Ь ~ )О, сь В >0 существует точка хь „!, удовлетворяющая условиям (5); например, можно взять хь „! — — оь, где хэ — точное решение задачи (4). Применяя теорему 4 3! к задаче (4) с учетом (5) имеем [хь „!-оь[ /2 Ф<Фз(хь+ !)- — Фь(еь) < еь, так что [х „! — х [< /2зь, (9) 4 7.
МЕТОД ЛИНЕАРИЗАЦИИ 285 Поскольку функция (2) сильно выпукла, множество (3) выпукло и замкнуто, то согласно теореме 4.3.1 задача (4) имеет, притом единственное, решение. Задачу (4) необязательно решать точно: достаточно найти точку х„, из словий '1"с 286 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ $7. МЕТОД ЛИНЕАРИЗАЦИИ Сложим оценки (17)-(20); с помощью (! 6) получим О 2!хй — .[ --[,-*,[ — [ „-,! (1- Ь,-ЦЛ [, й). Выберем ссй иэ условий 21— Х(1+ 2[Л [1) (21) (22) Возьмем произвольную точку х, Е Х„.
При сделанных предположениях по теореме 4.9.2 и лемме 4,9.2 найдутся такие числа Л,' ) О,, Л" > О, что (/'(х,)+ Х; Л;.д/(х,), х — х,) >0 !ух Е ХО, (10) 1 — 1 Л,".дз (х ) = О, 1 = 1, .. с пс, х„Е Х . (11) Подчеркнем, что в силу замечания, сделанного после формулировки следствия 2 к теореме 4.9.5, числа Л»1,..., Л' в (10), (!!) могут быть выбраны одни и те же для всех х, е Х,. Далее, иэ условия (6) и неравенств (8) следует ду(хй) + (дйс(х„), д — х,) < д;(ж) < О, 1 = 1,..., т. (12) Это значит, что множество (3) также удовлетворяет условию Слейтера, и к задаче (4) также применима теорема 4.9,2, из которой следует, что функция Лагранжа этой задачи 81(х, «) = = 2[х — хй[ +ау(/(хй),х — вй)4- х «!(ду(хй)+(д!'(хй),х — хй)), хЕХО «(«1~ «»)Е '=1 ЕЛΠ— — Е"', ИМЕЕТ СЕдпазуЮ тОЧКу (Ей, «"), Ей — РЕШЕНИЕ ЗадаЧИ (4), «" =(«!й, ..
ч «й) ЕВ+ . В силу леммы 4.9,2 (ей — хй -1-ай/'(хй) 4- 2 ' «.йдр(хй), х — ей) 30 Ухехо, (13) '=1 «ь(д,(х )+(д (хй),е„— хй))=0, 1=1,...,т, (14) д1(хй)+ (д (хй) ей хй) < 0 $ = 1 ° ° т ей ЕХО ° (15) Возьмем в (10) х = ей, умножим на ай > 0 и сложим с (13) при х = х,. Получим 0 ( (ей — хй, х — ей) + ай(/'(х,) — /'(хй), ей — х ) -1- -1-ай ~; лг(д/(х,),ей — х,)+ ~; «!й(ду'(хй),х — ей).
(16) 1=1 с=1 Преобразуем и оценим каждое слагаемое в левой части (16). Для первого слагаемого имеем (ей хй, х, — ей) = 2[ха — *,[ — 2[ей — хй[ — 2[х, — ей[ (17) Пользуясь неравенством (4.2,20) прн и = хй, ю = ей, е = х„ получаем оценку для второго слагаемого ай(/'(х„) — /'(хй), ей — х,) < айй!хй — ей[э/4. (18) Далее из леммы 2 6 1 при /(ж) = д (х),х = ей, у = хй с учетом неравенств (15) имеем д (ей) < (д (хй)+ (д! (жу ), еу, — хй)+6[ха — ей[э/2 < 6[хй — ей[у/2 с =1, „пт, Отсюда для третьего слагаемого из (16) с помощью равенств (11), неравенств (8) при х = ей и Лсй > 0 получаем ай ~ Л'(дй (**) Ей **) = 1'й Д, Лу(д!(Хс) +(ду~(жс) Ей Хс)) < с =1 с=! т т < ай д Л,*д!(ей) < ай[Л'[1Ц[хй — ей[ /2, [Л*[! —— ~ [Л[[.
(19) 1=1 с=1 Наконец, для четвертого слагаемого иа (16) с учетом равенств (14), неравенств (8) при х = х„ включений х, Е Х, «Е Ж имеем т » «,й (у/(ха Л х — ей) = Л, [«!й(ду (хй ) + (д/(хй), х, — хй))— с=1 с=! — «сй(ду(жу)+ (ду(жй), Еу, — хй))[< ~; «уйд (Х ) <О. (20) *' = 1 где уо, у такие малые положительные числа, что ч!у < 2(1 — у)/(Х (1 + 2!Л*[! )), Из (21), (22) тогда имеем [ей — х !~ .1- у[о — х [з < )х — х [э, й = О, 1,...
(23) Иэ неравенств (7), (9), (23) и леммы 2.6.10 следует существование конечных пределов !нп !хй — х,[= 1пп !ей — х„[, !нп [хй — ей[тО. (24) й т * й сс й Зто значит, что последовательность (хй), (ей) ограничены. Покажем ограниченность после. довательности («й) из (13)-(15). С помощью (12), (14) из (13) прн х = д имеем сс т (Ей — Ха+ай/!(Хй), д-Ей) > — ~; «й(др(Хй), Х-Ей)т ~ [«уй(-д!(Хй) — (д/(жй), ж — Хй))+ с=1 с =1 +«а(уи( й)+(д'( 'й) Ей й))! > Е «Ш( д!(*)) ) «уй Г'!" !д!(*)! Уту 1<с<т Отсюда и иэ неравенств (22), ограниченности (хй) и (ей) получаем 0 < « .й ( .
. . [(ей — х1, .1- а„ /'(х,), д — е„)) < сопз1 < оо, у = 1,..., т. 1< '<т е — х с ( — йа — д+/(хй)+ х ай д (хй), ж — ей) )т0 !Ух ехо, 1=1 — йй(д.(хй)+(д; (хй),ей — хй))=0, 1=!,...,тп. (25) Выбирая при необходимости подпоследовательности из ограниченных последовательностей (хй), (ей), (« /ай), можем считать, что эти последовательности сходятся. С учетом (24) й 1нп хй —— 1нп ей — — ет !пп, =р,*>0, 1=1,...,т. й й,сс й Ив замкнутости Хо следует, что е, Е Хо, а из (15) при й с оо получим д (е ) < О, с = 1,..., гп, Следовательно, е„Е Х.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
