Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 77
Текст из файла (страница 77)
(21) Возьмем произвольную точку х, Б Х„. Согласно теореме 4,2.3 тогда (/'(х ), х — х„) > О, х Б Х. (22) Из (20) и неравенства (4ги1) получаем (еь — хс -1- аь/'(хь), х — еь) >~ 0 Чх Б Х. (23) Положим в (23) х = х„а (22) умножим на ас > 0 и примем х = еь. Сложим получившиеся неравенства ( ь — хс, х„— еь) + аь (/'(хь ) — /'(*,), х„— е,) > О, й = О, 1 Преобразуем каждое слагаемое в правой части (24). Прелкде всего имеем 2(е„— х, х„— е„) = ]х„— х,] — ]хь — еь] — ]е — т.,! . г г Далее, воспользуемся неравенством (4.2.20) при и = хь, е = х„ ш = еь, получим (/с(х ) — /с(х ), х — е ) < (Ь/4)|х — е ]г й = О 1 Подставив (25), (26) в (24), получим ]хь — х„]г — ]еь — х,]г — (1 — а,Ь/2)]х — е ]г > 0 Отссода, учитывая условие (! 9), имеем !хь — х,] )м]ес — *,] + е]хь — еь]~, й =-0,1, (27) Далее, воспользуемся леммой 2 6 10 при г„= х„, г„= х„шь „, = е„; из (! 7), (2!), (27) и 1хь х]= 11ш ~сл — я|<со, йп )е — х ]=О, ь- ' ' ь ь * „ь ь Отсюда следует, что последовательность (хь) ограничена.
Тогда существует хотя бы одна предельная точка е, этой последовательности и подпоследовательность (хь ), сходящаяся к е,. Из (28) имеем 1пп еь —— е,. Согласно (23) с учетам (19) получаем (/ (хь), х — е„) > — (еь — хс, х — е„)о„) -]е — х ]]х — е ]г с — ! Отсюда при й = й л со будем иметь (/'(е ), х — е,) ) 0 при всех х Б Х. По теореме 4.2.3 тогда е, Б Х„. Вспомним, что неравенство (27) было получено для любой точки х„н Х . В частности,(27) верно и для х„ = е,.
Но е, — предельная точка последовательности (хс]. Из леммы 2.6.10 тогда следует, что (хь] сходится к е„. Теорема 4 доказана. С! где 0< Х. ра точ !хь — х,]г >]хь „! — х„1г+г]хь — хь с]г, й =О, 1,..., Чх„б Х,. )хь — е,]) !хь „! — е,), р(хь, Х ) > р(хь „с,Х,), Й =О, 1, ]г < ]х„— х ]г — ]х — х„]г -1- 2а (/~(хь) — / (х ), х, — хь с) = — х ]г — ]х — х — а(/'(х ) — /'(х ))]э+ ч.
ог]/ (хь) — / (х,)]г — 2о(/'(хь) — / (х„), хь — х ), Й = О, 1,... ]/(хь) — /(х,)] +Ьр]хь — х,$ <(Ь+р)(/(хь) — /(х,),хь — х,), й=0,1,... 257 $2, метод п) оекции грйдиентй ха+1 = жь — осел = (1 — и 5)хь рь „1 = рь — олма = (1 — тз)уь Ь=0,1,... '3 ду "'.к (34) О = Р (и, — а( )У (и,)) — и,. (38) д Ф П Васильев 256 г . 5.
мнтОды минимИЗй ЦИи а унКЦИй многих пеРЕМЕННЫХ функции д(о) (рис. 5.5) видно, что функция д(о) достигает минимума при 0 < и < 25 ' в точке и, = 2(5 + и) 1, причем д(п,) = (Ь вЂ” и)(А+ и). Теорема 5 доназана. П Приведем п(~имер, показывающий, что оценка (29) неулучшаема на классе сильно выпуклых функций из С '(Х), Пример 1. Пусть и = (з у) е Х = Ез, у(о) = (5 е~+ муз)(2, О < и < Ь. ясно, что зта функция сильно выпукла с константой е = и, принадлежит сь (е ) с константой е и до- н 2 д(а) стигает минимума на Ез в точке е„=(0, О).
Процесс (2) при пь = и, О < и < 2Ь ', имеет вид а.—— 5+ Е Положим здесь и = 2(Ь Ч- И), д = (Ь вЂ” И)(с + и) и тогда хз , = -дх, уь ~ — дуги Следовательно,)оь + ~— Рис. 5.5 — е (= д)о (= дат'(о !, т. е. оценка (29) неулучшаема. Заметим, что если в теоремах 1-5, в частности, Х = Ел, то мы получим сходимость соответствующих вариантов градиентного метода (!.3).
5. Опираясь на подходы к непрерывным методам минимизации, развитые в работе А. С. Антипина [25], можно предложить следующий непрерывный вариант метода проекции градиента, основанный на системе дифференциальных уравнений: х(1) =Рх(х(ь) — а(2)7'(х(т))) — х(1), 1 > О, где а(г) > 0 — заданная функция (параметр метода), Х вЂ” выпуклое замкнутое множество из Е". В частности, если Х = Е", то (34) превращается в систему (1.45).
Согласно теореме 4.4.4 решение х„задачи (1) удовлетворяет уравнению 'Р (х, — а(()г'(х,)) — х, =0 при Чз > О, Это значит, что каждая точка х„ е Х, является точкой равновесия (стационарным решением) системы (34). Можно ожидать, что при некоторых ограничениях на функцию 7(х), а(1) траектории х(1) системы (34) при больших г приближаются ко множеству Х,. Справедлива Т е о р е м а 6 (Антипин).
Пусть функция У(х) е С" (Е ), выпукла на Е', Г", > — оо, Х, ~о, а функция а(г) непрерывно дифференциругма при 1>0, а(1) > а >О, ац(1)<0 Чх >О. Тогда траектория х(1) системсч(34) с любым начальным условием х(0) = х е Е" определена при всех ( > 0 и существует точка п„е Х„такая, что !пп х(х) = и., 1пп г(х(1)) = у„ !пп х(т) = О.
До к аз а тельство. При выполнении условий теоремы О<аз< се(1)< < а(0), и с учетом свойства сжимаемости оператора проектирования (теорема 4.4.2) нетрудно доказать, что правая часть 'Р (х — а(х)г(х)) — х дифференциального уравнения (34) удовлетворяет условию Липшица по х, непрерывна по совокупности ((, х). Тогда задача Коши для уравнения (34) с начальным условием х(0) = х имеет решение х = х(1), определенное при всех х > 0 (см. ниже теорему 6.1.1).
Йспользуя характеристическое свойство проекции (неравенство (4.4.1)) уравнение (34) можно записать в эквивалентном виде ((х(й)+х(Г)) — (х(1) — а(Г)~'(х(1))),п — (х(()+х(Г)))>0 ЧпЕХ, Ч2>»0. (35) Кроме того, в силу теоремы 4.2.3 имеет неравенство (г'(х,), и — х,) > 0 или а(х)(у'(х,), и — х,) > 0 ЧпЕХ, Чь >О, Чх, Е Х.. Согласно (34) тогда х(х) + х(х) е Х Ы( > 0 (сама траектория х(1) может и не принадлежать Х при каких-то 1 > 0). Положим в (35) и = х„, в (36) о = х(х) + х(() и сложим получившиеся неравенства. Будем иметь (х(г)+ а(х)(г'(х(з)) — г'(х„)), х, — х(г) — х(з)) > 0 или (х(1)(з+ (х(х), х(1) — х,) + а(Ф)(Г'(х(1)) — Г'(х„)), х(х) — х„) + + а(Г)(~'(х(1)) — ~'(х„))) х(1)) < 0 ЧГ » >0) Чх„Е Х„. Отсюда с учетом неравенств а(т) > О, (7'(х(1)) — у'(х„)), х(1) — х,) > 0 Ч( > 0 (теорема 4.2А) имеем: (х(вИз+- — (х(2) — х (з+а(2) — (Г(х(х)) — Г(х,) — (Г" (х„),х(1) — х.))<0 Ыс>0.
Интегрируя это неравенство на произвольном отрезке ]т, 11, г > т > О, и, преобразуя интеграл от третьего слагаемого по частям, получим 1 ) =г ) !х(в)(зг(в+ -(х(в) — х„)з] + а(в)(Г(х(в)) — Г(х,)— ь — (г'(х,), х(з) — х„)) — ) а'(в)(7(х(в)) — 1(х,)— в — (7'(х„), х(в) — х,))с(в < 0 Ч$ > т » )О, Чх„Е Х„. Отсюда с учетом неравенств а'(1) < О, а(1) > О, (у'(х.), х(1) — х„) > 0 (теорема 4.2.3), ('(х(г)) — Г(х„) — (7'(х,), х(1) — х,) > 0 (теорема 4.2.2) имеем ь ~ /х(в))зг(в -)- -!х(2) — х ! < -)х(т) — х / + а(т)(у(х(т)) — у(х )) Ч(>т>0 Чх ЕХ. Из (37) при т = 0 следует 1 ]х(в))Чв+ 2!х(х) — х)~ < 2]хо — х(~+ а(0)(г(хо) — г(х)) Чз»>0.
о Отсюда заключаем, что траектория х(1) равномерно на 1 > 0 ограничена. Кроме того, ) (х(в)!зс(в < сю, и поэтому найдется последовательность (2,.)— о +со, для которой х(т,) — О. Кроме того, пользуясь теоремой Больцано— Вейерштрасса, можем считать, что последовательность (х(гг)) сходится к некоторой точке тг.. Так как множество Х замкнуто, а х(к)+х(х) ЕХ Ых >О, то 1пп(х(з )+х(з ))=и.
е Х. Далее, переходя в (34) к пределу при х = хз— — оо с учетом непрерывности оператора проектирования (теорема 4.4.2), 1пп а((ь) = ст(оо) > а > О, получим ,2 :гй Ь 3 МЕТОД ПРОЕКЦИИ СУБГРАДИЕНТА 289 Упражнения или 7(х) -» !п(; х Е Х, (2) 288 Гл, 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Согласно теореме 4.4.4 это значит, что н, Е Х„. Полагая в (37) т = Ьс и х, = еы имеем 2]х(Ь) — п.Г ~ 2]х(12) — н.!' + *(Ьс)(Х(х(Ь;)) — 1(н.)) ~Ь > Ь;- Отсюда, переходя к пределу сначала при Ь вЂ” +со, затем Ьс — +ею с учетом равенства [пп х(62)=п„ получим: ]!пт х(Ь)=п,.
Тогда [!п1 7"(х(Ь))=7"(х„)= »» * С сх с ь» = 7",. Наконец, из уравнения (34) при Ь вЂ” »+ос с учетом равенства (38) имеем: [пп х(Ь) = О. Теорема 6 доказана. С] с сю Для сильно выпуклых функций можно доказать следующую оценку скорости сходимости метода (34) при а(2) т ао — — сола! [25]: ]х(!) — х,! < ]хо — х,! ехр(- [ 6(т)дт), о где Ь(т) = ар (! — -~-) при 0 < а < Š—, Ь(т) = аЬ (! — — ) при а > —. Х+р' 'с 4 ) Ь+р' При построении нейрерывных методов проекции градиента могут быть использованы диф- ференциальные уравнения второго и более высокого порядков. Так, например, для выпуклых задач (1) в [25] исследована сходимость процесса ДЯх(2)ц-х(2)+хЯ=Р»(хЯ-аЯГ'(хЯ), 2 > О, д(2) ) Д, >О, и его двухшагового дискретного аналога, При Х = Е" метод (39) превращается в метод тяжелого шарика (1.49).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
