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