Ф.П. Васильев - Методы оптимизации (1125241), страница 73
Текст из файла (страница 73)
Рис. 5.4 Параметр с в равенстве (20) регулирует «чувствительность» метода к изменению «кривизны дна оврага», и правильный выбор этого параметра во многом определяет скорость движения по «оврагу». Некоторые эвристические соображения по поводу выбора с и другие аспекты применения овражного метода обсуждены в [557). Выражение (20) для овражного шага удобнее преобразовать так с»ОЯ |!! — СО! !!! ! ! !ОБ ! — «О! ! ! !. »05 ! — СО! ! — = Ь„ !с = ... = !«»с Ь„,=Ас"' ", А=Ьс '"'=сопз1>0, Ь=2,3,... Другой способ ускорения сходимости градиентного метода заключается в выборе подходящей замены переменных х= д(5) =(д!(5),..., д„(с)) с тем, чтобы поверхности уровня функции 7(д(5)) = С(5) в пространстве переменных 5 = (5!,..., 5") были близки к сферам.
Заметим, что С'Ы) = (д'(0)" У'(д(5)), где д'(5) = (дн!(~)) — матрица, «-я строка котоРой представлЯет собой д,.Я) =(ди,(~),..., д, .(Р)), а (дЯ))т — матРица, полученная из д'(С ) транспонированием. В пространстве переменных Е градиентный метод выглядит так: =5 — 13 (д'(~„))"у'(д(5„)), р„>О, Ь=О,1,... В пространстве исходных переменных х =(х',..., х") этот подход можно трактовать как итерационный процесс вида 244 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ вЂ” где А„— некоторая невырожденная матрица порядка и х и, представляющая собой параметр метода. То, что на этом пути можно добиться существенного ускорения скорости сходимости итераций, подтверждается, например, излагаемым ниже методом Ньютона, в котором полагается А, = (/л(шь)) ', й = О, 1,... 0 методах минимизации овражных функций и различных приемах ускорения сходимости итерационных методов см.
174; 84; 89; 222; 442; 525; 550; 586; 603; 65?; 721; 738; ?691 4. Исследуем сходимость другого варианта градиентного метода (3), в котором параметр а„ определяется из условия (9) с помощью дробления. А именно, пусть 1 < г < 2, а > 0 — фиксированные числа, а 1 > 0 — наименьший номер, для которого выполняется неравенство [з74; 603] /(х ) — /(хь — 2 'а/'(хь)) >2 ' >аз[/>(хь)[з, (21) и пусть аь = а/2'. (22) Теорема 4. Пусть г задаче(1) / > — оо, Х~Я, функция/(х) выпукла наЕ", /(х)е е С| '(Е") Тогда дяя последовательности (х„), определяемой методом (3),(21),(22), имеют место соотношения (11) и, более того, существует точка о„е Х„такая, что (х> ) -» о„, [хь+> — .[<[хь — е.[) р(хь»>$х„)<р(хь х.) ь=о,| " (23) причем равенство з (23) возможно лишь при хь — — хь» | — — ..
— — п„справедлива оценка 0</(х„)-/, <(ш!п((2-г)/(25);а)) >(2/г)[х„— о„[зй ' = 0(1/Ь), й =1,2,, (24) и если Х,— аффинное множество, гпо о,=Р» (хо), т. е. о„— ближайшая к хо точка из Х„. Доказательство. Сначала покажем возможность выбора аь из условий (21), (22). Пусть У > 0 — наименьший номер, для которого б 2 >с»<2 — г; (25) здесь 5 > 0 — константа Липшица для /'(х).
Из неравенства (2.6.7) при у= х„, х = хь— — 2 ' а/'(хь) с учетом (25) имеем /(х„) — /( „2->а/>(х )) > (/>(х ),2 >а/>(х )) — 5 ° 2 х> 'ах[/>(х )[з= =2 > 'а(2 — 2 >хо)[/'(хь)[Х) 2 > |аз[/'(х )[х. (26) Это значит, что при» = у неравенство (21) выполняется, и, следовательно, минимальный номер » > О, при котором справедливо (21), существует и не превышает номера у из (25). Пока>кем, что для а„ иэ (21), (22) справедлива оценка аь > ппп((2 — г)/(2Х );а), Ь = О, 1, (27) Сначала рассмотрим случай и > (2 — г)/(25).
Тогда оказывается, а„ > (2 - г)/(25) при всех й = О,! ... В самом деле, для номера у из (25) в этом случае имеем 2 >а < (2 — е)/о < < 2 а, у > О. Поэтому с учетом правила выбора номера », определения и из (22) и — »["'. неРавенства»' < У полУчим аь = а/2| > а/2» (2 — г)/(25). ПУсть тепеРь а < (2 — г)/(25).
Тогда неравенство (25) и, следовательно, (26) выполняется при У = О. Отсюда и из (21) следует, что» =О. Согласно (22) тогда а = а/2 = а, Ь =О, 1,... Объединяя оба рассмотренных случая, о приходим к оценке (27). Далее, возьмем л>обую точку х, е Х,. Из (3), (21), (22) и теоремы 4.2.2 имеем (г/2)аз [/ (хь)[З (/(х ) — /(х„+ |) </(хь) — /(х ) < (/ (х„), х„— х ). (28) Кроме того, из (3) следует [хь+ | — х„[з = [хь — а„/'(хь) — х,[з = [хь — х [х — 2а (/'(х ), х + * = » ь ь ь — х,) + аь[/'(хь)[ .
Отсюда с учетом оценки (28) получаем [х х [Х < [х„х [т — (г — 1)пгь[/'(хь)[2, 1 < к <2. (29) Следовательно, [х>, | — х„[ <[х — х[ «...[хо — х„[ >/х ЕХ. (30) 6 1. ГРАДИЕНТНЫЙ МЕТОД Из (30) выте>»ает существование предела 1пп [х„-х„[х и ограниченность последовательности (х„), Тогда найдется подпоследовательность (хь ), сходящаяся к некоторой точке е„.
Из (27), (29) следует, что (у'(хь ))-»/'(о,) =О. По теореме 4.2.3 тогда е, е Х,. Приняв х, = е„, из (30) полУчаем аш [хь — о»[= йш [хь — е,[=0, т. е, всЯ последовательность (хь) сходитсЯ к точке е„. Отсюда и из (29), (30) следуют неравенства (23), Как видно из (29), равенство в (23) возможно лишь при /'(х„) = О. Тогда в силу теоремы 4.2.3 хл —— е„е Х„, и процесс (3), (21), (22 на этом заканчивается окажем оценку (24). Обозначим аь — †/(хь) — /,. Из (28),(30) при х„ = о, имеем (г/2)аь[/ (хь)[з < аь — аы„ , аь < [/'(хь)[[хо — о„[, Ь = О, 1,...
Отсюда с учетом (27) получаем аь -аы > (г/2) ш|п((2 — г)/(2о); а)[хо-е„[ за, Ь = О, 1,... Из леммы 2,6.4 тогда следует оценка (24), аь, Наконец, пусть Х, — аффинное множество При Ь вЂ” » оо из (30) имеем [е. — х,[х < [х„— х„[х при любом х, еХ„. В частности, в этом неравенстве можно взять х, = о„+ а(Р (х>) —,)= = е ЕХ„а >О. ПолУчим [хо — о [Х > [о — о [Х =[(о — хо) — (е — х|,)[х = [о — хо[э+ [о — х [х — 2(п, — хо, о — то) = [о — хо[я — [е„— х [х — 2а(е, — хо, Р .
(хо) — е,) или [е, — х [х ) 2а[е, — Рх (хо)[э+2а(рх (хо) — хо е* Рх (хо)) Отсюда с Учетом Равенства (4 4 2) имеем [Я„-хо[я > 2а[е„-Р» (хо)[З пРи всех а >О. Разделив это неравенство на а > 0 и устремив а -»оо, получим о„ = Р» (хо). Теорема 4 доказана. П 5. Следуя [525], рассмотрим метод, представляющий собой комбинаци>о несколько модифи- цированного метода (З),(21),(22) и овражного метода. Возьмем начальные приближения: е е Е", Ь = 1, а > О, положим | —— о.
П некотоРого Ь >0 Уже известны пь ЕЕ", Ь > 1, аы > О, хь > е Е". ОпРеделим наименьший номер » > О, для которого выполйяется неравенство /(о ) /(о 2-» а /'(„)) ) 2-» — 1,„[/>(„)[2 (31) (32) Далее, положим '| г /("ь) /(еь — 2 >аы/'(еь)) > 2 > |а„[/>(о )[х. (34) (38) аь '"ы- /2 хь = "ь '"ь/ ("ь) ы+ 2( + т/4ьь -ь!/ ", =х„+ -ь — (х„— х„,), ьа| Таким обравом, в описанном методе (3!)-(ЗЗ) спуск из точки о. на » но оь на »дно оврага» осуществформулам ( ), ( ) с помощью одного шага градиентного метода (3) с правилом выбора параметра аь. близким к (21),(22).
Здесь возможно использование некото"ы е некоторых других иэ ЗЗ, пе р о градиентного метода: по аналогии с (8) в (32) можно взять а = 1/>5, К ( ), ресчет точки еь осуществляется с помощью овражного метода по фо, б т аь — — />, ак видно к(19). Пе вое из ав н 33 т да по формуле, лизкой ( ). р р венств (ЗЗ) представляет собой правило пересчета длины овражного шага; величина Ьь+ | ЯвлЯетсЯ положительным коРнем квадРатного УРавнениЯ х — х — Ььх — — О, так 2 х ь„,, — ь . ! — — Ью ь = 1, ь„ > о, ь = о, 1, С помощью индукции нетрудно получить оценку Ьь>й, Ь=|,2, (35) Теорема 5.
Пусть функция /(х) выпукла на Е", /(х)6 Сд'(ЕЯ), /, > — о>, Х ф й|, последогатеяьногть (х ) определена методом (3!)-(ЗЗ). Тогда О </(хь) — /, ((ш!п(1/(25); а >)) '(2ао(/(хо) — / ) 4 + |и! [х — т [х)/(2йз) = О(1/ья), Ь =1,2,... (36) До к а з а т е л ь с т в о. Пусть у > 0 — наименьший номер, для которого 2 > аы И!/О. Нетрудно видеть, что тогда (37) 246 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ это неравенство доказывается так Оке, как (2б) при з = 1. Отсюда следует существование номера ! < У, удовлетворяющего неравенству (31). Рассуждая так же, как при доказательстве оценки (27), нз (3!),(32),(37), (38) с помощью индунции получаем аь ) ш1п(1/(25); а !], й =О, 1,...
Обозначим рь —— (Ьь — 1)(хь ! — хь). Тогда из (ЗЗ) следует в„„! — — х — р„/6, г, рь — — 62 „((хь — еь „!) (40) Далее, с учетом (32),(40) имеем р„! — х„„! — — (Ьь ! — !)(хь — хь+,) — хь „! — — 62 „!(хь — хь „г) — х = ь !(х — эь + ! + а„+ ! / (еь О ! )) — хв —— рв — хь + ь» ! 66 + ! / (вь О !) Тогда для любого х, е Х„получаем 2 ! Р, — х„, -1 х ! =! Рв -х„-1 х ! + 2 а „, Ьв Н (/ (еь „, ), Рь — хь -! х ) ! а»м Ьь „, ]/ (е„щ ) ! или с учетом (40) ]Р„,— хь -1-х„]2-]Р— хь+х„]2=2пь Он(еь ),(ьь !Рь — Рь)-»(Р -ьь хь)-1-ь„„х,)+ + пьг , Ььа !]/'(еь .)!'=2 ь !(Ьа ! - 1)(/'( „„ ), рь ) -» +2пь !Ьь !(/ (оь !), х — оь !)+аь~„(ьь, !]/ (еь !)[2, й = О, 1,... (4!) Заметим, что (3!) с учетом (32) можно переписать в виде /(оь) — /(хь) ) (пь/2)]/'(еь)]2.
Для й + 1-й итерации это неравенство имеет вид /(е + ) ) /(хь,)-~- 2аь „!]/'(хь+ )! . (42) Из теоремы 4.2.2 с учетом (42) получаем (/(о + !), х„— о„„!) </(х ) — /(оь г !) (/, — Пхв»!) — 2аь г]/(еь, !)! . (43) Далее, из теоремы 4.2.2 и из (40), (42) следует (па+ !/2РГ (оьг !)! </(вь „!) — /(хьь !) </(хь) — (/(вьт !),хь — еьэ !) — /(х„+!) = =/(хь) — Пхь „!) — (/~(оь !), рь)/Ьь „! откуда (/'(е <), рь) ( Ьь ![(/(хь) — /(хь !)) — (аь !/2)]/'(еь !)]2]. (44) Обозначим о„= /(хь) — /,.
Подставим оценки (43), (44) в (41). С учетом (32), (34) получим ]р + — х ! + х,! — ]рь — хь + х ! ( < 2аь+,(Ь + ! — !)Ьь „!(оь — ай э ! — (пь О !/2)]/'(ейь <)]2)+ » 2а 6„( — о — (и„!/2)]/ (о„!)]2)+ аг ! Ьь г! ]/г(в ! Иг 2 2 2 а = 2а„, Ь,аь — 2а„„оь (Ьь -~-Ь „!) < 2аьЬьаь — 2аь „!Ьь !аь, ! Таким образом, ]р, — хО, -~х]2 — ]р — х +х]2 <2п 62 в — 2а, !Ь~ !а !, го=01 Суммируя эти неравенства по т от 0 до некоторого т = й — 1, получим ]рв — ха + х„]2-1-2ааьга„( 2аебвгоз+ ]рз — х -» х„]2 Отсюда с учетом равенств Ь = 1, ро = О, оценок (35), (39), произвольности выбора точки х из Х, приходим к оценке (35).
Теорема 5 доказана. С] Отметим, что метод (31)-(ЗЗ) не обеспечивает монотонное убывание функции /(х) на псследовательностяк (хь),(оь). Сравнение оценок (24) и (Зб) поназывает, что для выпуклых гладких аадач овражный метод имеет более высокую скорость скодимости, чем градиентный метод (3), (9), В [523] показано, что оценка /(хь) — /, = О(1//Ог) является неулучшаемой на этом классе функции среди всех методов, использующих лишь значения /(х), /'(х). 6. Остановимся на непрерывном варианте градиентного метода. В атом методе вместо итерационного процесса (3), порождающего траекторию (хь), которая зависит от дискретного времени й = О, 1,..., за основу берется система дифференциальных уравнений: х(Ь) = — п(Ь)/'(х(6», Ь > О, (45) где п(Ь) > 0 заданная функция (параметр метода). Эта система описывает движение материальнои точки, движущеися в силовом поле, задаваемом антиградиентом ( — /'(х», со скоростью х(2), пропорциональной антиградиенту в точке х(6).
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
