Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 66
Текст из файла (страница 66)
(41) Заметим, что (31) с учетом (32) можно переписать в виде У(па) — 1(иа) =и ) (аа/2) !Х'(па) (г. Для Ь+ 1-й итерации зто неравенство имеет вид 1('д+д) > 1("д+д)+ 2 д+д! 1 ( А+д) Г' (42) Из теоремы 4.2.2 с учетом (42) получаем <'(пд+) "- д+ ><Х(и»)-1(пае)(1» — У(и»+а)-Зад+ ')Х (".+)Р (43) Далее, из теоремы 4.2.2 и из (40), (42) следует (аа+ь/2) (Х'(па+ь) )г ( 1(па+ь) — Х(иа+ь) ( Х(иа) — <1'(па+ь), иа — иа+ь)— — 1(ид»ь) 1(иа) — 1(иа+ь) — <1'(па+ь), ра)/Ьа»ь, откуда <1'(па»ь)> раг( Ьа+ь((1(иа) — 1(ид+ь)) — (аа+ь/2) (1'(па+ь) (ь). (44) 2?5 ГРАДИЕНТНЫЙ МЕТОД 6 Ц Обоаначим а, = 1(и, ) — 1».
Подставим оценки (43), (44) в (41). С учетом (32), (34) получим (Рд„х — ид+ + и )2 — ~(Р— из+ и» ~2~ ~ 2ид+ (Ьд+ — 1) Ьд+д (ад — ад+ — (сед+ /2) ~ 1' (од+2) ) ) + + 2сь,+ Ьд+ ( — а,+ — (ад+ /2) (1'(од+ ) (2)+ сет+дЬ2+ ) 1'(од+ ) (~ = Ьза l 2 2 2 = 2и,+ Ьдад — 2пд+ ад+ (Ьд+ Ьд„) < 2адудад — 2ад+дд „ад 2. Таким образом, ) р — и + +и )2 — ~(р — и +и )~К,2а Ьз а — 2а,„+дЬ~~+„а +, та=0,1, ...
Суммируя эти неравенства по та от 0 до некоторого та = й — 1, получим ) рд — ид-(-и»)'+2идьдад<2 еь',ае+) ре — ие+»)'. Отсюда с учетом равенств Ьь = 1, рв = О, оценок (35), (39), произвольности выбора точки и из П приходим к оценке (36). Теорема 5 доказана. Отметим, что метод (31) — (33) не обеспечивает монотонное убывание функции 1(и) на последовательностях (щ), (оь). Сравнение оценок (24) п (36) показывает, что для выпуклых гладких задач овражный метод имеет более высокую скорость сходимости, чем градиентный метод (3), (9). В (228) показано, что оценка 1(ид) — 1» = 0(1/Д ) является неулучшаемой на этом класса функций среди всех методов, использующих лишь значения 1(и), 1'(и).
6. Кратко остановимся на непрерывном аналоге градиентного метода. Для этого перепивгем формулу (3) в безывдексной форме, приняв иь = и(2), щю = и(с + 52), сьь = 525(2), 52 > О, () (с) > О. Получим (и(2+52) — и(2))/52 = — ()(2)1'(и(е)), 2 > 0; и(0) = и,. Отсюда, формально переходя к пределу при 52-+-+О, придем к следующей задаче Коши: й(2) = — ()(2)1'(и(2)), С > 0; и(0) = иы (45) Задача (45) представляет собой непрерывный аналог градиентного метода, а исходный процесс (3) является методом ломаных Эйлера для решения задачи (45). Попятно, что задачу Коши (45) можно решать и другими численными методами, которые, возможно, будут сходиться быстрее метода Эйлера н лучше приспособлены для ыинимнзацни овражных функций (4, 13, 39, 54, 258).
О п р е д е л е н и е 1. Траекторию (репгенпе) а(г) задачи (45) будем называть минимизирующей, если и(г) определена при всех с > 0 и )пп 1 (и (2)) = 1„. Ограничимся следующей теоремой о сходпмости метода (45). Т еп р е м а 6. Пусть функиия 1(и) сильно выл укла на Е и 1(и) ш ш С' '(Е"), функуия 5(с) определена, непрерывна и 5(т) -" рь > 0 яри всех т > О.
Говда траектория задачи (45) при любом вььборе начальной точки иь является минамиоирузощей и сходится К точке минилнума и„о оленкой (и(2) — и )(!и — и )ехр( — 95 2), с>0, (46) зде постоянная д взята из теоремы 4.3.3. Доказательство. Прежде всего заметим, что по теореме 4.35 точна минимума и„функции 1(и) на Е" существует и единственна, а по МЕТОД ПРОЕКЦИИ ГРАДИЕНТА 277 3. Рассмотреть метод скорейшего спуска к другие варианты градяеят. ного метода для задачи мкнямнзацнн функции 1(о) = (Ак — Ь!з, озал", где А — матрица порядка ш Х п, Ь ш Ех; исследовать нх сходкмость.
4. Рассмответь метод скорейшего спуска для мнннмкзацнк функций 1(п) =хе+ау, к= (х, у) гвЕз, н 1(е) =хе+ уз+асс, и= (х, у, х) шхз, прн различном начальном приближении ке, считая коаффнцнент о намного больше единицы. 5. Доказать теоремы 1, 2 для метода (3), (7). (3) $ 2. Метод проекции градиента 1.
Будем рассматривать задачу Х(и)- ш(; иш СшЕ", (1) где множество (7 необязательно совпадает со всем пространством Е", а функция 1(и)ш С'((7). Непосредственное применение описанного выше градиентного метода в случае с1Ф Е" может привести н затруднениям, так как точка и„+, нз (1.3) при каком-то й может не принадлежать (1. Однако эту трудность можно преодолеть, если полученную с помощью формулы (1.3) точку и„— а,1'(и,) при каждом й проектировать на множество с1 (см. определение 4.41).
В результате мы придем к так называемому методу проекции градиента. А именно, пусть и,ш (1 — некоторое начальное приближение. Далее будем строить последовательность (и„) по правилу иьг, = Ус (иа — аьЕ (иа) ), й = О, 1, ..., (2) где а„ вЂ” положительная величина.
Если У вЂ” выпуклое замкнутое множество и способ выбора (а,) в (2) задан, то в силу теоремы 4.4.1 последовательность (и„) будет однозначно определяться условием (2). В частности, при (7 = Е" метод (2) превратится в градиентный метод. Если в (2) на некоторой итерации оказалось и„+, и, (например, ето случится при з (из) = 0), то процесс (2) прекращают. В атом случае точка и, удовлетворяет необходимому условию оптимальности и, = Ро (иь — а,х'(и„) ) (см.
теорему (4.4.3), и для выяснения того, является ли в действительности и, решением задачи (1) или нет, при необходимости нужно провести дополнительное исследование поведения функции 1(и) в окрестности точки и,. В частности, если 1(и) — выпуклая функция, то такая точка и„является решением задачи (1).
В зависимости от способа выбора а, в (2) можно получить различные варианты метода проекции градиента. Укажем несколько наиболее употребительных на практике способов выбора а„. 1) Введем функцию одной переменной 1ь(а) = 1(,тзо (иь— — сь)'(и„)) (а> 0) и определим аь из условий 1а(а„) =ш( 1а(а) = 1а, аа) О. аде Ф 278 методы Минимизации Функции мнОГих пегеменных ~гл, о Очевидно, прп С =Е" метод (2), (3) превратится в метод скорейшего спуска. Поскольку величину ао из условий (3) удается найти точно лишь в редких случаях (возможно также, что нижняя грань в (3) не всегда достигается), то сг„на практике определяют приближенно из условий типа (1.6) или (1.7). 2) Иногда приходится довольствоваться нахождением какого- либо а„>0, обеспечивающего условие монотонности: У(по+,)< < 7(и„). Для этого обычно выбирают какую-либо постоянную а > 0 и в методе (2) на каждой итерации берут я, = а, а затем проверяют условие монотонности и при необходимости дробят величину а„=а, добиваясь выполнения условия монотонности.
3) Если функция о'(и) принадлежит С' '(У) и константа Липшица Ь для градиента о'(и) известна, то в (2) в качестве ао можно взять любое число, удовлетворяющее условиям 0 < со< ссо < 2~(5+ 2е), (4) где е„е — положительные числа, являющиеся параметрами метода. 4) Возможен выбор а„из условия 1(ио) — о'(Уи(ио — со,.Г(ио) ) ) > ецио — Уо(и„— гол'(ио) )!', (5) где е >0 — параметр метода.
Для определения такого со, можно взять какое-либо число ао = а (например, а = 1) и затем дробить его до тех пор, пока не выполнится условие (5). Если о'(и)ш ш С' '(С), то можно показать, что выполнения условия (5) можно добиться за конечное число дроблений. 5) Возможно априорное задание величин а„из условий Ю ао>0, й=0,1, ...; ~ сов=со, ~аз<со, (6) о=о о=о например, ао = (й + 1) ' (й = О, 1, ...).
Сходимость метода (2), (6) будет исследована в $3. Заметим, что описанные здесь варианты метода (2) при П = = Е" переходят в соответствующие варианты градиентного метода. На практике для ускорения сходимостн вместо (2) часто пользуются более общим вариантом метода проекции градиента пооь = но+ ~о(Уи(ло — сооу'(по)) — по) = = 'РоУи(и, — аоу'(ио))+(1 — Ро)им 0 < Ро < 1, ао> О, (2') где параметры а„б„могут выбираться различными способами. Заметим, что в методах (2) илн (2') на каждой итерации, кроме выбора параметров и„бь нужно еще проектировать точку на множество С илн, иначе говоря, решить задачу минимизации Фо(и)=)и — (и,— а,У'(ио))1'- 1п1, ион С; (7) 9г1 МЕТОД ПРОЕКЦИИ ГРАДИЕНТА 279 здесь возможно использование функции Ф,(и) = ~и — и»Р + + 2х»<7' (и,), и — и„>, отличающейся от предыдущей функции постоянным слагаемым.
Задачу (7) можно решать приближенно и вместо точки и»ы ж У, Ф„(и»+,) = 1Е1 Ф»(и) = Ф»„определить ее приближение г»ы из условий г„„.,я У: Ф»(г»+»)(Ф»»+ 6»». (8) Предполагая, что У вЂ” выпуклое замкнутое множество, из (8) с помощью неравенства (4.3.3) имеем )г»+» — и»+»~'(~Ф»(г»+»)— — Ф» (и»+») ~ ~б» или г»+,ш П: ~г»+,— и»+»1 «6». Конечно, задачи (7), (8) далеко не всегда просто решаются. Поэтому методом проекции градиента обычно пользуются лишь в тех случаях, когда проекция точки на множество легко определяется. Например, когда множество У представляет собой шар в Е, параллелепипед, гиперплоскость, полупространство или положительный октант (см. примеры 4.4.1 — 4.4.6), задача проектирования точки решается просто и в явном виде, и реализация каждой итерации метода проекции градиента в атом случае не вызывает особых затруднений.
Если же задача проектирования для своего решения в свою очередь требует применения тех или иных итерационных методов, то эффективность метода проекции градиента, вообще говоря, значительно снижается. 2. Остановимся на вопросах сходимости метода (2), (4). Т е о р е и а 1. Пусть У вЂ” выпуклое замкнутое множество иэ Е", функция У(и)~С' '(У),1п1Х(и) = Ув) — со. Тогда для по- У слвдоватвльности (и,), полученной методом (2), (4) при любом начальном приближении и,, имеет место соотношение Нш~ и»+»вЂ” »-кю — и»~ = О. Если при этом множество М(и,)=(и: и и У, 7(и)~ «э'(и,)) ограничено, то 1ппр(ию Яв) = О, гдв Яв = (и» ия М(и ), »-» о <1'(и), о — и> ~ О при всех о»и И вЂ” мнохсвство стационарных точек функции э' (и) на М (и,) .
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
