Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 80
Текст из файла (страница 80)
3) Другой способ выбора а,: при /ь(х ) > 0 полагают а, = О, а если Д„(х„) < О, то аь = Ль, где ь', — минимальйый номеР сРеди номеРов 4 > О, удовлетворяющих условию ! 7(х„) — 7(ха+ Л'(х„— х„)) > Л'г~~(хь) !, Ж! где Л, г — параметры метода, 0 < Л; а < 1. 4) Величины а, в (5) можно априорно задавать из 7 условий !783] 0 < аь <1, 1!ш а„=О, ~" а„=со, а=а например, а„= ()4 + 1) ', й = О, 1,... Такой выбор а„очень прост для реализации на ЭВМ, но, вообще говоря, не гарантирует выполнение условия моно- Рис. З.б тонности /(х,+,) < /(х„).
5) Возможны и другие способы выбора аь в (5). Например, можно задавать а, = 1 и проверять условие монотонности /(х„~!) < /(х„), а затем при необходимости дробить а„ до тех пор, пока не выполнится условие монотонности. На рис. 5.6 поясняется геометрический смысл метода (3), (5) в двумерном случае. 267 4 4. МЕТОД УСЛОВНОГО ГРАДИЕНТА (13) (15) (16) й Е Хо> (23) гьо Е 266 Гл. в. метоДы минимизАЦии ФУнкыий мнОГих пеРеменных 2. Рассмотрим теперь сходимость метода (4), (5), (9). Т е о р е м а 1. Пусть Х вЂ” выпуклое замкнутое ограниченное множество из Я", функция /(х) е С" (Х). Тогда при любом выборе хо е Х для последовательности (х ), определяемой условиями (4), (5), (9), справедливы равенства 1пп (/7(хг), х„— х,) =О, !пп р(х„, Я„) =О, где Я, = Тх: х Е Х, (/'(х), о — х) > 0 при всех г> Е Х), Если, кроме перечисленных условий, /(х) вьспукла на Х и г„+6,(С,й ", С,=сонэ!>О, 1/2<р(1, (14) то 1пп /(хг) =/„, !пп р(х„Х,) =О, и справедлива оценка 0</(х„) — /,<Сй о, Й=1,2,...; С,=сапа!>О Наконец, если, кроме того, /(х) сильно выпукла на Х, то х !г < (2С /х)й-о Й 1 2 (17) Д о к а з а т е л ь с т в о.
При сделанных предположениях /„> — со, Х, ф О. Так как множество Х ограничено, то впр !и — о) < д <оо. Из условия (9) ч>ох следует /(х, с) = д,(а„) < д, + 6„< /(х„+ а(хг — х,)) + б, при всех а, 0 < а < 1. Поэтому пользуясь неравенством (2.6.7), имеем /(х„) — /(х„+,)+6, ~ )/(хь) — /(хо+а(х„— *„)) ~ )— сг(/'(х,.)> *,— *„)— — агЬ)х — х !г/2 > — а/'(х„) — агЬс!г/2, 0< а (1, й =0,1,... (18) Множество Аг = ТО, 1,2,...) разобьем на два множества 71>+ = (й: й е Е1г', (/'(х„),х, — х„) >0) и Ж =1ч''1Ф+.
Так как !и1/,(х) </„(х,) =О, то из (4) получаем 0 < Ях„) < г, при всех й Е 1г'+. Поэтому если )г7+— бесконечное множество, то /г(х„) — 0 при й — оо, й Е Ф~. Теперь пусть й Е ссГ > Тогда из (18) имеем О( — Л( 'о) ((/(хг) — /(х„+с)+ б )/а+ а7„р/2 (19) пРи всех а, 0 < а < 1, Й Е !г' . Далее, из (9) следует, что /(х„, ) < /(, ) „ + б„, й = 0; 1,... Так как /(х,) > /„> — оо, й = О, 1,..., то из леммы 2.6.2 вытекает существование конечного предела !пп /(х„) > /,. Следовательно, 1пп (г( )— 'ш („г(х„) — /(х„г,)) =О. Если Аà — бесконечное множество, то при й - оо, й е !г, из (19) имеем 0 ~~ !пп (Я,(хо)>! < 1!ш (/„(х )) < а5 рг/2 при всех а, 0 < а < 1. Устремляя а — +О, отсюда получим /г(х„) — 0 при й — > оо, й ~ !У .
Объединяя оба случая й е АГ> и й е !г, приходим к первому равенству (13). Так как Х ограничено н (х„) е Х, то последовательность (х,) имеет хотя бы одну предельную точку. Пусть х,— произвольная предельная точка (х„), пусть (хг ) - х„. Согласно (4) ймеем /„(хь) — г < 1и!/„(х) < (/'(хг), х — хг) пРи всех х Е Х и й =О, 1,... х Отсюда при й = й — оо с учетом первого равенства (13) получим, что (/'(х,), х — х,) > 0 при всех х Е Х. Тем самым показано, что любая предельная точка последовательности (х„) принадлежит Я,. Отсюда следуют вто ое равенство (13).
Х усть теперь /(х) выпукла на Х и х„— произвольная точка из Х,. Тогда нз теоремы 4.2.2 и условия (4) имеем * 0 < а = /(хь) — /(х>) ~ ((/'(хг)> хг — х,) = = †/г(х„) < — ппп /„(х) < †/о(хг) + гсо Й = О, 1,...
(20) х Отсюда и из первого равенства (13) следует !пп /(хь) =/„т. е. (хг)— минимизирующая последовательность. Из теоремы 2.1.1 тогда получаем !!ш р(хсо Х.) = О. Равенства (15) доказаны. Заметим, что неравенство (20) г может служить полезной апостериорной оценкой при практическом использовании метода (4), (5), (9). Остается получить оценку (16). Для этого множество АГ = (0,1, 2,...) разобьем на два множества 7о = (й: Й Е А>, аь > г„), 7> = (й: й Е М, 0 < а„< < г,).
Из оценки 0 < аг — гг < — /„(х„), Й с го, (21) являющейся следствием неравенства (20), следует, что 7о С 1с7-. Поэтому (18) можно переписать в виде > а~/ (х )) — агЬс!г/2 — б,, 0~ (а ~(1, й Е/о. (22) (13) (с/,(х„)с) ограничена, то, взяв при необходимости с! еще большим, можем сделать 0< сг„= !/,(хг)!с! гЬ ' < 1 при всех й =О, 1,... Принимая в (22) а = сг„, получим а„— а„„, > 1/(27>с(г)>с/г(х )>сг бо !о е 7о Отсюда и из (21) с учетом условия (14) имеем а„г, ( а„— (а, — г„)г/(25сР)+ б ( а„— агг/(27 с(г) + +(вира)Ь сс! гг +6 <а — а,/А+Ай где А = спахС25с>>г. (внР а„)Ь 'с( Со' Со). ьао Если й е Хо то 0 < а„< г < С й го.
Кроме того, из (18) при а — +О полУчим аь — а„„, + 6„) 0 или аг „, < а„+ б„< а„+ С й-гг дла всех й = =О, 1,... Таким образом, последовательность (а,) удовлетворяет условиям леммы 2.6.5, из которой следует оценка (16). 269 5 4. МЕТОД УСЛОВНОГО ГРАДИЕНТА 0</(х!) — /,<Сзй Р, й=1,2,... (34) /(хь) — /(хь !) ) О, (27) Упражнения э из (4) следует ооь < зпР а„а„< Сза,, й =О, 1, 2 ьэо (29) (31) (32) 268 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Наконец, оценка (17) вытекает из неравенства (4.3.3) и оценки (16), Теорема 1 доказана. ьй 3.
Исследуем сходимость методе (4), (5), (! 0). Т е о р е м з 2. Пусть Х вЂ” зь!ауклое замкнутое ограниченное множество из Е", функция /(х) принадлежит С! >(Х), Тогда ари любом хо е Х длл последовательности (х ), определяемой услозилми (4), (5), (! 0), сараеедлигы равенства (13). Если, кроме я!ого /(х) зотукла на Х, то имеют место равенства (15), а при гь < Сей ~г, Со — — сопз1>0, 0< р< 1, верна оценка (16). /Тлл сильна выпуклой функции слраггдлйга оценка (17). Д оке зете л ьс тэ о. Тек же, кзк нерзэенстео (!8), нетрудно показать, что /(хь) — /(хь !) ) -оь/ь(хь) — аьхь'!хь — хе!~/2, й = О, 1,...
(24) В соответствии с формулой (10), определяющей зеличину аь рассмотрим три зозможных случая: 1) Если /ь(хь) < О, ооь — — 1 < рь !/ь(хь ЩХь — хь ) 2, то из (24) с учетом (11) имеем /(хь) — /(хь о !) и )(/ь(хь)! — 5 рь(/ь(хь))/2 )и г)/ь(хь И.
(25) 2) Если /ь(*ь) (О 'гь = рь!/ь(хь)!!хь хь~ <1, то из (24) с учетом (11) получаем /(хь) — /(х,,)) рь)/ь(хь)!2!хь — х„Г2 — Ерз!/ь(х Из!х х Гз/2= = !/ь(хьИ !хь — хь1 рь(1 — Ерь/2) > !/ь(хь)! д хгог, д > зир !и — и!. (26) и ех 3) Нзконец, если /ь (хь) > О, то согласно (10) и из (24) имеем 0 < /ь(хь) < г,, (28) Из (25)-(27) вытекает, что последовательность (/(хь)) не еоэрзстзет. Тзк кэк /(хь) > /, > > — оо, то существует !!ш /(хь) ) /, и, следовательно, 1!ш (/(хь) — /(хь !)) = О. Отсюда ьь ь+! и из (25), (26), (28) имеем 0 ( !/ (хе И ( шэх(гь! сопз1 (/(хь) — /(хе о !))'/2) о О при всех й оса.
Первое из равенств (13) доказана. Второе равенство (13) устанавливается тзк же, кзк э теореме 1. Пусть теперь функция /(х) выпукла нз Х . Тогда справедлива цепочка неравенств (20), из которой следуют равенства (15), Предполагая, что еь < С й 2", 0 < р (1, докажем оценку (16).
ПРедеэРительно эзметим, что 0 < аь — — /(хь) — /„< зиР (х) — /„= Сз < оо, поэтомУ * х Еще рзэ переберем рзссмотренные выше три возможности. 1) Если /ь(х ) (О, аь — — 1 < рь!!/ь(хь)йхь — хь! 2, то из (20), (25), (29) имеем а — а > > гаь — ззь или ь ь+! аз + ! < аь — гаь + згь ( а, — а (г/С ) .!. гС й-2а 2 (30) ) у /ь( ь) < аь = рь!гь(хь)йхь хь~ < 1. Здесь, э свою очередь, имеются дзе возможности: аь > г! или 0(аь < гь. Если аь ) гь, то из (20), (26), 0 < а < С получим 2 -2 2 -2 — 2 Ь 2 аь — аь+! >(а! — гь) д гог>аьд гог — 2Сзгьд еог или аь „! < аь — азь (г г/дз)+ 2сзгогд зс й Если же 0 и аь < гь, то достаточно воспользоватьсЯ более пРостым следствием (26):, < :аь !.
аь Последние дэз нерзэенстэз можно переписать з виде О ( аь ( Сей ~г, аь „! < а! ( аь 4 Сей 3) Наконец, пусть /ь(хь) > О, аь — — О. Тогда из (20), (27) получим 0 < аь < еь, а + ! < аь что снова приведет к нерзэенстээм (32). Из (30)-(32) следует, что последовательность (аь) удовлетворяет условиям леммы 2.6.5, нз которой получаем оценху (16), Теорема 2 докзззнз. С! 4. Наконец, рассмотрим эзризнт метода условного градиента (4),(5),(!2) 1783].
Теореме 3. Пусть Х вЂ” выпуклое замкнутое ограниченноемножестго изЕ", функция /(х) Е С!' (Х) и выпукла на Х. Тогда при любом хо е Х длл аоследозательности (х ), определяемой условиями (4), (5), (12), сарагедлигы равенства (!5). Если при этом аз =(й о 1Г гь =Се(й+ !Г й =0 1 ° ° то О</(хь) — /, <Сг!п(й+1)/й, й=1,2,..о (33) а если аь =(й+ 1) р гь = Се(й+ 1) р й =0 1 0< р <1 то здесь Сз, Сч — некоторые полохоительнь!е постоянные. До к э з з тельст эо. Заметим, что неравенства (20), (24) не зависят от способа выбора а, 0 < аь (1, з (5), поэтому сохраняют силу и з рэссмзтриэземом случае. Из них имеем а! — аь ! > аь(аь — гь) — аьЬд /2 или 2 2 аз+! < (1 — аь)ах+а~~Ей~/2+ аьгь, й =О, 1,... Отсюда с учетом свойств последовательностей (аь), (г ) из (4), (12) заключаем, что (а„) удоэлетэоряет условиям леммы 2.6.6.
Поэтому (ип аь — — 0 или 1йп /(хь) = /,, Отсюда и из Ь оо Ь оо теоремы 2.1.1 получаем равенства (15). Оценки (ЗЗ), (34) следуют из лемм 2.6.8, 2.6.9. 1. Вычислить несколько итераций метода (3), (5), (6) для функции /(и) = х + ху+ у при 2 2 и 6х = (и= (х у) без: 0(х < 1, -! < у <О), выбирая ио — — (1, — 1), (-1,0), (1,0) или (О О). 2. Для функции из примера 1 проверить выполнение условий теорем 1-3 и сформулировать условия сходимости соответствующих вариантов методе условного градиента.
3. Деть описание различных вариантов метода условного градиента для функции /(х) = = !Ах — Ь1~, где А — матрица га х и, Ь е Е"", з множество Х является шаром или перзлле. лепипедом. Опираясь нэ теоремы 1-3, доказать сходимость метода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
