Ф.П. Васильев - Методы оптимизации (1125241), страница 76

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 76)

Из (16) следует, что )х — х (<(д(ст))ь(хо — хт я'! 7т > й Отсюда при т- сс получим оценку (15). Так как х,=Р„(х„— ст/'(х,)), то из теоремы 4.4.4 следует, что хь — точка минимума функции /(х) иа множестве Х. Теорема 3 доказана. П Заметим, что наименьшее значение у(ся) из (15) п1>и 0 < а < 2)ьЬ ' достигается при ст, = )гЛ ' и равно д(сг,) = (1 — ()г/Ь)') (Я. 3. Следуя !241, рассмотрим слоднмость метода (2), (4), не требуя, а отличие от теорем 1, 2, ограниченности множества АГ(хо).

Кроме того, будем считать, что вычисление градиента функции и проектирование на множество на каждой итерации проводятся с погрешностями. Теорем а 4. Пусть Х вЂ” вьтуклое гамкнутое многкестао ив Е", 1п1 Х ф Я, функция у(х) выпукла яа Х, у(х)Е СЬ (Х), >, > — со, Х„г Е1. Пусть вместо точного влечения градиента Г(х) и проекции Рх(х)жР(х) иавестяы ия приблихггния Уь'(х) и соответственно Рь(х) с погретностью )Т(х) — Уь~(х)! < бь, хЕ Х; !Р(х) — 'Рь(х)! < Себя, х Е л", С,=сапы>0, бь>0, Ь=0,1,..4 2; б, =6<ос.

ь=о 255 4 2. МЕТОД ПРОЕКЦИИ ГРАДИЕНТА (!8) (У(х),х — х)>0, хбХ (22) [х„— х„[<(д( ))й! — .о[, Й=О,1, (29) Из (20) и неравенства (4,4.1) получаем где Г', '* г,,К 1 — рой, 0<а<2(ЬЧ-р) ', д( )= Ьп — 1, 2(Ь+р) (а<2Ь (24) (26) (31) (32) (33) 254 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Наконец, пусть последовательность (хй) определяется условиями хй ! —— Рй(хй — айУк'(хй)), як 6 Х, й =О,! где ай еькбирается так: О<го<а <2(! — е)/Ь, й=0,1,, 0<э<!. Тогда (х„) сходится к некоторой точке е, 6Х,.

Д о к а э а т е л ь с т в о. Наряду с (хк) введем вспомогательную последовательность (ок), определяемую следующим образом; ик — — Р(хк — п у'(х )), й = О, 1, .. и ео— - хо. (20) Ото|ода и из (18) с помощью теоремы 4.4.2 и условий (17) получаем !хй ! — ог,! < !Рк(хк — ай Уй'(х,)) — Р(хй — айУй~(х ))[+ + [Р(хй — пйУй~(хй)) Р(хй — пйУ~(хй))! ( Собк + ай[Уй~(хй) — У~(хй)! < < Собй Ч (2(1 г)/Ь)б.

= С бк й = 0 1 (21) Возьмем произвольную точку х, 6 Х„, Согласно теореме 4.2.3 тогда (ий — хк + ак У (хг ), х — ой) > 0 кУх 6 Х. (23) Положим в (23) х = х„а (22) умномким на пй > 0 и примем х = о, Сложим получившиеся неравенства ("й и ой)+ай(у'( .) — у'(,),х„— .) >О, А=О, ! 11реобразуем каждое слагаемое в правой части (24). Прюкде всего имеем 2(и — х, х„— и,) = /х — х„[з — /х, — ой!з — !и — х,[з (25) Далее, воспользуемся неравенством (4,2.20) при и = хй, о = хм ш = ок; получим (У'(х ) — Уч(х„), х„— о ) < (ЬУ4)!х — и [з, й =О, 1, Подставив (25), (26) в (24), получим [хй — х„! — [о, — х,/З вЂ” (1 — айЬ/2)[хй — ой! > 0 Отсюда, учитывая условие (! 9), имеем [хй — х,[з > [и„— х„/з.1- е/х„— о !з, й — О 1 (27) Далее, воспользуемся леммой 2.6.10 при х„= х,, г„= хы юй ! — — ой! из (! 7), (21), (27) получим 1!и /х — х„! = 8гп !ой — х,! < оо, !пп [ой — х„! = О.

(28) й оо й оо й Отсюда следует, что последовательность (хй) ограничена. Тогда существует хотя бы одна предельная точка о, этой последовательностй и подпоследовательность (хй ), сходящаяся к и„. Из (28) имеем 1цп ой — — и,. Согласно (23) с учетом (19) получаем (у(х,),*-.й»-(,-*„*-..)-й -!;-*,[[*-;[; . Отсюда при й = й со будем иметь (у'(о,), х — о„) > 0 при всех х 6 Х, По теореме 4,2,3 тогда оо 6 Х,.

Вспомним, что неравенство (27) было получено для любой точки х, 6 Х„, В частности, (27) верно и для х, = и,. Но о, — предельная точка последовательности (х„). Из леммы 2.6.!0 тогда следует, что (х„) сходится к о„. Теорема 4 доказана. С! Замечание 1. Если в (17) бк — — О, й =0,1,..., то из (!8)-(20) следует, что х„! — ей, й = О, 1,... Тогда из (27) имеем !хй — х.!'>!хй,— х.! Йе[х, — х„,!', Й=О,!,..о 'кгх„пХ Пользуясь произволом в выборе х, н Х„отсюда получаем [х„— е[>!х, — о[, р(хй,Х)>р(хй„к,Х), Й=О,!,..о причем равенство здесь возмоккно лишь при хйч! — — хк, что в силу теоремы 4.4.3 означает хй 6 Х,.

Таким образом, при точной реализаций метода (!7)-(19) расстояние от точки хк до множества Х, или до точки о„монотонно убивает. Как мы видели, таким кке свойством обладает градиентный метод (1.3), (1.21), (1.22). 4. Опираясь на неравенства, полученные при доказательстве теоремы 4, можно оценить скорость сходимости метода (2), (4) для сильно выпуклых функций, причем, в отличие от теоремы 3, новая оценка оказывается неулучщаемой на классе сильно выпуклых функций, принадлеккащих С! '(Х), Те ар е м а 5.

Пусть Х вЂ” выпуклое замкнутое множество из Ж", 1п1 Х фиг, а функция У(х) сильно выпукла на Х и принадлежит С' '(Х ), Пусть последовательность (х„) построена методом (2) при пй — — а, й = О, 1... О < а < 2УЬ. Тогда 0 < д(а) < 1, постоянные р, Ь вэятьк иэ (2.6.6), (4.3,12), а х„— точка минимума у(х) на Х. Наименьшее значение д(п) при 0 < а < 2Ь ! достигается при а = гй„= 2(Ь -ь р) ! и разно д(п,) = (Ь вЂ” р)(Ь + р) Доказательств о.

Из теоремы 4.3.1 следует, что У, > — оо, Х, состоит из единственной точки х,.Тогда из теоремы 4имеем )пп !хй-х !=О. Здесьмы предполагаем, чтов(17) бй — — О, й = О, 1,, поэтому из (18), (20), (2!) следует ек — — хк !, й = О, 1, Учитывая последнее равенство и условие а„= а, подставим (25) в (24). Получим [х„, — х„[х < !х„— х,[я — [х,, — х„[з+ 2а(у'(хк) — у'(х,), х, — хй „!) = =[х„— х,[З вЂ” [х, — хй „! — а(у'(хй) — у (х,))! + и. аз[у'(х„) — у'(х )!я — 2п(у'(хй) — у'(х ), хй — х,), Й =О, 1,... (30) Вспомним неравенства (4.3.17),(4.3.18), из которых имеем [,у'(хй) — у'(х,)! -1- Ьр[х„ — х„! < (Ь Ч- р)(у'(х ) — у'(х„), х, — х„), й = О, 1, р[х — х,! <[у'(х ) — у'(х,)[< Ь!х„— х„[, й =О,1,...

Из (30), (31) следует [х, — х,[З < [х — х„! -и а [у'(хй) — у (х,)!— — 2а(Ь + р) ! !Уг(х ) — У~(х„)[~ — 2аЬР(Ь + Р) [хй — хо! — а[а 2(У, 4 ) ![[Ук(х ) — У(х )/З-1-[1 — 2аЬР(Ь -1-Р) '[[х„— х [, й =0,1,... Рассмотрим два случая: 1) если 0< а < 2(Ь+р) ' < р ', то из (ЗЗ) плевого неравенства (32) имеем !х„! — х !з < < !хй — х,!й[а(п — 2(Ь+р) )р -1-! — 2пЬр(Ь+р) !=(! — ар) !хк — х [; 2) если Ь ! <2(Ь+р) ! < а <2Ь !, то из (33) и правого неравенства (32) получим [хеч!— -х,[я <[хе — х,[з[п(а — 2(Ь+р) !)Ьз+1-2аЬр(Ь+р) '[=(Ьа — 1)я[хй — х,[з.

Объединяя оба случая, имеем !хй „! — х ! <д(а)!х„— х !, й =О, 1, „откуда следует оценка (29) Из графика ыее 257 $2. МЕТОД ПРОЕКЦИИ ГРАДИЕНТА (34) Ч Ф,П Васильев 256 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ функции о(п) (рис. 5.5) видно, что функция 2(п) достигает минимума при 0 < и < 25 1 в точке и, = 2(ь ч- д) ', причем в(п,) = (ь — д)(ь + д), теорема 5 доказана.

и Приведем поимер, показывающий, что оценка (29) неулучшаема на классе сильно выпуклых функций из С '(Х), Пример 1. Пусть о =(х, у) сХ = ох, 1(о) =(Лая+ дух)12, 0 < и ( Ь. ясно, что зта функция сильно выпукла с константой к = д, принадлежит С ' (Е~) с константой Ь и до. с д(а) стигает минимума на Ех в точке лв = (О, О). Процесс (2) при пь — — и, 0 < о < 25', имеет вид — 1 хь 1 — — еь — псе =(1 — пь)ью ч(п Вь ь ~ = уь пдрь = (! он)пь 5=0,1,... а.—— положим здесь и = 2(ь+ л) ', ч = (5 — д)(5 + РГ .

ц в+ тогда еь, = — еаь, рь 1 — — явь. Следовательно, !ц„+1— Рис. 5.5 — е ! = л!пь! = Чье '!и !, т. е. оценка (29) неулучшаема. Заметим, что если в теоремах 1-5, в частности, Х = Ее, то мы получим сходимость соответствующих вариантов градиентного метода (1.3), 5. Опираясь на подходы к непрерывным методам минимизации, развитые в работе А. С.

Антипина 125), можно предложить следующий непрерывный вариант метода проекции градиента, основанный на системе дифференциальных уравнении: х(1)=?х(х(1) — о(1)Г(х(2))) — х(1)в 1)О, где сх(1) > 0 — заданная функция (параметр метода), Х вЂ” выпуклое замкнутое множество из Е". В частности, если Х = Е", то (34) превращается в систему (1.45). Согласно теореме 4.4.4 решение х, задачи (1) удовлетворяет уравнению ?х (х, — сг(1)7'(х,)) — х, = 0 при Чз > О. Это значит, что каждая точка х„Е Х„является точкой равновесия (стационарным решением) системы (34), Можно ожидать, что при некоторых ограничениях на функцию Г(х), се(х) траектории х(1) системы (34) при больших 1 приближаются ко множеству Х„.

Справедлива Т е о р е м а 6 (Антипин). Пусть функция 7(х) е Оь '(Е"), выпукла на Е", ?"„ > — оо, Х. ф О, а функция сх(1) непрерывно дифференциругма при 2 >О, сх(1)> сх >О, схц(1)<0 И >О. Тогда траектория х(1) системы(34) с любым начальным условием х(0) = хо Е Е" определена при всех 1 > 0 и существует точка п„е Х„такая, что !пп х(1)=п„)!ш Г(х(1))=7., !пп х(1)=0. Доказательство. При выполнении условий теоремы 0< его< сх(1)< < сх(0), и с учетом свойства сжимаемости оператора проектирования (теорема 4.4.2) нетрудно доказать, что правая часть ?х (х — се(1)?'(х)) — х дифференциального уравнения (34) удовлетворяет условию Липшица по х, непрерывна по совокупности (1, х). Тогда задача Коши для уравнения (34) с начальным условием х(0) = х имеет решение х = х(1), определенное при всех 2 > 0 (см.

ниже теорему 6.1.1). Йспользуя характеристическое свойство проекции (неравенство (4.4.1)) уравнение (34) можно записать в эквивалентном виде ((х(2)+х(2)) — (х(1) — се(1)?в(х(1)))ви — (х(1)+х(1))))0 ЧпЕХв 'о'2)0. (35) Кроме того, в силу теоремы 4.2.3 имеет неравенство (7'(х,), и — х„) > 0 или ех(1)(У'(х,), и — х,) > 0 'ч'пеХ, 'в'х>0, Чх,еХ,. Согласно (34) тогда х(2)+ х(1) е Х ьуг > 0 (сама траектория х(т) может и не принадлежать Х при каких-то с > 0).

Характеристики

Список файлов книги