Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 73
Текст из файла (страница 73)
$ ! ГРАДИЕНТНЫЙ МЕТОД 243 (19) ;1,:. Нс с!«. !!с, откуда имеем х„+, — — х, — сс Ас Г"'(х«), г«»>0, Ь=0,1,..., 242 Гл. В. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ Для ускорения сходимости этого метода прн поиске минимума «овражной» функции можно предложить следующий эвристический прием, называемый овражным методом.
Сначала опишем простейший вариант этого метода. В начале поиска задаются две точки е«, еп из которых производят спуск с помощью какого-либо варианта градиентного метода, и получают две точки х, х, на «дне оврага». Затем полагают е» вЂ” х! — (х! — х«)!х! — х»~ Ь в!яп (! (х~) .с (~0)) где Ь вЂ” положительная постоянная, называемая овражным шагом. Из точки тю которая, вообще говоря, находится на «склоне оврага», производят спуск с помощью градиентного метода и определяют следующую точку х на «дне оврага», Если уже известны точки х, х„..., х„, Ь > 2, то из точки о„! = х — (х„— х» !)!х — х„,~ 'Ь в!9п 1Г(х„) — !"(х«!)) совершают спуск с помощью градиентного метода и находят следующую точку х,, на «дне оврага» (см.
рис. 5.3; спуск из точки с!с в точку х„ состоящий, быть может, из нескольких итерационных шагов градиентного метода, условно изображен отрезком прямой, соединяющей точки ею х„ Ь = О, 1,...). Величина овражного шага Ь подбирается эмпирически с учетом информации о минимизируемой функции, получаемой в ходе поиска минимума. От правильного выбора Ь существенно зависит скорость сходимости метода.
Если шаг Ь велик, то на крутых поворотах «оврага» точки о„могут слишком удаляться от «дна оврага» и спуск из точки и„в точку х!«может потребовать большого объема вычислений. Кроме того, при больших Ь на крутых поворотах может произойти выброс точки о» из «оврага», и правильное направление поиска точки минимума будет йотеряно. Если шаг Ь слишком мал, то поиск может очень замедлиться и эффект от применения овражного метода может стать незначительным. Эффективность овражного метода может существенно возрасти, если величину овражного шага выбирать переменной, реагирующей на повороты «оврага» с тем, чтобы: 1) по возможности быстрее проходить прямолинейные участки на «дне оврага» за счет увеличения овражного шага; 2) на крутых поворотах «оврага» избежать выброса из «оврага» за счет уменьшения овражного шага; 3) добиться по возможности меньшего отклонения точек е„от «дна оврага» и тем самым сократить объем вычислений, требуемый для градиентного спуска из точки е» в точку х„, Ь = О, 1,...
Интуитивно ясно, что для правильной реакции на поворот «оврага» надо учитывать «кривизну дна оврага», причем информацию о «кривизне» желательно получить, опираясь на результаты предыдущих итераций овражного метода. В работе !657! предлагается следующий способ выбора овражного шага; (20) где гс, — угол между векторами и» вЂ” х„о х, — х„,, определяемый условием сов сс« = (е» вЂ” х „х — х» !)(о» вЂ” х» !) !)х» — х„ а постоянная с > 1 является параметром алгоритма.
Точка «с„»! определяется из (19) при Ь = Ь»« Р Разность сов гс» — сов сх„ , в равенстве (20) связана с «кривизной дна оврага» и, кроме того, обладает важным свойством указывать направление изменения «кривизны». А именно, при переходе с участков «дна оврага» с малой «кривизной» на участки с большей «кривизной» будем иметь сов сс„ — сов сс„ ! < 0 (см, рис. 5.4). Тогда, в силу (19) имеем Ь»«! < Ь„, т. е. овражный шаг уменьшается, приспосабливаясь к повороту «дна оврага», что в свою очередь приводит к уменьшению выбросов точки юс»! на «склоны оврага». При переходе с участков «дна оврага» с большой «кривизной» х на участки с меньшей «кривизной», наоборот, сов сс„ — сов сс, , > О, поэтому овражный шаг увеличится и поя- "с! антея возможность сравнительно бы- »»с ас! стро пройти участки с малой «кри- ~»! визной», в частности, прямолинейные участки на «дне оврага».
Если «кри- «с« визна дна оврага» на некоторых участках остается постоянной, то разность «с сов«с — сов с«„, будет близка к нулю, и поиск минимума на таких участ- хс« ках будет проводиться с почти посто- л с х»ч ! янным шагом, сформированным с учетом величины «кривизны» при выходе »«с на рассматриваемый участок. Рис.
ВА ! !араметр с в равенстве (20) регулирует «чувствительность» метода к изменению «кривизны дна оврага», н правильный выбор этого параметра во многом определяет скорость движения по «оврагу». Иекоторые эвристические соображения по поводу выбора с и другие аспекты применения овражного метода обсуждены в [657]. Выражение (20) для овражного шага удобнее преобразовать так Ь Ь ссс с — ссс с , с сасс — соса ссс — сссс — »с"' — =Ь с ' '-'=...=5 с + ~~с — 1 2 Ь»«! =Ас"', А = Ь,с "'"' =сонэ!>О, Ь =2,3,...
Другой способ ускорения сходимости градиентного метода заключается в выборе подходящей замены переменных х = д(с ) = (дс(ь ),..., д (в)) с тем, чтобы поверхности уровня функции 7(д(с)) = С(с) в пространстве переменных 5 = (5!, .. «5") были близки к сферам.
Заметим, что СЯ) =(дЯ))т Г'(д(Е)), где д(Е) =(дч,(Е)) — матрица, »-я строка которой представляет собой д,.'(Е) = (дчс(5),..., дя.(с)), а (дЯ)) ! — матрица, полученная из дЯ) транспонировайием, В пространстве переменных Е градиентный метод выглядит так: 5„„= 5„- !1»(д (5»))'У'(д(5,)), !1„> О, Ь =О, 1,... В пространстве исходных переменных х =(х',..., х") этот подход можно трактовать как итерационный процесс вида $1 ГРАДИЕНТНЫЙ МЕТОД 245 244 Гл. 5.
МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ вЂ” где А„— некоторая невырожденная матрица порядка и х ть, представляющая собой параметр метода. То, что на этом пути можно добиться существенного ускорения скорости сходимости итераций, подтверждается, например, излагаемым ниже методом Ньютона, в котором полагается А„= (/е(хь)) ', й = О, 1,, О методах минимизации овражных функций и различных приемах ускорения сходимости итерационных методов см.
174; 84; 89; 222; 442; 525; 550; 586; 603; 657; 721; 738; 7691. 4. Исследуем сходимость другого варианта градиентного метода (3), в котором параметр а„ определяется иэ условии (9) с помощью дробления, А именно, пусть ! < е < 2, а > 0 — фиксиооввнные числа, а 1 > 0 — наименьший номер, для которого выполняется неравенство [374; 603] /(хь) — /(хь — 2 'а/'(хь)) > 2 ' 'ае[/'(хь)[Э, (21) и пусть аз — — а/2'. (22) Теорема 4. Пусть е задаче(1) /,>-со, Х„рЯ, функция/(х) еьшукла на Е",/(х)е е С~ '(Е"). Тогда дгя последогательности (хь), определяемой методом (3),(21),(22), имеют место соотношения (11) и, более того, существует точка о, Е Х„такал, что (хь) — ~ о„ [хь, — о„[( [хь — о,[, Р(х эп Х„) <Р(хь, Х,), А=О, 1,..., (23) причем равенство е (23) возможно лишь при хь — — хь+ ! —— ...
— — о„спраеедлиеа оценка 0</(х ) — /, ((ш|п((2-е)/(25); аН ~(2/г)[хо-о,[хй ! =О(1/й), й =1,2,..., (24) и если Х,— аффинное множество, ток,=Р» (хо), т. е. о,— ближайшая к то точка иг Х,. Доказательство. Сначала покажем возможность выбора аь из условий (2!), (22). Пусть у ) 0 — наименьший номер, для которого Ь 2 Ух<2 — е; (25) здесь Ь > 0 — константа Липшица для /'(х). Из неравенства (2.6,7) при у = хь, х = хь— — 2 'а/'(хь) с учетом (25) имеем /(хь) — /(х~ — 2 Уа/'(х„)) > (/'(хь),2 Уа/'(х )) — Ь 2 ЭУ а [/'(хь)[Э = =2 У а(2 — 2 УаЬ)[/'(хь)[э) 2 У !хе[/'(хь)[э.
(26) Это значит, что при Ь = У неравенство (21) выполняется, и, следовательно, минимальный номер Ь ) О, при котором справедливо (21), существует н не превышает номера У из (25). Покажем, что для аь из (21), (22) справедлива оценка аь > пцпО2 — г)/(25); а), Ь =О, 1,...
(27) Сначала рассмотрим случай а > (2 — г)/(2Ь). Тогда оказывается, аь > (2 — е)/(25) при всех Ь = 0,1 ... В самом деле, для номера у из (25) в этом случае имеем 2 уа < (2 — г)/Ь < < 2 ут а, у > О. Поэтому с учетом правила выбора номера С определения аь из (22) и неравенства Ь < у получим и = а/2' ) а/21 > (2 — е)/(25 ), Пусть теперь а < (2 — г)/(25 ). Тогда неравенство (25) и, следовательно, (26) выполняется при У = О. Отсюда и из (21) следует, что Г =О. Согласно (22) тогда а = а/2о = а, Ь =О, 1,, Объединяя оба рассмотренных случая, приходим к оценке (27). Далее, возьмем лгобую точку х, е Х,. Иэ (3), (21), (22) и теоремы 4.2.2 имеем (е/2)аь[/'(хь)[х < 7(хь) — /(хь !) < /(хь) — /(х,) < (/'(хь),хь — х„). (28) Кроме того, из (3) следует [хь+ ! — х,[з = [хь — аь/~(хь) — х,[х = [хь — х„[э — 2сгь (/ (хь), хь— — х„) + аьэ[/'(хь)[з.
Отсюда с Учетом оценки (28) полУчаем — [' < [х„- х„['- ( — 1)а'[/'(хь)[' ' « ' 2 (29) Следовательно, [хь ! — х,[э<[хь — х[ «...[хо — х[ Чх,еХ. (30) Далее, положим у у гО наименьшии номер для которог 2 Уаь, < 1/Ь. Нетрудно видеть, что тогда .(.ь)-/(„,-2-заь,/г(.,))>2-1-! [/(. )[г (з7) (38) Из (ЗО) вытекает существование предела Ош [хь — х,[з и ограниченность последовательности х 1г. Тог Ь чч (хе1г. огда найдется подпоследовательность (х„), сходящаяся к некоторой точке е,. Ив (27), (29) следует, что (/ (хь )) г/ (о) =-О, По теореме 4 2 3 тогда е„еХ„, Приняв х„= о„, из (ЗО) получаем 1пп [хь — о,[= йш [хь — е,[=0, т. е.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
