Ф.П. Васильев - Методы оптимизации (1125241), страница 77
Текст из файла (страница 77)
Положим в (35) тв = х„в (36) и = х(с)+ х(с) и сложим получившиеся неравенства. Будем иметь (х(1) + се(1)(ут(х(1)) — у'(х,)), х, — х(1) — х(1)) > 0 или !х(1)/х + (х(1), х(х ) — х„) + сг(1)(?в(х(1)) — (в(х )), х(1) — х ) + + се(1)(~'(х(1)) — ~'(х„))в х(1)) ~ (0 Чг )~ О, Чхв Е Х,. Отсюда с учетом неравенств сх(х) > О, (у"(х(х)) — !(х)), х(х) — х ) > 0 ьуг > 0 (теорема 4.2.4) имеем: (х(1)/Я+- — !х(1) — х„/з+ех(1) — „с(7(х(1)) — ?(х„) — (?'(х„)вх(1) — хв))(0 Чг)0. Интегрируя это неравенство на произвольном отрезке (т, 1), 1 > т > О, и, преобразуя интеграл от третьего слагаемого по частям, получим в 1 ~в 1 ) !х(в)~' в+ 2( (в) -;Г~ + а(в)(7(х(в)) - у(х.)— ~в=с в — ()"(х,), х(1) — х„))/ — 1 ех'(вЯ(х(в)) — 7(х,)— в= — (~'(х,)в х(в) — х.))дв ( 0 Ч1 ) т ~ )О, Чх„б Х..
Отсюда с учетом неравенств гх'(1) ( О, а(1) > О, (7'(х„), х(1) — х„) > 0 (теорема 4.2,3), Г(х(1)) — Г(х.) — (~'(х„), х(1) — х,) > 0 (теорема 4.2.2) имеем з( Ф( )Гдв+ 21*(в) М < 2~*(т) **Г+ ( )(вт(*( )) Х(М) ь?2 ) т ) Ов Чх. Е Хв. Из (3?) при т = 0 следует ) !х( )1 еь + 2!х(ь) — ~,)~ < 2) о —,('+ сх(0)(в'(хо) — в'(х,)) вь > О. о Отсюда заключаем, что траектория х(1) равномерно на 1 > 0 ограничена.
Кроме того, 1 (х(в)(яе!в < со, и поэтому найдется последовательность (1,.)— о — +со, для которой х(хв) — О. Кроме того, пользуясь теоремой Больцано— Вейерштрасса, можем считать, что последовательность (х(зх)) сходится к некоторой точке и„, Так как множество Х замкнуто, а х(х)+х(с) ЕХ Чй >О, то !!ш (х(1,)+х(2,))=п„е Х, Далее, переходя в (34) к пределу при 1 = ьв— оо с учетом непрерывности оператора проектирования (теорема 4.4.2), 1!пз се(гт) = сх(оо) > сх > О, полУчим ее О=? х(п, — о(с ) р(х,))- и..
(38) 288 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Согласно теореме 4.4.4 зто значит, что п, Е.Х., Полагая в (37) т = 81 и х, = п„имеем ! ]х(2) [2 < ! (х(1,) — и„! + ст(11)()(х(11)) — )(и,)) уй > Ь" Отсюда, переходя к пределу сначала при 1 — +ос, затем 1,. -++оо с учетом равенства ]пп х(11)=п„, получим: ]пп х(1)жт,. Тогда ]!пз 7(х(1))=)(п,)хх 1 э 1 ьо 1 а = 7",. Наконец, из уравнения (34) при Ь вЂ” +ос с учетом равенства (38) имеем: !пп х(Ь) =О. Теорема 6 доказана.
П Для сильно выпуклых функций можно доказать следующую оценку скорости схадимости метода (34) при а(2)ш ао — †сопз1 []: ]х(2) — х„! < ]х1 — х,! ЕХр(- ] Ь(т)дт)), о а 4 / аХ1 4 где Ь(т) = ар(1 — — ~) при 0 < а <, Ь(т) = аа(1 — 4 ) при а > т —. 4 ) 5+и' ( ) +и' При построении непрерывных методов проекции градиента могут быть использованы диф. ференциальные уравнения второго и более высокого порядков. Так, например, для выпуклых задач (1) в [25]исследована сходнмость процесса р(2)х(2)+х(2)+ХЯ=Р»(х(2)-а(2)7 (х(2)), 2 >0~ р(2) > Д! >О, и его двухшаговога дискретного аналога.
3 При Х = Еч метод (39) превращается в метод тяжелого шарика (1.49). Непрерывный и дискретный варианты методов более высокого порядка см., например, в [520-521! Упражнении 1. Вычислить несколько итераций метода проекции градиента при различных способах выбора аь в (2) для функции )( ) ( !)2+( „!)2 и с Х = Еэ = [и = (х, у) е Е: х > О, у ) 0). Рассмотреть начальные приближения ао — — (О, 0), аа = (О, 1), ао = (1, 0), ао = (1, 1). 2. Описать одну итерацию метода проекции градиента для функции (1.5), считая, что множества Х представляет собой шар, гиперплоскасть, параллелепипед, полупространство или положительный ортант (см.
примеры 4.4.1-4.4.6). Исследовать сходимость метода. 3, Рассмотреть метод проекции градиента для функции )(х) = !Ах — Ь], где А — матрица 2 порядка т х и, Ь Е Ех, считая, что множество Х имеет вид, описанныи в примерах 4.4.1- 4.4.6, Исследовать сходймость. ф 3. Метод проекции субградиента 1.
В рассмотренных выше градиентном методе и методе проекции градиента требовалась дифференцируемость минимизируемой функции. Однако для выпуклых функций указанные методы более естественно описать на языке субградиентов (см, $4.6). А именно, пусть Х— выпуклое замкнутое множество из Е", функция )(х) выпукла на Х и ее субдифференциал д)(х) непуст при всех х е Х. Тогда для приближенного решения задачи 7(х) -~1п1; х е Х, (1) можно предложить следующий итерационный метод: =р ( „— а с ), а,>0, сьедтг(хь), й=011 (2) где ха — некоторая точка из Х, а субградиент сь выбирается иа д)(хь) произвольным образом.
Если при некотором й окажется, что ха+ ! — — хь, то процесс (2) прекращается, так как в этом случае х„— решение задачи (1). В самом деле, при хь — — Р»(х — аз сь) согласно теореме 4.4.1 (хь — (хь — аьсь), х — хь) = (сь, х — хь)аь ) 0 или (сью х-хь) >О пРи всех х с Х, Отсюда из теоремы 4.6,4 следует, что хь е Х,.
Согласно замечанию 1 к теореме 4.6.4 точка х„с Х„тогда и только тогда, когда х, = = Р»(х, — ас.), а > О, где с„— некоторый элемент субдйфференциала д)(х„). Отсюда ясно, что итерационный процесс (2) представляет собой метод поиска неподви1кной точки оператора Р» (х — ас), с С д)(х). В там случае, когда функция 7" (х) дифференцируема во всех точках х Е Х, метод (2) паевращается в метод проекции градиента, а при Х = Е" — а градиентный метод, При выборе длины шага аь в (2) можно руководствоваться теми же саабрахгениями, которые были опи.
саны выше в $1, 2. Мы здесь ограничимся рассмотрением случая, когда аь в (2) выбирается из условий аз > О, й =0,1,...,' з„аэ — — аа, т», азз <оо. (3) ь=о ь-о Как уже отмечалось в 4 1, в качестве аэ можно взять аз — — С(й + 1), где С = сонэ! > О, 1)2 < а < 1; например, аь = (й+ 1) ', й = О, 1,...
Метод (2), (3) не гарайтирует выполнения условия монотонности у(ха) > )(хь,1) на каждой итерации и сходится, вообще говоря, медленна, но если проекция точки на мйожестве Х и субградиент сь с д)(хь) находятся несложно, то этот метод очень прост для реализации на ЗВМ.
Дока1кем его сходимость. Теорема 1 Пусть Х вЂ” выпуклое замкнутое множество из Е", функция )(Х1 определена и выпукла на некотором открытом выпуклом множестве И', садерз1сащем Т (например, И' = и" ). Пусть ), > — ао, множество Х„тачек миним ума )(х) на Х непусто и ограничено, и пусть, кроме того, зар зар !с! = А < оа (4) х е х г е эу!ч ! Говда последовательность (хь), определяемая условиями (2), (3), такова, что Зш У(хь) =Ух 1ап р(хьоХ,) =О. (5) Дока з а т ель с т в о. При сделанных предположениях функция )(х) непрерывна на Х, субдиф41еренцналы д)(х) непусты, выпуклы, замкнуты и ограничены при всех х с Х (см, те- оремы .2.15, 4,6.1, 4.6.2).
Из ограниченности множества Х„и теоремы 4.2.17 следует, что мнох<ество М(С) =[х сХ: )(х) < С) ограничено при любом С ) )„. Множество Х, выпукло и замкнуто в силу теоремы 4.2.1 и леммы 2.1,1, Согласно определению 4.4.1 проекции точки на множества и теореме 4.4,2 имеем зг Р (хь 1 Х )=]хь 1 Рх (ха+1)]2 < ]х. Рх (хь)]2=]Р»(хь ьс.) Рх(Р» (хь))]2 < < ]х„— аьса-Р» (х,)]2=р'(ха, Х„)+аз]сь !'-2аь(с„, х„-Р» (х„)) ~ь(~а~ха 1х(хь)) еаз!сь! +р (хь,х ) — р (х„,г,х ), й=о, 1, (6) ммируя неравенства (6) по й от 0 до некоторого з > 1, с учетом условий (3), (4) получим 2а„(сваха — Р» (х,)) <А 2 аьз+Р~(ха,Х„) — Р (хе+1,Х,)< < А ); аь~ + р~(ха, Х,) = В < аа, з = 1,2,...
(7) ь-а Далее, по определению субградиента имеем О < )(хь) — )„х У(хь) — 1(Р» (хь)) < (сь, хь — Ртг (хг,)), й = О, 1,... (8) Из (7),(8) следует, что числовой ряд или Су Е аа(сз, Х1, — Р» (ха)) ь=о с неотрицательными членами сходится Но согласно (3) имеем ч~ — . П ~~ а„= со. оэуому сходи. ь=о $3. МЕТОД ПРОЕКЦИИ СУБГРАДИЕНТА 289 .; з!,":. 261 9 3, МЕТОД ПРОЕКЦИИ СУБГРАДИЕНТА (9) Вгп (са хь Р» (х! )) О Р О Р Р зцр зцр )с!=л <Ою ь Е Х 0 Е ЬУ(о] О За(о] *3 оди- на; (10) 7(х)-+!и1! мех=(хе хо, д(х) <0), 260 Гл.
5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ мость предыдущего ряда возможна лишь при Вт (сь,х -Р» (ха))=0, Это значит, что суще Ь ж ствуют номера й(<йз«... Й„<... такие, что Тогда из (8) при й = й -Р со получим (пп 7(хз ) = 7„. Кроме того, из (8), (9) следует, что г Р 0 'Р 7(хь ) <Д+зиР(сь, х — Р (хз )) = С<со, т.
е. [хь ) ЕМ(С). Но М(С) огРаннчено, а (хь )— Р минимизирующая последовательность, поэтому из теоремы 2.1.2 имеем 5ш р(хь, Х,) =О. 00 Тем самым показано, что для подпоследовательности (хз ), удовлетворяющей условию (9), справедливы равенства (5). Опираясь на это, покажем, что равенства (5) имеют место для всей последовательности (хь) Иэ (3),(4),(6),(8) получаем, что ,2(. Х)<дз(х,,Х)+„2!с !2<уз(х„,Х)~.азлз, Й=О,] Это значит, что числовая последовательность аь — — р (хь, Х,), й =О, 1, .. О удовлетворяет усла.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
