Ф.П. Васильев - Методы оптимизации (1125241), страница 75
Текст из файла (страница 75)
Для этого обычно выбирают какую-либо постоянную а > 0 и в методе (2) на каждой итерации берут а, = а, а затем проверяют условие монотонности и при необходимости дробят величину аь = а, добиваясь выполнения условия монотонности. 3) Если функция /(х) принадлежит С' '(Х) и константа Липшица Ь для градиента /'(х) известна, то в (2) в качестве аь можно взять любое число, удовлетворяющее условиям 0 < ге < аь < 2/(Ь + 2г) (4) где г, г — положительные числа, являющиеся параметрами метода. 4) Возможен выбор аь из условия /(*ь) — /(Р (хь — ~„/'(хь))) > г!*, — Р (~ь — ~ь/'(хь))!', (5) где г > 0 — параметр метода. Для определения такого аь можно взять какое- либо число аь = а (например, а = 1) и затем дробить его до тех пор, пока не выполнится условие (5).
Если /(х) я С' '(Х), то нетрудно показать, что выполнения условия (5) можно добиться за конечное число дроблений. 5) Возможно априорное задание величин а. из условий а >О, А=0,1,...; 2, 'аь=со, 2, 'аз<со, (6) ь=е ь=.о например, аь = (й + 1) ', к = О, 1,... Сходимость метода (2), (6) будет исследована в $ 3. Заметим, что описанные здесь варианты метода (2) при Х = Е" переходят в соответствующие варианты градиентного метода. На практике для ускорения сходимости вместо (2) часто пользуются более общим вариантом метода проекции градиента хь 1 = хь + А(Рх(хь юь/'(хь)) хь) = = !ЗьРх(хь '"ь/(хь)) +(1 !Зь)хь~ 0 < )Зь > ! '"ь > О (2) где параметры аь !Зь могут выбираться различными способами.
Заметим, что в методах (2) или (2') на каждой итерации, кроме выбора параметров аь, !3„, нужно еще проектировать точку на множество Х или, иначе говоря, решить задачу минимизации Фь(х) = !х — (хь — аь/'(хь))!~ — ~ !и1, х б Х; (7) здесь возможно использование функции Ф,(х)=!х — х„!'+2аь(/ (х ), х — х ), отличающейся от предыдущей функции постоянным слагаемым.
Задачу (7) можно решать приближенно и вместо точки хе ч, е Х, Фь(хь,) = !п1Ф„(х) = =Фь„определить ее приближение г,„, из условий г„, Е Х'. Фь(гь,) < Фь, + б~~. (8) Предполагая, что Х вЂ” выпуклое замкнутое множество, из (8) с помощью неравенства (4.3.3) имеем !гьч, — х,ч,! < Фь(гьч,) — Ф,(х,) < 5,'.
или гьч ~ ~ Х !гь, ~ хеь ~! ~ <бь. Конечно, задачи (7), (8) далеко не всегда просто решаются. Поэтому методом проекции градиента обычно пользуются лишь в тех случаях, когда проекция точки на множество легко определяется, Например, когда множество Х представляет собой шар в Е", параллелепипед, гиперплоскость, полупространство или положительный ортант (см. примеры 4.4.1 — 4.4.6), задача проектирования точки решается просто и в явном виде, и реализация каждой итерации метода проекции градиента в этом случае не вызывает особых затруднений. Если же задача проектирования для своего решения в свою очередь требует применения тех или иных итерационных методов, то эффективность метода проекции градиента, вообще говоря, значительно снижается.
2. Остановимся на вопросах сходимости метода (2), (4). Т е о р е м а 1. Пусть Х вЂ” вьтуклое замкнутое множество из Е", функция /(х) Е СГН(Х), !и1/(х) = /„> — со. Тогда для последовательнох сти (х„), полученной методом (2), (4) при любом начальном приближении х, имеет место соотношение !пп !хе ч, — х ! =О. Если при этом множество М(х ) = (х: х Е Х, /(х) < /(хе)) ограничено, то !пп р(х,, Я,) = О, где о. = (х: хе М(х ), (~"(х), е — х) > 0 при всех п е Х). Д о к а з а т е л ь с т в о. Йз неравенства (2.6.7) при д = х„, х = х„ь, имеем /(хь) /(хь- ~) > (/(хь), хь х„„,) — (Ь/2)!хь — хь,!г, й =О, 1,... (9) Из (2) и теоремы 4.4.! следует, что (х„, — [х — а /'(х )], х — х.,) > 0 Чх е Х. Перепишем это неравенство в виде (7'(х„), х — х, ~,) > (х„— хеь „х — х„~,)/а„к = О, 1,...
(10) 252 Гл. б. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ 4 2. МЕТОД ПРОЕКЦИИ ГРАДИЕНТА 253 (15) оя' Ах =Р. (х — ст/'(х)), (!7) Отсюда при х = х„с учетом условия (4) получим ()"(хь), х — х,,) > )хь — хь,)т/сть > (Ь/2+ г)!хь — хь„,)а.
Подставим эту оценку в (9): /(хь) — /(хь,) > г/х — х„„,/т, й = О, 1,... (11) Так как /(хь) > /„> — сс и последовательность (/(хь)) — убывающая, то существует конечный предел !!щ /(хь) > /„и, следовательно, 1пп (/(х„)— — /(хь„,)) =О. Отсюда и из (11) сразу получим !!ш )хь — хя,! =О. Пусть теперь множество М(хо) ограничено. Так как согласно (11) /(хь „) < /(хь) «... /(хо), то (хь) е М(хо).
По теореме Больцано— Вейерштрасса ограниченная последовательность (хь) имеет хотя бы одну предельную точку. Пусть х„— произвольная предельная точка (х ) и (х ) — > х,. По доказанному !!ш !хь, — хь(=0, поэтому (х, )- х.. Переь сь ходя в (10) к пределу при й = й — сс, с учетом условий (4) и непрерывности /'(х) получим (/'(х,), х — х„) > 0 при любом х е Х, т, е, х„е 8„.
По лемме 2.1.2 расстояние р(х, Я„) непрерывно по х, поэтому !пп р(х,, Я,) = яь — ьо = р(х„, Я,) =О. Отсюда следует, что (р(ха, Я,)) имеет единственную предельную точку, равну>о нулю, т. е. !!ш р(хь, Я„)= О. Теорема 1 доказана, П Теорема 2. Пусть выполнгньс всв условия теоремы 1 и, кроме того, функция /(х) выпукла на Х, Тогда для последовательности (хь) из (2), (4) имеем !пп /(хь) =/„, !пп р(х„Х,) =О, (12) причем справедлива оценка 0~~/(хь) / (Сей 1 Со=сонэ!>Ой=12...(13) Доказательство.
Из ограниченности М(х), непрерывности /(х), согласно теореме 2.1.2, следует /, > — сс, Х, = (х; х Е Х, /(х) = Я ф О, Х, с М(х ). Возьмем произвольную точку х„Е Х,. Из неравенства (4.2.4) тогда имеем 0 < а„= 1(хь) — ) (х,) < (/'(хя), х — х,) = = (/'(хь), х — х„,) — (/'(хь), х„— х„,), й = О, 1,... Пользуясь неравенством (10) при х = х, и условием (4) выбора гяь, отсюда получим 0 ( ая ( (/'(хь), х. — хь „,) — (х„— х„„х, — хь,,)/ст ( < )хь — х„, !(зпР 1/'(х)1+ Р/г ) = С!хя — х, „, !, й = О, 1,...
(14) м(.,1 Здесь мы учли ограниченность множества М(х ), поэтому лл = зпр !и— ,ьям(г) — о~ < сс и, кроме того, !/'(х)! < )/'(х) — /'(хо))+)/'(хои < Ь )х — х !+)/'(хо)! < < ЛВ +1/'(хо)/ при любом х Е М(х„), так что зпр !/'(х)/ < сс, Из (11), м1,1 (14) следует ая — а„, > гС; 'а'„= Аа'„, й = О, 1,... Отсюда с помощью леммы 2.6.4 придем к оценке (13), из которой также следует первое из равенств (12). Второе равенство (12) является следствием теоремы 2.1.2. П Рассмотрим случай сильно выпуклой функции, предполагая, что в методе (2) величина оа выбирается постоянной.
Т е о р е м а 3. Пусть Х вЂ” выпуклое замкнутое множество, функция /(х) Е С' '(Х) и сильно выпукла на Х. Пусть 0 < а < 2)гй-а, где постоянные р, Ь, р < Х, взяты из (2.6.6), (4.3.12). Тогда последовательность (хь), получаемая из (2) при оя = ст, й = О, 1,..., сходится к точке минймума х„, причем справедлива оценка !хь — х,( < )хо — х„!(д(сг))ь, й =О, 1,..., где д(сг) = (1 — 2)гст + стаЬ Я) ПЯ, 0 < у(гт) < 1. Доказательство.
Введем отображение действующее нз Х в Х. Покажем его сжимаемость при 0 < ся < 2)гЬ '. С помощью теоремы 4.4.2 имеем ~)Аи — Ап)Я = (Р (и — ст/'(м)) — Рх(о — ст/'(о))!а < < ~„„/~(м) о+ „„/~(оЦЯ 1„„1г+ ЯУ~(и) /~(,)~г — 2гя(/'(и) — /'(о) м — т>) < !и — о!Я(1+ сяЯЬЯ вЂ” 2(лгя) = да(ст)!и — о!а т, е. )Аи — Ап) < д(сг)!и — о(, и, т> е Х (16) Так как 0 < ст < 2)>Л ', то О < д(гя) < 1.
Это значит, что отображение А— сжимающее. Заметим также, что замкнутое множество Х С Е" представляет собой полное метрическое пространство с метрикой р(м, о) = )и — о~. Следовательно, можно пользоваться принципом сжимающих отображений 1393). Метод (2) при гяь = ст, записанный в виде х +, — — Ах„, представляет собой известный процесс поиска неподвижной точки х, сжима>ощего отображения А, т. е. точки х„для которой х, = Ах,. Известно [393], что такая точка х„существует, единственна и 1пп ~!хь — х,)= О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
