Ф.П. Васильев - Методы оптимизации (2002) (1158201), страница 90
Текст из файла (страница 90)
4. В методе (7), (9), (11), (12) направления Вэ, р1,..., рь строятся с помощью процесса А.ортогонализации последовательно вычисляемых градиентов Е(хо), Е'(х,) ..., Е'(хь), и поэтому этот метод для задачи (1) и полученный на его основе метод (21)-(23) для задачи (!7) в литературе часто называют методом сопряжением градиентов. Б общем случае в методе сопряженных направлений могут быть использованы и другие способы построения векторов р„, отличные от (22). А именно, пусть направления и1, р1,, рь, удовлетворягощие условиям (10), уже известны и с их помощью последовательно построены точки х1,..., хь „1 по формулам (21), (23).
Следу1ощий вектор рь „1 будем определять из условий (рь+1, Ар;) =О, | = О, 1,..., й. В случае квшгратичных функций (1) формула (8) остается справедливой при любом выборе векторов рэ, р1,, рь в (21), (23), поэтому условие ортогональности вектора рь „1 к векторам Аро, Ар|,..., Арь здесь приводит к равенствам (р„„дг)=о, д|=Е'(х,.)-Х'(х,.„), =0,|,...,й, (29) Условия (29) илгеют смысл и для неквадратичных функций, и ими пользуются для определения рь „1 в общем случае. Обычно вектор рь+1 ищут в виде [61; 71; 76; 222; 374; 586; 7591 Рь 1 —— Нь „1Х'(хь „1), Нь „1 —— Пь + ЛНз, (30) 6 10.
МЕТОД НЬЮТОНА 301 300 гл. б. метОДЕ4 мнннмнзйцнн функцнй мнОгнх переменных Упражнения (3) 9 10. Метод Ньютона (л где матрица СтНь определяется из условий (29). Нетрудно видеть, что перечисленные условия (29),(30) матрицу 7ьНь определяют неоднозначно и в зависимости от того, как распорядиться этим произволом, можно получить различные варианты метода сопряженных направлений. Если на каком-либо шаге Нь †- О, то метод (21), (23), (29), (30) обновляют, полагая А = 7 — единичная матрица. Приведем один из вариантов этого метода, в котором матрицы Нь аопределяются по правилу Л,,=Л„- Л '.,=Пь З-Гт.,>, И-А (774, )(Н. д. )т (779ги «а) В [6031 предлагается и исследуется метод сопрязкенных направлений, позволяющий зв конечное число итераций найти точку минимума квадратичной функции (1) на множестве, задаваемом линейными ограничениями типа равенств и неравенств.
Различные варианты метода сопряженных направлений, более тонкие оценки скорости сходимости читатель может найти а 174; 374; 6031. 1. Показать, что точка мь, полученная методом сопряженных направлений для квадратичной функции (1) при То = ю, есть точка минимума этой функции на гиперплоскости, проходящей через точку яо и натянутой на векторы 7'(яо),7'(м~),...,7 (иь 1). 2. Описать метод сопряженных направлений для функции 7(я) = )Аз — ь1', я е е", где А †матри порядка отх и, Ь е Ем.
До сих пор мы рассматривали методы первого порядка — так называются методы минимизации, использующие лишь первые производные минимизируемой функции. В этих методах для определения направления убывания функции используется лишь линейная часть разложения функции в ряд Тейлора. Если минимизируемая функция 7(х) дважды непрерывно дифференцируема и производные 7'(х), ул(х) вычисляются достаточно просто, то возможно применение методов минимизации второго порядка, которые используют квадратичную часть разложения этой функции в ряд Тейлора. Поскольку квадратичная часть разложения аппроксимирует функцию гораздо точнее, чем линейная, то естественно ожидать, что методы второго порядка сходятся быстрее, чем методы первого порядка.
Ниже будет рассмотрен метод Ньютона, имеющий квадратичную скорость сходимости на классе сильно выпуклых функций. Здесь мы пользуемся следующей терминологией, принятой в литературе: говорят, что последовательность (хь) сходится к точке х, с линейной скоростью или со скоростью геометрической прогрессии (со знаменателем д), если, начиная с некоторого номера, выполняется неравенство (хлт,— х,~ < д)хь — х„), 0 < 1) < 1; при выполнении неравенства )хь+,— х„! < дь)хь — х,), где (дь) — «О, говорят о сверхлинейной скорости сходимости последовательности (х,) к х., а если здесь да= С~(хь — х„~!" ', т.
е. (хьт1 — х„)< С(хь — х.!', то говоРЯт о скоРости сходижости порядка з (при а=2 получим квадратичную скорость сходимости). Для некоторь|х методов выше была установлена линейная скорость сходимости на классе сильно выпуклых функций; в тех случаях, когда (хь — х„~ = 0(1/й), скорость сходимости ниже линейной; для метода сопряженных направлений можно показать сверхлинейную скорость сходи- мости !603]. 1. Опишем метод Ньютона для задачи ,7(х) - !и1; х е Х, (1) где 7(х) е С'(Х), Х вЂ” выпуклое замкнутое множество из Я" (например, Х = Е"). Пусть х е Х вЂ” некоторое начальное приближение.
Если известно й-е приближение хь, то приращение функции 7(х) е Сз(Х) в точке хь можно представить в виде 7(х) — 7(хь) = (7 (хь), х — хь) + — (7 (хь)(х — хь), х — хл) + О()х — хь) ). Возьмем квадратичную часть этого прнрапгения 7ь(х) = (7 (х„), х — хь) + — (7 (х,)(х — х„), х — х„) н определим вспомогательное приближение хл из условий хь Е Х, уь(хь) =!п1У (х). Следующее (й + 1)-е приближение будем искать в виде хач, = ха + сть(гч Е— хь), 0 < сть < 1. (4) В зависимости от способа выбора величины аь в (4) можно получить различные варианты метода (2)-(4), называемого методом Ньютона.
Укажем несколько наиболее употребительных способов выбора сгь. 1) В (4) можно принять аз=1, й=0,1,... (5) В этом случае, как следует нз (4), хьт, = х„, й = О, 1,..., т. е. условие (3) сразу определяет следующее (й + 1)-е приближение. Иначе говоря, хь, Е Х, гь(хь „1) = !п17ь(х), й = О, 1,... (6) В частности, когда Х = Е", в точке минимума функции уь(х) ее производная 7ь'(х) обращается в нуль, т, е. 7ь'(хь ..) =)"(хь)+ ~а(хь)(хье, — х„) =О. (7) Это значит, что на каждой итерации метода (2) — (5) или (6) нужно решать линейную алгебраическую систему уравнений (7) относительно неизвестной разности хат, — х,. Если матрица этой системы 7л(хь) — невырожденная, то из (7) имеем х„,, = хл — (7л(хь)) '7"'(хь), й = О, 1,...
(8) Широко известный метод Ньютона для решения системы уравнений Е(х) = Я(х),..., Е„(х)) =О, х Е Е", представляет собой итерационный процесс [74; 89; 550; 6351 х, = х„— (Р"(х )) 'Е(хь), й = О, 1,..., (9) где Г'(х) — матрица, з-я строка которой равна Г,'(х) =(Е...,..., Еы.). Сравнение формул (8) и (9) показывает, что метод (8) решения задачи (1) в 303 $10.
МЕТОД НЫОТОНА !!(Х"(х)) '!! < р ', х Е Е". (16) а < 2р,'Х 'до" й = 0 1 ... (17) Ь !Г( ) ! < 2р'д, (13) 302 Гл. З. МЕТОДЫ МИНИМИЗАЦИИ ФУНКЦИЙ МНОГИХ ПЕРЕМЕННЫХ случае Х = Е" представляет собой известный метод Ньютона для решения уравнения /'(х) = О, определяющего стационарные точки функции /(х). Отсюда происходит название метода (2)-(4) и в общем случае. 2) В качестве со„в (4) можно принять о, = ЛЧ, где ь — минимальный среди 4 > 0 номер, для которых выполняется неравенство [603! Х(х,) — /(х„+ Л'(х„— х,)) > гЛ'!Х (х„)!, (10) где Л, г — параметры метода, 0 < Л; г < 1.
3) Возможен выбор аь в (4) из условий (603! О< а„< 1, д„(о„)= ппп д„(а), д (о)=/(х„+ со(х„— х,)). (11) очак~'" Заметим, что метод (2) — (4) с выбором длины шага о„по правилам (10), (! 1) аналогичен соответствующим вариантам метода условного градиента, где для определения х„использовалась линейная часть приращений, а в методе Ньютона — квадратичная часть (2). Если /„(х) из (2) сильно выпукла, а Х = Е" или Х задается линейными огранйченнями типа равенств или неравенств, то для определения х, из (3) могут быть использованы методы из $8, 9.
Следует заметить, что задача (3) в общем случае может оказаться весьма сложной и сравнимой по объему требуемой для своего решения вычислительной работы с исходной задачей (!). Метод Ньютона для решения задачи (1) обычно применяют в тех случаях, когда вычисление производных /'(х), /"(х) не представляет особых трудностей и вспомогательная задача (3) решается достаточно просто. Достоинством метода Ньютона является высокая скорость сходимости.
Поэтому, хотя трудоемкость каждой итерации этого метода, вообще говоря, выше, чем в методах первого порядка, но общий объем вычислительной работы, необходимой для решения задачи (1) с требуемой точностью, при применении метода Ньютона может оказаться меньше, чем при применении других более простых методов. 2. Сначала исследуем сходимость метода Ньютона (2)-(4) с выбором шага со„из условия (5) при условии Х = Е" или, проще говоря, метода (8). Теорема 1.
Пусть функция /(х) сильно выпукла на Е, /(х)е е С'(Е") и, кроме того, !!У"(х) — о "(у)!! ( Х |х — у!, х, уЕ Е", Х =сова! > О. (12) Пусть начальное приближение х выбрано таким, что где р > 0 — постоянная из теоремы 4.3.4, а д — некоторая константа, 0 < д < 1. Тогда последовательность (х„), определяемая условиями (8), существует, сходится к точке х, минймума /(х) на .Е", причем справедлива оценка !х,— х!<2рХ 'д", й=0,1,...
(14) Доказательство. Существование и единственность точки х, установлена в теореме 4.3.1. Согласно теореме 4.3.4 (/"(х)б,с) ) )р!6!', хеЕ", 6 еЕ~. (15) Отсюда следует, что система уравнений /"(х)6 = 0 имеет единственное решение 6 = 0 и, следовательно, матрица /о(х) невырожденная при всех хе Е". Это значит, что система (7) при каждом й =О, 1,... имеет, и притом единственное, решение, т.
е. последовательность (х ) однозначно определяется условиями (8). Кроме того, полагая в (15) с = (/"(х)) 'х, получим р!(Х"(х)) 'г/~<(х,(/"(х)) 'г) <!х!!(/"(х)) 'г! илн !(/о(х)) 'х!< !г!!б при всех г Е Е . Это значит, что Введем числовую последовательность а, = !/'(х„)! и покажем, что При й = 0 неравенство (17) следует из условия (13). Пусть (17) справедливо при некотором й > О.
Йз условия (8) и формулы (2.6,5) имеем /'(х „,)=/'(х,)+ 1 /" (х +Г(хо,,— х„))(х„„— х )о!б= о = '1(/о(х„) — Х"(х +Г(хо„,— х„))]о!!(Х"(х„)) 'Х'(хо). о Отсюда и из (8), (12), (16) с помощью предположения индукции получим а,~, ( (Ц2)!х„, — х !р 'а„( (Х/(2ро))аоо ( < (Х/(2 о))(2 „г/Х )о(, о )о (2 о/г ) м ~ Неравенства (17) доказаны. Тогда из теоремы 4.3.3 с учетом равенства /'(х,) = 0 имеем р!хь — х„! < (/'(х ) — Х'(х,), хь — х,) < !Х'(х„)!!хо — х.! или !х — х„! < а„р '. Отсюда и из неравенства (17) следует оценка (14).
Теорема 1 доказана. П Как видно из оценки (14) и как показывает практика, метод Ньютона (8) сходится очень быстро. Однако у него есть один существенный недостаток; для его сходимости начальная точка х должна выбираться достаточно близкой к искомой точке х,. Это требование в теореме 1 выражено условием (13), означающим, что !х — х,! < а р ' < (2р/Х )д. Приведем пример, показывающий, что при отсутствии хорошего начального приближения метод (8) может расходиться. Пример 1.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
