Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 76
Текст из файла (страница 76)
'Задачу (>') можно решать приближенно и вместо точки х, э, Е Х, Ф (х >,) = >п1 Ф,(х) = = Ф.„ определить ее приближение гь , из условий , е Х; Ф,(, „,) <Ф,,+ б', (8) Предполагая, что Х вЂ” выпуклое замкнутое множество, из (8) с помощью неравенства (4.3.3) имеем [вьэ, — х„,[ < Ф (г,о,) — Ф„(х„„,) < б,', или зо о ~ с Х: [ гь „~ — х„ь ~ [ ~ (бь. Конечно, задачи (7), (8) далеко не всегда просто решаются. Поэтому методом проекции градиента обычно пользу>отся лишь в тех случаях, когда проекция точки на множество легко определяется. Например, когда множество Х представляет собой шар в Е', параллелепипед, гиперплоскость, полупространство или положительный ортант (см. примеры 4.4.1-4.4.6), задача проектирования точки решается просто и в явном виде, и реализация каждой итерации метода проекции градиента в этом случае не вызывает особых затруднений.
Если же задача проектирования для своего решения в свою очередь требует применения тех или иных итерационных методов, то эффективность метода проекции градиента, вообще говоря, значительно снижается. 2. Остановимся на вопросах сходимости метода (2), (4). Т е о р е м а 1. Пусть Х вЂ” выпуклое замкнутое множество из Е", функция /(х) е С" (Х), 1п1/(х) = /, > — оо. Тогда для последовательности (х„), полученной методом (2), (4) при любом начальном приближении х,, имеет место соотношение 1пп [х„,, — х,[=0. Если при этом мной сю жвство М(х ) = (х; х е Х, /(х) < /(хо)) ограничено, то !1ш р(х„, Я,) = О, гдв Я, = (х: хе М(хо), (/'(х), о — х) > 0 при всех с е Х).
Доказательство. Йз неравенства (2.6.7) при у=х,, х=х„, имеем /(хь) — /(х„+,) > (/'(х„), х,— х,+,) — (Х/2)[х,— х,э,[о, й = О, 1,... (9) Из (2) и теоремы 4.4.1 следует, что (хо~~ — [х„— а 7'(х )[, х — х„,) > О Чх Е Х. Перепишем это неравенство в виде (/'(х ), х — х,„,) > (хь — хо „х — х„э,)/аю й =О, 1,, (10) 252 Гл.
б. МЕТОды МИНИМИЗАЦИИ ФРНКЦИИ МНОГИХ ПЕРЕМЕННЫХ $2. МЕТОД ПРОЕКЦИИ ГРАДИЕНТА 253 Отсюда при х = х„с учетом условия (4) получим (Х'(хй), хй — х,й,) ) !хй — хйй,!'/сгй ) (Х/2+ г)(хй — хйе,(~. Подставим эту оценку в (9): /(х ) — /(хй,) > г)хй — хй„)(~, й =О, 1,... (11) Так как /(хй) > /„> — аа и последовательность (/(хй)) — убывающая, то существует конечный предел 1!гп /(хй) > /„и, следовательно, 1пп (/(х„)— й й о — /(хй„,)) = О. Отсюда и из (11) сразу получим !!гп (хй — хйй,! =О. Пусть теперь множество М(х ) ограничено. Так как согласно (11) /(хй „) < /(хй) « ... /(х ), то (хй) е М(хо), По теореме Бальцано— Вейерштрасса ограниченная последовательность (х„) имеет хотя бы одну предельную точку. Пусть х„ — произвольная предельная точка (х ) и (х ) -й х,.
По доказанному !пп !хай, — х.! = О, поэтому (х ) — + х,. Г)ере* й гг ходя в (10) к пределу при й = й„- аа, с учетом условий (4) и непрерывности /'(х) получим (/'(х,), х — х,) ) 0 при любом х е Х, т, е. х, е Я„. По лемме 2.1.2 расстояние р(х, Я„) непрерывно по х, поэтому 1ип р(хй, Я,) = л = р(х„, 8„) =О. Отсюда следует, что (р(хй, Я,)) имеет единственную предельную точку, равную нулю, т. е. !пп р(хй, Я„)=0. Теорема 1 доказана. С) Теорема 2. Пусть выполнены всг условия теоремы 1 и, кроме того, функция /(х) выпукла на Х. Тогда для последовательности (х„) из (2), (4) имеем !!гп /(хй) =/„Вш р(хй, Х„) =О, (12) причем справедлива оценка 0</(хй) — /„< С,й ', С =сапа(>0, й =1,2,, (13) До к а з а т е л ь с т в о. Из ограниченности М х ), непрерывности /(х), согласно теореме 2.1.2, следует /, > — ао, Х, = х: хе Х, /(х) =Я фо, Х, с М(х ).
Возьмем произвольную точку х„е Х,. Из неравенства (4.2.4) тогда имеем 0 < а„= Х(хй) — Х(х.) < (Х'(хй), хй — х,) = = (/'(хй), хй — х,) — (/'(хй), х„— хй,), й = О, 1, Пользуясь неравенством (10) при х = х, и условием (4) выбора ай, отсюда получим 0 < ай < (/'(х ), х, — хй,,) — (х„— хй „„х, — хй+,)/сг < < )х — хай, ((зцр )/'(х))+ Р/г ) = С,)хй — хй „(, й = О, 1,... (14) мг*,) Здесь мы учли ограниченность множества М(х ), поэтому Р = зпр !и— ь, ч е Мгч) — о~ < аа и, кроме тога, !Х'(х)! < )/'(х) — Х'(хо)!+!Х'(хо)! < Х !х — х (+!Х'(хо)! < < Х Р + !/'(хо)! при любом х е М(х ), так что знр )/'(х)~ < са.
Из (11), М(я ) (14) следует ай — ай, > гС, 'а', = Аа'„, й = О, 1,... Отсюда с помощью леммы 2.6.4 придем к оценке (13), из которой также следует первое из равенств (12). Второе равенство (12) является следствием теоремы 2.1.2. С) (15) )хй — х,! < )хо — х.)(д(сй))й, й =О, 1,..., где д(сй) = (1 — 2)йсг + сгвХ в))г', 0 < д(гл) < 1. Доказательство. Введем отображение Ах=Р (х — а/'(х)), действующее из Х в Х. Покажем его сжимаемость при 0 < т < 2)йХ, в.
С помощью теоремы 4.4.2 имеем !Аи — Аи!з = !Рх(и — а/'(и)) — Рх(о — сг/'(и))!з < < !и — сг/ч(и) — и + о/ (и)!в = )и — и)я+ сгя)Х'(и) — Хч(о)(я— — 2сг(/'(и) — /'(и), и — и) < !и — и!'(1+ свЯЬ' — 2(лгх) = де(са)!и — и!Я, т. е. )Аи — Аи! < д(о)(и — о!, и, и Е Х.
(16) Так как 0 < гй < 2)йХ, ', то 0 < д(сг) < 1. Эта значит, что отображение А— сжимающее. Заметим также, что замкнутое множество Х с Е" представляет собой полное метрическое пространство с метрикой р(ий и) = !и — и() Следовательно, можно пользоваться принципом сжимающих отображении 1393]. Метод (2) при ой = сг, записанный в виде х +, — — Ахй, представляет собой известный процесс поиска неподвижной точки х, сжимающего отображения А, т.
е, точки х„, для которой х. = Ах,. Известно 13931, что такая точка х„существует, единственна и !пп 1хй — х,! = О. Из (16) следует, что й гь !хй — х ! <(д(сг)) !хо — х й! Чгп > й. Отсюда при гп — + са получим оценку (15). Так как х. =Р (,х„— сг/'(х,)), то из теоремы 4.4.4 следует, что х„— точка минимума функции /(х) на множестве Х. Теорема 3 доказана. П Заметим, что наименьшее значение д(сх) из (15) ппи 0 < са < 2)йХ, ' достигается при а. = )йХ ' и равно д(сг,) =(1 — ()й/Х )') гз. 3.
Следуя !245 рассмотрим сходимость метода (2), (4), не требуя, в отличие от теорем 1, 2, ограниченности множества М(хо). Кроме того, будем считать, что вычисление градиента функции и проектирование на множество на каждой итерации проводятся с погрешностями. Т е о р е м а 4. Пусть Х вЂ” выпуклое замкнутое множество из Е", )п1 Х ~ ЕГ, функция Х(х) выпукла на Х, Х(х) е С~ '(Х), Х, > -оо, Х, Ф О, Пусть вместо точного значения градиента Х'(х) и проекции Рх(х) тР(х) известны их приблилгения Хй'(х) и соответственно Рй(х) с погрешностью )Х (х) — Хй'(х)! < 6й, х е Х; )Р(х) — Рй(х)! < Собй, х е Е", Со=сопв1>0, 6„>0, в=0,1,.,4 д,' 6.=6<со. й=о (17) Рассмотрим случай сильно выпуклой функции, предполагая, что в методе (2) величина сей выбирается постоянной.
Т е о р е м а 3. Пусть Х вЂ” выпуклое замкнутое множество, функция /(х) е С' '(Х) и сильно вьгпукла на Х. Пусть 0 < сг < 2)йХ ', где настоянные )й, Х,,и < Х, взяты из (2.6.6), (4.3.12). Тогда последовательность (х ), получаемая из (2) при сг = гх, й =О, 1,..., сходится к точке минимума х„причем справедлива оценка 255 $2. МЕТОД ПРОЕКЦИИ ГРАДИЕНТА 3 а и е ч а н и е 1. Если в (17) 6„= О, й = О, 1,..., то нэ (! 8)-(20) следует, что хь „, — — е„, й = О, 1,...
Тогда из (27) имеем (18) Пользуясь произволом в выборе х, Б Х„отсюда получаем причем равенство здесь возможно лишь при хь+ с —— хь, что в силу теоремы 4.4.3 означает хь Б Х,. Таким образом, при точной реализаций метода (17)-(19) расстоиние от точки хь до множества Х„ или до точки е, монотонно убывает. Как мы видели, таким лке свойством обладает градиейтный метод (1.3), (1,21), (!.22). 4. Опираясь на неравенства, полученные при доказательстве теоремы 4, можно оценить скорость сходимости метода (2), (4) для сильно выпуклых функций, причем, в отличие от теоремы 3, новая оценка оказывается неулучшаемой на классе сильно выпуклых функций, принадлеясащих С! '(Х).
Теорема 5. Пусть Х вЂ” гыпукхое замкнутое множество из Е", сп1 Х ФЕ1, а функция /(х) сильно гьшукла на Х и принадлежит С! '(Х). Пусть последовательность (хь] построена методом (2) лри сль —— а, й =О, 1,..., 0 < а < 2/Ь. Тогда !хь — х„]<(д(а))ь],—,], Й=О, 1, (29) 1 — ро, 0<а<2(Ь-1-и) д( )= Ьа — 1, 2(Ь+ р) (а (2Ь д(а) < 1, постоянные р Ь гзятьс из (2 Б 6), (4 3!2), а х„— точка минимулса /(х) на Наименьшее значение д(а) при 0 < а < 2Ь ' достигается лри а = а, = 2(Ь + и) ' и ено д(о,) = (Ь вЂ” р)(Ь + и) Доказательство. Иэ теоремы 4.3.1 следует, что /, >-оо, Х, состоит из единственной ки х,.
Тогда из теоремы 4 имеем 1пп /хь-х,]=0. Здесь мы предйолагаем, что в (17) бь — — О, й = О, 1,..., поэтому из (18), (20), (21) следует еь —— хь „с, й = О, 1,.... Учитывая последнее равенство и условие аь — — а, подставим (25) в (24). Получим ;л: д' (24) (25) (26) (30) Вспомним неравенства (4.3.17), (4.3.18), из которых имеем (31) 8 (32) р!хь — х,!(]/'(хь) — /'(х,)](Ь1хь — х,], й=0,1,... Из (30), (31) следует ~г<] ]г+ г]/с( ) /с( )]г — 2о(Ь ти) ]/~(хь) — /'(х„)] — 2аЬР(Ь+и) ]хь — х ] =а]сл — 2(Ь+и) с]~/(х ) — /(х)~г+(1 — 2аЬр(Ь+ и) с]]хь — х], Й=О,1,... (28) (33) Рассмотрим даа случая: 1) если 0< а < 2(Ь ч- р) ' ( р ', то из (33) и левого неравенства (32) имеем )хь ! — х,)г ( <]х — х Ца(а — 2(Ь+и) )гл +1 — 2оЬР(Ь+р) ]=(1 — ар) 1х — х ]; 2) если Ь ' <2(Ь+р) ' (а <2Ь ', то из(33) и правого неравенства (32) получим ]ха+!— -х,/г <!хь-х„/г(о(а — 2(Ь+р) ')Ьг+1-2аЬР(Ь+р) с]=(Ьсс — 1)г]хь-х,]г.
Объединяя оба случая, имеем !хь с — х,] < д(а)/хь — х„!, й =О, 1,..., откуда следует оценка (29). Иэ графика 254 г . 5. МетОДЫ МИНИМИЗАции функцИй мнОГих ПВРЕМЕННЫХ Наконец, пусть последовательность [хс) определяется условиями хс+ с =Рс(хь — ас/с'(хь)), хо б Х, й =О, 1,,, ч где аь выбирается так: 0<го(ос<2(!э)/Ь й 0 1 ... 0<э<1 (! 9) Тогда (хс) сходится к некоторой точке е, е Х,. Доказательство. Наряду с (хь) введем вспомогательную последовательность (ес], определяемую следующим образом; еь =7л(хь аь/(*ь)) "=0 ! ' ее = то (20) Отсюда и из (18) с помощью теоремы 4.4.2 и условий (17) получаем 1 ь ! еь~(Рь( ь ь/ь( ь)) р( л ь/ь( ~))]' +]Р(хь — аь/ь'(хь)) — Р(хс, — аь/'(хь))] ( Собь + аь]/ь~(хь) /~(хь)~ < ( Со ба с (2(1 г)/Ь )бь = С! бь й = 0 1 ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
