Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 89
Текст из файла (страница 89)
Так как р. фО, то (Ар. Р.) > 0 и последние равенства возможны лишь при 7| =О, ~ыр, П Тем самым все этапы индукции проведены, следующее (й + 1)-е прибли- жение хг, построено. Если 7"'(хг х,) = О, то х„х, = х„— решение задачи (1) найдено. Ъсли гке 7"'(хг~,) ~ О, то согласно индукции процесс можно про- должать дальше. Метод сопряженных направлений для задачи (1), заключающийся в по- строении последовательности (х„1 по правилу (11), где а„рг определяют- ся из (?), (9), (12) (или (14)), р = 7"'(х ), описан.
Название этого метода объясняет следующее 'О п р е де лен и е 1. Векторы'р, р„..., р„называются сопряженными относительно матрицы А или А-ортогональными, если (рг, р,) = при всех г фу, 0 < г', 7' < й. Н рудно' видеть, что для квадратичной задачи (1) метод сопряженных ет о и на р правлений закончится за конечное число итераций нахождением т чк х.. В самом деле, векторы 7'(хь), 7'(х,),..., 7'(х„),..., получаемые этим мг е- тодом образуют ортогональную систему () (х ) г (х )) =0 г л ~ Од в и-мерном пространстве не может быть более п ненулевых взаимно ортого- нальных векторов. Следовательно, найдется номер й, 0 < й < гг такой, что 7'(х„) =О.
Тогда х„ = х, — решение задачи (1), 2. Перейдем к рассмотрению задачи ,Г(х) > 1п1| х х Х = Е (17) где функция 7'(х) Е С'(Я"), причем в отличие от задачи (1) здесь 7'(х) не предполагается квадратичной. Так как формула (9) содержит матрицу А, характеризующую квадратичную функцию (1), то описанный выше метод сопряженных направлений (7), (9), (11), (12) не может быть непосредст- венно применен для решения задачи (17). Поэтому сначала формулу (9) приведем к виду, не содержащему матрицу А. С учетом равенств (6), (8) числитель и знаменатель дроби (9) можно преобразовать так: (А,„„~(.„)) =(У(.„,)-7(.„),7'(*г))~„-~, =-~7'(*.)/'~ и (АР, „Р,,) = (7(х„,) — 7(х„), Р„,)аь ', = (7(хг,), Рг,)аг', = = (7'(х„,) Г'(хг,) — )гг,р„г)а„', =)7'(х„,)/~ах ',.
Тогда формула (9) запишется в виде у (г (хг) г (хг-|) г( ь)) (18) )7 (хг |)) или ;::,:г|::., где 3 У( ~Н' (19) )у!( цг ' Кроме того, вспоминая, что для функции (1) А =ух(х„), формулу (9) мо „о представить еще и в такой форме: у (ух(хг)гг и 7'(хь)) (20) (г (хг)гг-г Рг г) Для квадратичной функции (1) все три формулы (18)-(20) дают одну и ту же величину )г„. Но если функция 7" (х) отлична от квадратичной, то из этих формул будут йолучаться, вообще говоря, различные значения )3„. В результате, отправляясь от соотношений (7), (11), (12), (18)-(20), при- дем к следую|цему описанию метода сопряженных направлений для зада- чи (17).
Пусть х — некоторое начальное приближение. Будем строить подовательность (х,) по правилам х„, = х, — а, рю й = О, 1,..., ро= Г(хь)1 рг = У'(хг) ?угрг й = 1 2 ° ° 1 величина аь определяется условиями а„> О, д„(а ) = ш!и д,(а), д„(а) = Х(х„— сгр„), (23) а ьь а Д, в (22) вычисляется по одной из формул (18), (19) или (20). Отметим, что в варианте (20)-(23) метода сопряженных направлений требуется, что- бы 7(х) Е Сг(Е"), и поэтому на практике он применяется очень редко и лишь в тех случаях, когда матрица ?х(х) вычисляется достаточно просто.
6 9. МЕТОД СОПРЯ)КЕННЫХ НАПРАВЛЕНИИ 299 298 Гл. 5. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИИ МНОГИХ ПЕРЕМЕННЫХ Так как в задаче (17) квадратичность функции не предполагается, то нельзя ожидать, что описанный метод сопряженных направлений за конечное число итераций приведет к точке минимума функции Х(х) на Е". Далее, точное определение величины аь из условий (23) возможно лишь в редких случаях, поэтому реализация каждой итерации метода будет сопровождаться неизбежными погрешностями. Как показывает практика, эти погрешности, накапливаясь, могут привести к тому, что векторы (р,) перестают указывать направление убывания функции, и сходимость метода может нарушиться, Чтобы бороться с этим явлением, метод сопряженных направлений время от времени обновляют, полагая в (22) 73ь =О. Обозначим множество тех номеров й ) 1, при которых принимается Дь ж О, через Ег» Номера й е Х называются моментами обноеленыя метода.
Если метод использ)уется без обновления, то Е, =и. На практике часто берут Хо = Ттз, 2п, 3п, где и-размерность рассматриваемого пространства. Возможны и другие правила выбора моментов обновления. Кстати, если Е, = (1,2,3,...), то метод (21)-(23) превратится в метод скорейшего спуска. Если функция Е(х) не является квадратичной, то для описанного метода сопряженных направлений равенства (5), (6), вообще говоря, не выполняются. Однако, тем не менее, и в общем случае при любом выборе моментов обновления справедливы равенства (Е(хь,1), рь) = О, (Е(хь), рь) = !Е(хь)!2, й = О, 1 (24) В самом деле, при й = 0 имеем ро — — Е'(х|), поэтому (Е'(хо), рэ) = 1Е'(хо)/~. Из условий (23) при й = 0 в случае ао > 0 следует до (ао) = (Е(хо — аэро), -ро) = — (Е (х| ), ро) = О.
Если же ао = О, то х1 — — х и 0 < до'(0) = — (Е (хо), И|) =-)Е'(хо)!2 <О, так что Е (хо) = Е'(х1) =О, (Е (х1), ро) =О. Таким образом, равенства (24) при й = 0 верны. Сделаем индуктивное предположение; пусть для некоторого й > 1 имеют место равенства (Е'(хь ), рь 1) =О, (Е (хз 1), рь 1) = !Е (хь 1)! . Тогда из (23) при а„> 0 получим дь (аь) = -(Е (ха+1), рь) =О. Если же а„= О, то ха+ 1= хь и 0( '(О)= (Х'( „), „)=-(Е'(х„),Е'(х )-е рь 1)=-/Е'(х )!2= — /Е'(хьь1)!2<О,позюму Е'(х.
„,) =0 и (Е'(х„г1), р,) =О. Наконец, (Е'(х,), рь) = (Е'(хь), Х'(хь) — дарь ) = )Е'(хь)! . Равенства (24) доказаны. Из первого равенства (24) и определения (22) вектора рь следует !2 !Ег( ) д ~2 ~Ег( )!2+ дг! ~2 ! (25) 3. Пользуясь соотношениями (24), (25), установим сходимость метода сопряженных направлений (21)-(23),(!8). Теорема 1. Пусть функция Е(х) сильно выпукла иа и", Е(х) 6 Оц'(Гду). Тогда при л1обом выборг множества Го моментов обновления и тобом начальном приближении хо последовательность (х ), определяемая условиями (21)-(23), (18), сходится и точке х, минимума функции Е(х|г иа Ли, причем спразгдгигы оценки 1хь — х,)2 < — д" а, !с = О, 1,..., 2 2 ь 0 ( аь — — Е(хь) — Е, ( да го, (26) з где д =! — 2 2, 0 < д < 1, и — постоянная из теоремы 4.3.3, Ь вЂ” константа Липй(„2+ ьг) тица дхя градиента Е'(х) иа а".
Доказательство, Из теоремы 4,3.1 следует существование и единственность точки х„, в которой Е(х„) = Е, = |п1Х(х). Функция дь(а) = Е(хь — арь) при рэ ф 0 также сильно выпукла, и условия (23) однозначно определяют величину аь ) О. Будем считать, что рь ф О, Е'(х ) Ф О, а„ > 0 при всех й = 0,1,..., ибо в противном случае из (24) при р„ = 0 получим Е'(хь) = 0 и хз = х„ — решение задачи (17).
В силу выбора аь при всех а > 0 имеем Е(хь ь1) < Е(хь — арь). Отсюда и из леммы 2.6.1 с учетом второго равенства (24) получим Е(х„) — Е(хь „1) ) Х(хь) — Е(хь — арь) > а(Е'(хь), рь) — †2 (рь! = = а1Е'(хь)/~ — а /рь/~, а м О, й = О, 1,, (27) Докажем теперь неравенство 76 1рь! < !Е (х„)!, 7 игл 1(их+ 52) 1, й О, 1, (28) согласио теоРеме 4 3 3 имеем и1хь-хь 1! =магг 1!Рь 1! <(Е (хь)-Е (хь 1), хь-х, 1)= = (Е'(хь) — Х'(хь 1), рь 1)(-аь 1). Отсюда с учетом равенств (24) получаем !2 < (Ег( ) ) !Ег( И2 Тогда из (18) следует 1»ь! < (Е (хь)1ь!хь — хь 11!Е (хь 1)! ( /Е'(хг)!паз 1!РЬ 1!(»аз /РЬ 1! ) = Ьи /Е'(хз)11Р / т. е.
Дь~Рь 1! и ьл 1!Е'(хь)й й = О, 1,... Отсюда и иэ (25) получим (рь!~ < )Е'(хь))~(1+ Ь~и 2), что равносильно неравенству (28). Теперь нетрудно доказать оценки (26). Из (27) с учетом (28) имеем а„— аь „, ) а(1 — 2 — 1/Х(хь)!2, 'га) О, й =0,1, 7) Следовательно, а — а >шаха 1 — — х = — х а г 2 7 ~ 2 й=О 1 ( )!Е ( И !Е ( И но 2»аь </Е(хь)!~ (см. неравенство (1.18)), поэтому аь-аь 1> 7»аь или аь „1((! — 7и)аь—- = да, й = О, 1,... Отсюда следует первая из оценок (26). Вторая оценка (26) вытекает из первой оценки и неравенства (4.3.3). Остается заметить, что 0 < д < 1, ибо и ( Ь.
Теорема доказана. П Отметим, что оценки (26) являются довольно грубыми. Более тонкие исследования показывают, что метод сопряженных направлений на самом деле имеет более высокуго скорость сходимости, чем зто следует из оценок (20). В то же время этот метод ненамного сложнее метода скорейшего спуска. Недостатком метода сопряженных направлений является его чув. ствительность к погрешностям при определении величины аь из условия (23) — недостаточно точное определение аь может привести к ухудшению сходимости метода.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
