Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 65
Текст из файла (страница 65)
5.4 а постоянная с) 1 является параметром алгоритма. Точка Р,+, определяется из (19) при Ь=Ь,+,. Разность сояа,— сова,, в равенстве (20) связана с «кривизной дна оврага» и, кроме того, обладает важным свойством ~г-Ф указывать направление измепения «кривизны».
А именно, при переходе с участ» -г ков «дна оврага» с малой «,-г е «кривизной» на участки с с г большей «кривизной» будем г4 г иметь сов а, — сов а„, ( 0 «„г (см. рис. 5.4). Тогда в силу (19) Ь,+,(Ь„т. е. овражи, гг» ный шаг уменыпается, при- спосабливаясь к повороту б,г «« ' »г.г «дна оврага», что в свою с.
очередь приводит к уменьй.г шению выбросов точки Р„+, на «склоны оврага». При переходе с участков «дна оврага» с большой «кривизной» на участки с меньшей «кривизной», наоборот, сова, — сова,, ) О, поэтому овражный шаг увеличится и появится возможность сравнительно быстро пройти участки с малой «кривизной», в частности, прямолинейные участки на «дне оврага». Если «кривизна дна оврага» на некоторых участках остается постоянной, то разность соя а,— сова«, будет близка к нулю, и поиск минимума на таких участках будет проводиться с почти постоянным шагом, сформированным с учетом величины «кривизны» при выходе на рассматриваемый участок.
Параметр с в равенстве (20) регулирует «чувствительность» метода к изменению «кривизны дна оврага», и правильный выбор этого параметра во многом определяет скорость движении по «оврагу». Некоторые эвристические соображения по поводу выбора с и другие аспекты применения овражного метода обсуждены в (276). Выражение (20) для овражного шага удобнее пре- ГРАДИЕНТНЫЙ МЕТОД 271 образовать так: совиг;совид г ) совид-совид в ь сагид — сагид дог = «с — = гд,с откуда имеем йдь =АГсе"д, А = й,с "*"г = согж1)0, й= 2,3, Другой способ ускорения сходимости градиентного метода заключается в выборе подходящей замены переменных и= Ела)= =(Е (ь) ..., Е,(9)) с тем, чтобы поверхности уровня функции У(Ы(9))= С($) в пространстве переменных $ =Д', ..., й") были близки к сферам.
Заметим, что б ($) =(д (9) )'У (д(ь) ), где Ы (9) = гя" .(9)) — матрица, г-я строка которой представляет соц) бой Ег(9)=(к. г(ь), ...,д п(9)), а (д'($))* — матрица, полученная из я'($) транспонированием. В пространстве переменных 9 градиентный метод выглядит так: $ге,=$д — 6«(Е (~,)) У (Е(~д)), ~д>0, й=О, 1, ... В пространстве исходпых переменных и=(и', ..., и») зтот подход можно трактовать как итерационный процесс вида ид.„, = и„— а«А«У (ид), ад > О, й = О, 1, ..., где А„— некоторая невырожденная матрица порядка вХ в, предстанляющая собой параметр метода. То, что на етом пути ыожно добиться существенного ускорения скорости сходимости итераций, подтверждается, например, излагаемым ниже методом Ньютона, в котором полагается А„= (У" (и,) ) ' (й = О, 1, ...) .
О ыетодах минимизации овражных функций и различных приемах ускорения сходимостп итерационных методов см. 14, 19, 54, 111, 229, 238, 250, 258, 284, 307, 314, 336). 4. Исследуем сходнмость другого варианта градиентного метода (3), в котором параметр аг определяется не условия (9) с помощью дробления. А именно, пусть 1 < е < 2, а > Π— фиксированные числа, а 1 > О в нанмепьшнй номер, для которого выполняется неравенство (11, 19, 66) У(ид) — Х(и« вЂ” 2-'аХ'(ив)) > 2-' 'ав)Х'(ид) )г, (21) н пусть ад = а(2г. (22) Теор е м а 4.
Пусть е задаче (1) У» > — оо, У» Ф 8, угункггия 1(и) выпукла на Е", У(и) гнеь'(Е"). Тогда длп последовательности (ид), определяемой методом (3), (21), (22), имеют место соотногиения (Н) и, бо- лее того, существует точка ое гв У» такая, что (ид) -т ое, ) идет — ое(~)ид — ое) Р(и«+и ые)ейР(ид Пе) й=О, 1, ..., (23) причем равенство в (23) во»погано лить при ид = ид+г ... о„; спра- ведлива оиенка О<у(и ) — Уее!,(ш1п((2 — е)Д2Ь); аЦ г(2/е))и — ое) й =0(1/й), й 1,2,..., (24) 272 МЕТОДЫ МИНИЪ|ИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ 1ГП. Э и если У вЂ” афгбинное множество, то ов = УП (и,), т. е.
о» вЂ” ближайшаЯ к ию точка иа П». Доказательство. Сначала покажем возможность выбора и» из условий (21), (22). Пусть 1) 0 — наименьший номер, для которого 1 ° 2-та < 2 — е; (25) здесь Ь ) 0 — константа Липшица для 1'(и). Ив неравенства (2.3.7) при о иь, и = и» вЂ” 2 гх1'(и») с учетом (25) имеем 1(и,) — 1(иь — 2 та1'(и»)) )<1'(ин), 2-Га/'(и»)> — Ь 2-1-'а(1'(и»))» = 2 Г 'а(2 — 2-1пЬ) (1'(и») (т > 2-Г-»ае(1'(иь) (з.
(26) Это значит, что при 1=1 неравенство (21) выполняется, и, следовательно, минимальный номер» ) О, при котором справедливо (21), существует и нв превышает номера у из (25). Покажем, что для а» из (21), (22) справедлива оценка а» ~ впп ((2 — е)/(25); а), й =О, 1, (27) Сначала рассмотрим случай а ) (2 — е)/(25). Тогда оказывается, стн ) (2 — е)/(25) при всех й = О, 1, ... В самом деле, для номера / из (25) в этом случае имеем 2-та < (2 — е)/Ь < 2 гыа (/ > 0). Поэтому с учетом правила выбора номера», определения а» из (22) и неравенства»</ получим ае = сс/2» =» а/21 ) (2 — е)/(2Б). Пусть теперь а < (2 — е)/(2Ь).
Тогда неравенство (25) ц, следовательно, (26) выполняется при / = О. Отсюда и из (21) следует, что 1=0. Согласно (22) тогда а»=а/2'=а (/т = О, 1, ...). Объединяя оба рассмотренных случая, приходим к оценке (27). Далев, возьмем любую точку ив ен У . Из (3), (21), (22) и теоремы 4.2.2 имеем (е/2) а„).1'(и,))з<,1(и,) — 1(и,+ ) (1(и„) — 1(и») (~(1'(иь), иь — и») (28) Кроме того, ив (3) следует (иь+ — ив!~ = (иь — аь1'(ин) — и»( = (иа— — и» (з — 2а, (1'(иь), иа — ив)+ аз ! 1' (и„) (з.
Отсюда с учетом оценки (28) получаем ) и,+ — ив(»((и„— ив '(з — (е — Ц аз (1'(и,)(з, 1 < е < 2. (29) Следовательно, (иа+ — ив) ~((иа — и»! (~ ... ~((и — и»! ч/и»ее П» (30) Из (30) вытекает существование предела 11ш (и„— ив(~ и ограничена»» ность последовательности (щ). Тогда найдется подпоследовательность (иь ), сходящаяся к некоторой точке о„.
Пз (27), (29) следует, что (1 (иь )) «1 ("») =О. По теореме 4.2.3 тогда о ш У . Приняв ив = о, пз (30) получаем )пп ! иь — о» ! = 1!ш ) и„— «» ~ =О, т. е. вся последоь о» вательность (и») сходится к точке и„. Отсюда и нз (29), (30) следуют неравенства (23). Как видно из (29), равенство в (23) возможна лишь при 1'(ин) = О. Тогда в силу теоремы 4.2.3 и„= о» ш (1», и процесс (3), (21), (22) на этом заканчиваетсл. ГРАДИЕНТНЫЙ МЕТОД 273 Докажем оценку (24). Обозначим а, = 1(и„) — 1в. Из (28), (30) при ив = ив имеем (е/2) аа ! 1'(иа))~~ (аа — аз+1, аа( ((1'(ин) (! ио — ив (, 5 =0, 1, Отсюда с учетом равенства (4.4.2) имеем )и — и )з)га!и — У, (и)!з при всех я > О.
Разделив зто веравекство иа а ) 0 и устремив а- со, получим и = Уп (и ). Теорема 4 доказана. 5. Следуя (229), рассмотрим метод, представляющий собой комбикацию несколько модифицироваккого метода (3), (21), (22) и овражкого метода. Возьмем начальные приблпжевия: и,»ы Е", Ь, = 1, а 1 > О, положим и 1 = о». Пусть для некоторого /с > 0 уже известны иь ш Е", Ь» ) 1, аь 1 > > О, и», »и Е".
Определим ваимекьший валер 1) О, для которого выполкяется перазекстзо 1(и») — 1(и» вЂ” 2 »а» — 11'(иь)) ) 2 ' »а»-»( 1'(иь)('. (31) Далее, положим аь = а»,/2', иь = 1»» а»1 (иь)» ܄— 1 'а+1 (32) 1 / ь„+, = -, ((+ )/' 4ьй+ 1), (ЗЗ) Таким образом, в оппсаииом методе (31) — (33) спуск из точкл иь па «дло оврага» осуществляется по формулам (31), (32) с помощью одного шага градиентного метода (3) с правилом выбора параметра аь близким к (21), (22). Здесь возможно использование кекоторых других вариантов градиент- наго ыетода, яапример, по аналогии с (8) в (32) можно взять а» = 1/Л. Как видно из (33), пересчет точки иь осуществляется с помощью овражного метода по формуле, близкой к (19).
Первое из равевств (ЗЗ) представляет собой правило пересчета длины овражвого шага; величина Ь»ы является положительным корнем квадратного уравнения х — х — Ьа — — О, т так что Ьт — Ь„=Ьз, Ь =1, Ь >О,,' 5=0,1, ... (34) С помощью индукции нетрудно получить оценку Ь, ) Ь, Ь = 1, г, ... (35) Теорема 5. Пусть фу»»кипя 1(и) выпукла на Е", 1(а) «пба '(Е"), л'в > — оо, //о ~ 8, последовательность (и») определена методом Отсюда с учетом (27) получаем ໠— а»+1) (е/2) шш ((2 — з)/(25)! а) Х Х! и — ив! зааз (/с = О, 1, ...). Из леммы 2.3.4 тогДа следУет оЦенка (24). Йакоиец, пусть (/в — аффиикое множество.
При Ь-т оо из (30) имеем )ие — ие( ()ио — ие! при любом иеш(/в. В частпости, в этом нерва з векстве мошко взять и = о -(- а(УО (и ) — и ) = и «и Пв, а > О. Получим (ио — иа! ~)! и» вЂ” исс! =((ов ио) ("а ио) ! =(ив — ио! +! иа — и !— 2 (ив 'ло* иа ио) ! иа ио ! ! ив '»о ! 2а (иь ио Упв (ие) — о ) или )ьв ™о! )~га(иь — Уп (ио)! +за(Упе(ио) ио ив Угт (ио))' 274 МЕТОДУьд МИНИМИЗ»ЦИИ ФУНКЦИИ МНОГИЕ НЕРЕМЕННЬДЕ 1тгч, З (31) — (33).
Тогда 0(1(и,) — 1 ((шьп(1/(2У); а )) д(2а (1(и ) — 1 )-( + ддд( ! и — ьго! //(2»)=0(1/»'), »=1ь 2 "° (36) иь П» д о кавит ель с т в о. Пусть / ) 0 — наименьший номер, для которого 2 д < 1/Ь. (37) Нетрудно видеть, что тогда 1(пд) 1(па — 2 ьиа ьХ'(па)) ~ ~2 ь ьаа ьььХ'(па) ььг; (38) вто неравенство доказывается так же, как (26).
Отсюда следует существование номера д ( /, удовлетворяющего неравенству (31). Рассуждая так же, как ири доказательстве оценки (27), иа (31), (32)„(37), (38) с помощью индукции получаем иа) ш1и(1/(27,); а ь), »=О, 1, ... (39) Обозначим ра= (Ьа — 1)(иа-ь — иа). Тогда из (ЗЗ) следует па+ь = иа — ра/Ьа»ь, ра Ьа+ь(иа — па»ь) (40) Далее, с учетом (32), (40) имеем ра+ь — иа»ь (Ьа»ь — 1)(иа — иа+ь) — иа+ь = Ьа+ь(иа — иа+ь) — иа = = Ьа»ь(иа — па+ь + аа+ьХ'(иа+ь)) — иа ра — иа + аа»ьЬА+ь1'(па+ь). Тогда для любого и» гн д/» получаем Рд+ — и»+а+и»1~= ! Рд — и + и»(~+ 2ад+дьд+а<У'(ид+ ), Р» — ид+и,)+ +аз+ Ь,з+ (Х'(и,+ ) )з, или с учетом (40) ) р„+,— д+,+~~' — ) р„— ~+,~'<2,,<1'( д,), (Ьд,р,— р„)+ +(Р— Ьд+ ид)+ Ьд+ и 1+ аде+ Ьзд+ ) У'(пд+ ) )~= 2ад+ (Ьд+ — 1)Х Х<1'(пд+ ), Р»1+ 2аь,+ Ьь,+ <Х'(од+а), и» вЂ” пд+ )+ а»+дьд+д) Х'(ид+д) (~, » О, 1, ...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
