Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 85
Текст из файла (страница 85)
Получим (- ) *- 1 с 2 ! 2 1 2 ! 2 + пх)[хс хе+ с[ < 2 [зс жь[ 2[хе+с хь[ < 2 [ею хь[ й Ос |с Отсюда следует, что [к „вЂ” х [2([х — х [24([х — х[242( ..([хо — х [яда+С, й=0,1,... Оценка (17) доказана. Гз Отметим, что если функция 7'(з) дифференцируема на Х, то теоремы 4, 5 сохраняют силу и для метода (!4). 2. Опишем непрерывный вариант проксимального метода, следуя [251. Рассмотрим задачу ус(г,х,п(с)) = 2[г — ж[ + п(с)7(г) ю |п1, г е х, (20) где п(С) > 0 суС > О, Х вЂ” выпуклое замкнутое множество, У"(х) выпукла на Х. Тогда ус(г,х,п(С)) сильно выпукла с постоянной сильной выпуклости х = ! и по теореме 4.3.1 задача (20) имеет, притом единственное, решение г = рг(х,п(С)). Введем систему дифференциальных уравнений й(С) = рг(з(С),п(С)) — х(С), С > О.
(21) '.Ле[с7 $6. ПРОКСИМАЛЬНЫЙ МЕТОД Согласно теореме 1 решение з, задачи (1) удовлетворяет уравнению рг (ж„, п(С)) — х, = 0 при 'тС > О. Это значит, что каждая точка х„е Х, является точкой равновесия (стационарным решением) системы (21). Можно ожидать, что йри некоторых требованиях на функции у(з), п(С) траектории ж(С) системы (21) при больших С приближаются ко множеству Х,. Справедлива Те ор е ма 6 (Антипин [25!).
Пусть множество Х и функция У(х) удовлетворяют условиям теорем 3,4, функция п(с) непрерывна и 0< ге < п(с) < тс чс > О. тогда траектория х(С) системьс (21), гьсходясцая иэ любой точки з(0) = жо, определена при всех С >0 и сходится при с — с -1-со к некоторой точке о„= о,(хо) е х„кроме того, иш х(с) = О. с сю Доказательство.
В силу теорем 2, 3 правая часть рг(х,п(С)) — х уравнения (2!) удовлетворяет условию Липшица по з и непрерывна по С, потому все решения системы (21) определены при всех С ) 0 (см. ниже теорему 6.1.!). В силу уравнения (21) имеем рг(х(С), сс(С)) = й(С)+ з(С) Е Х и по теореме 63.1 'Ф[ — [г — рг(х(С), п(С))[ = — [г — (х(С) +ж(С))[ < ус(г, ж(С), п(С))— 1 2 1 — ус(рг(х(С), п(С)), х(С), п(С)) = — [г — ж(С)[ — -[(х(С) + з(С)) — ж(С)[2+ + п(С)(С'(г) — у(В(С)+ х(С))) ссг Е Х, С > О.
(22) Полагая в (22) г = х, Е Х„, с учетом неравенств у(х) — у(х(С)+ х(С)) < О, п(С) > 0 получим [з(С) + х(С) — ж [ = [я(С)[ + [ж(С) — ж [ -1-2(ж(С), х(С) — х ) < [з(С) — х [ †(С)[ .';1:,.-': 283 или 2 [х(с)[2+ 2 3-[з(с) — х[2 < 0 чс >О, суз„е х,.
(23) Интегрируем это неравенство на отрезке [т, С[ с 2) [В(г)[ да+ [х(С) — з„[ < [з(т) — х,[2 2СС > т > О, ссхс Е Х,, Это означает, что функция [х(С) — х,[ не возрастает при всех х„ Е Х„, В частности, при 2 т = 0 отсюда имеем: [з(с) — х,[2 ( [хо — х,[2, так что траектория (ж(с), с > О) ограничена и, КРОМЕ ТОГО, [ [Х(С)[ дС < СО. ОтСЮда СЛЕдуЕт Сущсетааеаинс ПОСЛЕдОВатЕЛЬНОСтИ (СС) -с+СЮ о такси, что [х(с;)) — со, (х(сс))-со„, (п(с.)) — си, 0< г < и < г. так как х — замкнутое множество, й(С) + ж(С) Е Х, то х(С )+ х(С ) — с ю„Е Х.
Далее в (22~ перейдем к пределу прн с = с, — с со. учитывая, что 1пп 7(з[сс)+х(сс)) >у(о), получим 0 < п (г(г)-7(о)) сух еХ. с:ю это значит, что о, ех„. тогда функция [х(с) — о,[2 не возрастает. потому 1!ш [х(с) — о,[2= С сю = |пп [х(С ) — о [ = О, т, е, 1ип з(С) = о,. Наконец, из неравенства (23) при х, = о, имеем ю с с С сю [х(С)[ < -(х(С), х(С) — о ) < [х(С)[ ° [з(С) — о [ или [й(С)[ ( [х(С) — о [ ЧС )~ О, Отсюда следует, что |пп х(С) = О. Теорема 6 доказана. С| Для сильно выпуклых функций 7(з) можно получить следующую оценку скорости сходи- мости метода (21). Теорема У. Пусть множество Х и функция 7(х) удовлетворяют условиям теорем 3, 4, функция у(х) сильно выпукла с постоянной сильной выпуклости х > О, функция п(С) >О непрерывна и [ и дт= Есо, пусть х(с), с ) 0„— любая траектория сип|т! стемы (21).
Тогда о + п(т)" С [х(С) — х,[ < [х(0) — х„[ехр( — [ — — 2(-) — дт) сссС >О. (24) о 1+2п(т)х Доказательство. Из теоремы 4.3.1 следует, что задача (1) имеет, притом единствен. нос, решение х, и 2[к — х [ ~ (7(г) — 7(з„) СУг е Х. (25) Функция ю(г, х, п(С)) сильно выпукла на Х с постоянной сильной выпуклости 1+ п(С)х и из (20), (21) имеем -(1+п(С)х)[г-(з(С)+х(С))[ < зс(г х(С)сп(С))-зс(х(С)+х(С) х(С) п(С)) С > 0 (26) ст Упражнения 3 7.
Метод линеаризации (б) д,(х) < О,, дж(х) <0; (8) дз(кь) + (ду(хь), к — хз) < д;(л) «ук Е Хо. 284 Гл. 5. МЕТОДЫ МИНИМИЗАПИИ ФУН1ЯИИ МНОГИХ ПЕРЕМЕННЫХ В (25) положим к = В(З)+ к(!), Умножим на п(З) > О и сложим с (26) пРи к= ам ПолУчим -(!42*(!)' )Ом(зи +1 (з) — ') +2(*(з) к(!) — *)) <-1 (1) —;! — -! (!)! ! >О или « — „()к(!) — к«) ехр() — — ф)~ — г1т)) < О, з > О. 1 + 2««(т)к Интегрируя это неравенство иа отрезке 10, 11, придем к оценке (24). гз Замечание 2. При о(З) ш «х =сопз! >0 требование условия Липшица от функции 7(л) в теоремах 6, 7 излишне. Зто требование нужно было в теореме 3 при доказательстве непрерывности рг(ж о) по совокупности (а,а), что в свою очередь обеспечивало непрерывность правой части системы (21) по З и продолжимость траекторий я(З) на всю полуось ! > О.
Однако при о(!) ш г«правая часть (2!) от з ие зависит и для продал«кимости траектории достаточно условия (9), Замечание 3. При доказательстве теорем 4-7 для нас не было существенно, каким методом решаются вспомогательные задачи (3),(13),(20) для определения значений проксимального оператора в требуемых точках (к,п). Однако ясно, что проксимальный метод имеет смь«сл применять лишь тогда, когда ил«естся удобный быстро сходящийся метод для решения упомянутых вспомогательных задач. В этих задачах, а отличие от исходной задачи (1), минимизируемая функция сильно выпукла благодаря слагаемому — )з — х~, что обеспечивает их 1 з одноэначиу«о разрешимость и, можно надеяться, улучшает схо3«мость используемых методов их решения, повышает устойчивость этих методов к погрешностям вычислений, Различные варианты проксимального метода, вычислительные аспекты этого метода исследованы, напри.
мер, в 125; 26; 30; 799; 803; 813]. В следующем параграфе рассматривается метод, который можно истолковать как некоторое развитие проксимального метода. 1. Реализовать один шаг проксимального метода для задач из упражнений 4.6.1, 4.6.3, 5,2 5.3 при различных начальных приближениях. 2. Опираясь иа теоремы 1-3, доказать, что проксимальный оператор является монотонным аамкнутым, компактным отобрахзением. Этот метод на каждой итерации использует линейные аппроксимации минимизируемой функции н функций, задающих ограничения.
Опишем его для задачи Дх) — «(п1, х юХ =(х ЕХо: д,(х) <О,...,д (х) <0), (1) предполагая, что Хо — выпуклое замкнутое множество из Е" и функции 7'(х), д,(х) ш С'(Хо). ПУсть хо — начальное пРиближение, х Е Х . ПРедположим, что )с-е приближение х, е Х, при некотором к > 0 уже известно. Введем функцию Ф,(*) — -!* — х 1~+ ~ь(7'(~„), * — хь), сть О, ! (2) и множество Игь =(хЕ Хо: дг(хь)+(д,'(хь), х — х„) <О, з =1,..., тг.
(3) Пусть Игь ~Я. В качестве )с + 1-го приближения хь„, возьмем решение следующей задачи минимизации: Фь(х) — «!п1, х Е Игь. (4) $7. МЕТОД ЛИНЕАРИЗА!!ИИ 285 Поскольку функция (2) сильно выпукла, множество (3) выпукло и замкнуто, то согласно теореме 4.3.1 задача (4) имеет, притом единственное, решение. Задачу (4) необязательно решать точно: достаточно найти точку х„, из условий х ейг: Ф х (1п1Ф (х +е., еь>0. (5) ь( ° ) ь ) Если Х, многогранное множество, то задача (4) представляет собой задачу квадратичного программирования и может быть решена конечношаговым методом (см, ниже $7).
Если Игь — ограниченное множество, то для решения задачи (4) может быть использован, например, метод условного градиента, который будет сходиться и при е„ > 0 позволит определить точку х„„, из (5) за конечное число шагов. В общем случае задача (5), конечно, не всегда просто решается. Метод линеаризации (5) обычно используют лишь в тех случаях, когда определение точки х,„, из (5) не требует большого объема вычислений. Полезно заметить, что задача (4) равносильна задаче «рь(х) = 2)х — (х„— сть7'(хь)))' — «1П1« * Е И'„, так как «рь(х) — Фь(х) = схьз)7"'(хь)!з = сопз1, х е Е'. Это значит, что точное решение пь задачи (4) представляет собой проекцию точки х„— ст ~'(хь) на множество И'„, а точка х, „, из (5) является приближением для пь.
Отсюда следует, что если в (1) ограничения д,.(х) < 0 отсутствуют (т =0), то Х = = Х, = Игь и метод линеаризации превратится в метод проекции градиента. Т е о р е м а 1. Пусть Х вЂ” выпуклое замкнутое множество из Е", ш1 Х ~ И (в частности, возможно Хо — — Е"); функции 7(х), дз(х) е е С'(Хо), выпуклы на Хо и тахЯси) — 7'(и)(; !пах )ду(ы) — д (и)!эг ( Ь |ы — Ч «гы«т«Е Хо' ! к «< ч« выполнено условие Слейтера, т.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
