Ф.П. Васильев - Методы оптимизации (1125241), страница 89
Текст из файла (страница 89)
Таким образом, равенства (24) при Ь =0 верны. Сделаем индуктивное предположение: пусть для некоторого ь > ! имеют место равенства (1'(хь ), рь !) =О, (1 (хь !)~ рь !) = !1 (жь !)! Тогда из (23) при аь >0 получим дь (аь) = -(1(жь г !), Рь) =О. Если же аь — — О, то хь + ! = хь и 0<~,~(0) (1~(хь),„„)= (1(х,),1'( ь)-д,р,,)= — (у'(х,н2=-(у'(жь„)(2<О,поэтому 1(ж„,) =0 и (1г(хь,), рь) =О. Наконец, (1 (хь), р,) = (1 (х ), 1 (хь) — !Уь рь !) = (1 (хь)! . Равенства (24) доказаны.
Из первого равенства (24) и определения (22) вектора рь следует (Р ! =(У (жь) — лР! = !1 (хь)! +Д~(Р ! (25) 3. Пользуясь соотношениями (24), (25), установим сходимость метода сопряженных направлений (2!)-(23),(18) Теорема 1. Пусть функция 1(х) сильно выпукла на Е", 1(ж)е С'!(ЕЯ).
Тогда яри любом выборе мноакества То моментов обновлении и любом начальном приближении жо последовательность (х ), олргделяемая условиями (21)-(23), (18), скодитсл к точке х„ минимума функции 1(ж~ на Еч, причем справедливы оценки 0 < аь — — 1(хь) — 1, ( д" ао, (х, — х,(2 < — д" а, й =О, ! 2 2 (26) з где д = 1 — и, 0 < д < 1, Р— постоянная из теоремы 4.3.3, Ь вЂ” константа Лил- 6(„2+ 52) тица для градиента 1'(х) на Е", Доказательство. Из теоремы 4.3.! следует существование и единственность точки х„в которой 1(ж,) = 1, =1и!1(ж). Функция дь(а) = 1(хэ — арь) при рь рО также сильно выпукла, и условия (23) однозначно определяют величину аь > О. Будем считать, что рь фО, 1'(жь) Ф О, аь > 0 ПРи всех Ь = 0,1,..., ибо в пРотивном слУчае из (24) пРи Рь = 0 полУчим 1'(ж,) = 0 и хь — — х, — решение задачи (17).
В силу выбора аь при всех ж >0 имеем 1(хьж !) < 1(жь — арь). Отсюда и из леммы 26! с учетом второго равенства (24) получим 1(хь) — 1(хь „!) > 1(хь) — 1(жь — арь) > а(1'(хь), рь) — -~у — !Рь(2 = =а(1 (хь)! — — (Рь! а >О й =0 1, (27) Докажем теперь неравенство (28) Согласно теореме 43 3 имееми(хь — хь !! =Раз !!Рь !! <(1 (жь)-1(хь-г) хь™хь — г)= = (1'(ж ) — 1'(хь !), Рь !)(-аь !).
Отсюда с Учетом Равенств (24) полУчаем иа (р, <! ((1(х !),Рь !)=!1(х„)(. Тогда из (18) следует !д ! < !1 (х )(Ъ(жь — х„!!(1 (хь !)! < !1(жь)(7. ь-~(рь-1!О ь-г(рь ~!'Гг =Ер '!1(жь)0!Рь-гг' т. е. Дь(рь !! < Х Р (1~(жь)(, й =О, 1,... Отсюда и из (25) получим (рь(2 ( (1'(хь)!2(1+ А~и 2), что равносильно неравенству (28). Теперь нетрудно доказать оценки (26). Из (27) с учетом (28) имеем а„— а, „! > а (! — гг-1(1(хь)!~, чж > О, й =О, 1,... т/ Следовательно, аь — аь „, > гпах а!1 — — )(1(хь)(2= 2(1'(хь)(~, в =О, 1, во х 27~ Но2иаь <!1 (хь)(2 (см. неравенство(1 18)), поэтому аз-аь „! > граь или аз ! <(1-ти)аь= = даь, й = О, 1,... Отсюда следует первая из оценок (26).
Вторая оценка (26) вытекает из первой оценки и неравенства (4.3.3). Остается заметить, что 0 < д < 1, ибо и < Ь, Теорема доказана. П Отметим, что оценки (26) являются довольно грубыми. Более тонкие исследования показывают, что метод сопряженных направлений иа самом деле имеет более высокуго скорость сходимости, чем это следует иэ оценок (20). В то же время этот метод ненамного сложнее метода скорейшего спуска.
Недостатком метода сопряженных направлений является его чувствительность к погрешностям при определении величины аь из условия (23) — недостаточно точное определение аь может привести к ухудшению сходимости метода, 4. В методе (7), (9), (1 1), (12) направления Рь, р!,..ч рь строятся с помощью процесса А-ортогоиализвции последовательно вычисляемых градиентов 1(то), 1'(ж,),, , 1'(хь ), и поэтому этот метод для задачи (1) и полученный на его основе метод (21)-(23) для задачи (17) в литературе часто называют методом солряжгннык градиентов. В общем случае в методе сопряженных направлений могут быть использованы и другие способы построения векторов рь, отличные от (22).
А именно, пусть направления ни р!,.,ч рь, удовлетворяющие условиям (10), уже известны и с их помощью последовательно построены точки ж„ ..ч хь „, по формулам (21), (23). Следующий вектор рь „г будем определять из условий (рь „1, А рг) = О, 4 = О, 1,..., й. В случае квадратичных фунйций (1) формула (8) остается справедливой при любом выборе векторов нг, рг, , рь в (21), (23), поэтому условие ортогональиости вектора Рь ! К ВЕКтОРВМ АРЭ, АР!,..., Арь ЗДЕСЬ ПРИВОДИТ К РаавнетзаМ (р„„дг) = О, д,.
= 1'(*2) — 1'(жз „,), ' = О, 1, .. ч и (29) Условия (29) имеют смысл и для неквадратичных функций, и ими пользуются для определения р„„, в общем случае. Обычно вектор рь „, ищут в виде (61; 71; 76; 222; 374; 586; 759] Р„„=Е„,1(х„„), Е„„=Е,+Ан„, (30) зо! $ 10. МЕТОД НЪЮТОНА 300 Гл. 6. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ и Упражнения (3) 9 зО. Метод Ньютона з' где матрица Ьугь определяется из условий (29). Нетрудно видеть, что перечисленные условия (29),(30) матрицу ГьНь определяют неоднозначно и в зависимости от того, как распорядиться этим произволом, можно получить различные варианты метода сопряженных направлений.
Если на каком-либо шаге Нь — О, то метод (2!), (23), (29), (30) обновляют, полагая А, = à — единичная матрица. Приведем один из вариантов этого метода, в котором матрицы ~» определяются по правилу а,=% — =г(  — г( ) и (Нд )(Н дь) (Оч чь) В [603) предлагается и исследуется метод сопрюкенных направлений, позволяющий за конечное число итераций найти точку минимума квадратичной функции (1) иа множестве, задаваемом линейными ограничениями типа равенств и неравенств. Различные варианты метода сопряженных направлений, более тонкие оценки скорости сходнмости читатель может найти з !741 374; 603].
1. Показать, что точка ею полученная методом сопряженнык направлений для квадратичной функции (!) при То = Я, есть точка минимума этой функции на гиперплоскости, прозодящей через точку яо и натянутой на векторы У'(яо),7'(я!),,7'(яь !). 2. Описать метод сопряженных направлений для функции 7(я) = (Ах — Ь(З, я е Е", где А — матрица порядка гп х и, Ь Е Еы. До сих пор мы рассматривали методы первого порядка в так называются методы минимизации, использующие лишь первые производные минимизируемой функции. В этих методах для определения направления убывания функции используется лишь линейная часть разложения функции в ряд Тейлора. Если минимизируемая функция 7'(х) дважды непрерывно дифференцируема и производные 7'(х), Гл(х) вычисляются достаточно просто, то возможно применение методов минимизации второго порядка, которые используют квадратичную часть разложения этой функции в ряд Тейлора.
Поскольку квадратичная часть разложения аппраксимирует функцию гораздо точнее, чем линейная, то естественно ожидать, что методы второго порядка сходятся быстрее, чем методы первого повядка, Ниже будет рассмотрен метод Ньютона, имеющии квадратичную скорость сходимости на классе сильно выпуклых функций. Здесь мы пользуемся следующей терминологией, принятой в литературе: говорят, что последовательность (хь) сходится к точке х, с линейной скоростью или со скоростью геометрической прогрессии (со знаменателем д), если, начиная с некоторого номера, выполняется неравенство (хьь! — х,! < 9)хь — х„~, 0 < д < 1; при выполнении неравенства )хьт.— х.! < дь(хь — х,~, где (д ) — ьО, говорят о сверхлинейной скорости сходимости последовательности (х„) к х„, а если здесь да=С(хь — х„!' ', т. е.
(хье! — х,!<С(х — х,(, то говорят о скорости сходимости порядка з (при в=2 получим квадратичную скорость сходимости), Для некоторых методов выше была установлена линейная скорость сходимости на классе сильно выпуклых функций; в тех случаях, когда (хь — х,~ = 0(1/й), скорость сходимости ниже линейной; для метода сопряженных направлений можно показать сверхлинейную скорость сходи- мости 1603).
д. Опишем метод Ньютона для задачи 7(х) — ь !п(; х Е Х, (1) где 7(х) Е С'(Х), Х вЂ” выпуклое замкнутое множество из й" (например, Х = Е'*). Пусть х е Х вЂ” некоторое начальное приближение. Если известно й-е приближение ха то приращение функции )'(х) Е Сз(Х) в точке хь можно представить в виде 7(х) — 7"(хь) = (~'(хь), х — хь) + кл(~"(х )(х — х„), х — х„) + о(~х — хьюз). Возьмем квадратичную часть этого приращения 7' (х) = (у'(х ), х — х ) + -(ул(х )(х — х ), х — х ) и определим вспомогательное приближение х„из условий хз Е Х, уь(хь) = !п1,7~ (х). Следующее (й + 1)-е приближение будем искать в виде х ! —— х +сть(хь — х), 0<ель<1. (4) В зависимости от способа выбора величины а„в (4) можно получить различные варианты метода (2) — (4), называемого методом Ньютона.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
