Ф.П. Васильев - Численные методы решения экстремальных задач (1125247), страница 78
Текст из файла (страница 78)
Из Условий (23) пРн д = 0 в слУчае ао ) 0 следУет Уо (а,) = <У' (и,— аоР,) — р)= — <У'(~г), р)=0. Если же а =О, то и =и н 0(1о (0)= = — (У'(и ), ро> = — /У'(и ))з(0, так что У'(ио) =У'(ио) = О, <У'(и,), р,> =О. Таким образом, равенства (24) прн Д = 0 верны. Сделаем нндук.
тнвное предположение: пусть для некоторого й ) ( имеют место равенства <У'(ио), рд-о> = О, <У'(ид-о), рд,> = /У'(ид 1) /о. Тогда нз (23) прн ад ) 0 получим 1 (ад) = — <У'(ид+ ), р > = О. Если же ад =О, то из+о = ид н МЕТОД СОПРЯЖЕННЫХ НАПРАВЛЕНИЙ 327 6 81 0(Х,(0)= — (У'(и,), р,) = — (У' (и,), У' (и ) — ()ьра ) = — (У'(и ) ~~= = — ) У' (и,+ ) /~(0, поэтому Х'(иьь,) = 0 и <1'(икы), рв> = О. Наконец, (У'(иь), рь) = (Х'(иь), Х'(иь) — рьрь,) = )Х'(иг) ) . Равенства (24) доказаны.
Из первого равенства и определения (22) вектора рь следует ) Ра) =)Х (иа) ()зуд т! =( У (иа)) +Рь(уд г)~, /с=1,2, ... (25) 3. Пользуясь соотношениями (24), (25), установим сходимость метода сопряженных направлений (21) — (23), (18). Теорема 1. Пусть функция 1(и) сильно выпукла на Е", У(и) ~ ж СЬ '(Е") Тогда при любом выборе множества 1г моментов обновления и любом начальном приближении иг последовательность (щ), определяемая условиями (21) — (23), (18), сходится к точке ив минимума функции 1(и) на Е", причем справедливы оценки 2 (ил — и, )~( — д"ав, к= О, 1, ..., (26) 0(а„=У(и ) — У (д~аа, согласно теореме 4.3.3 р ! и„— ие )в=разе ) рд )г((1'(и ) — х'(ид ), иь — и„д) = (У'(иа) — У'(ие ), рь ) ( — аь ).
Отсюда с учетом равенств (24) имеем Наг ~)рь-1)г ( (1'(иь-1), рг- ) = (1'(иь-1))'. Тогда ич (18) следует )()ь) ~ (/1'(иь))Х)иь — иь 1))1'(иь ~)) г( ()1'(иь))Хлгь-!рь-1)Ьссг г)рь- )г) '=Хбг '!1'(иь)))рь- ) ', т. е )бь) )рь-1) ( Хбг '(1'(иг)), )с = О, 1, Отсюда и из (25) получим (рь)г ( )1'(иь) (г(1+ Егр-г), что равносильно неравенству (28). где д = 1 — з г (О ( д ( 1), и — постоянная иг теоремы 4.3 3, А(д +Е) Х вЂ” константа Липшица для градиента Х'(и) на Е", Д о к а з а т е л ь с т в о. Иэ теоремы 4.3.1 следует существование и единственность точки ив, в которой У (иг) = У„= 1п( У (и). Функция Еп Хь(а) = У(иь — арь) при рва О также сильно выпукла, и условия (23) однозначно определяют величину аг ) О.
Будем считать, что рь чь О, Х'(и ) ~ чьО, аг) 0 при всех к=О, 1, ..., ибо в противном случае из (24) при рь = 0 получигм 1'(иь) = 0 и ие — и„— ретпение задачи (17) . В силу выбора аг при всех а) 0 имеем 1(иьы) (1(ик — ссре). Отсюда и из леммы 2.3.1 с учетом второго равенства (24) получим У(и ) — У(и„) > У(и ) — У(и — аРд)га(1'(и„), Р ) — — (Ра!г= аб 2 = а) У'(иа) (г — а — ) ра)гт а)~0, )с = О, 1, ... (27) 2 Докажем неравенство '11 )рь)г( (1'(иь))', 7 = р Е '(а+ Ее)-', Уг =О, 1, .
(28) 328 метОды минимизации Функции мнОГих нетеменных [Гл, в Теперь нетрудно доказать оценки (26), Иэ (27) с учетом (28) имеем аь — ~э+д)сг (1 — 2 ) [Х'(иь))~, сг~>0, й=О, 1, ... Следовательно, а — а )шах ~1 — — )Х'(иэ)(э= 7 )Х'(иа)(э, й=0,1, Но 2ра» < (Х'(и»)(г (см. неравенство (1.18)), поэтому ໠— а»+1) 7)га» или а»ы < (1 — 7)д)а» = да» (й =О, 1, ...). Отсюда следует первая иэ оценок (26). Вторая оценка (26) вытекает из первой оценки и неравенства (4.3.2). Остается заметить, что 0 < д < 1, ибо д» < П Теорема доказана. Отметим, что оценки (26) являются довольно грубыми.
Более тонкие исследования показывают, что метод сопряженных направлений на самом деле имеет более высокую скорость слодимости, чем это следует из оценок (26). В то же время этот метод не намного сложнее метода скорейшего спуска Недостатком метода сопряженных направлений является его чувствительность к погрешностям при определении величины сг» из условия (23) — недостаточно точное определение ое может привести к ухудшению сходимости метода. 4. В методе (7), (9), (11), (12) направления р„рн ..., р» строятся с помощью процесса А-ортогоналиэации последовательно вычисляемых градиентов Х(и,), Х'(и,), ..., Х'(и»), и поэтому этот метод для задачи (1) и полученный на его основе метод (21) — (23) для аадачи (17) в литературе часто называют методом еоирнэгенных градиентов, В общем случае в методе сопряядепных направлений могут быть использованы и другие способы построения векторов р», отличные от (22).
А именно, пусть направления р„рь ..., р», удовлетворяющие условиям (10), уже известны и с их помощью последовательно построены точки иь ..., и»тг по формулам (21), (23). Следующий вектор р»т, будем определять из условий <р»+ь Ард> = 0 (г = О, 1, ..., й). В случае квадратичных функций (1) формула (8) остается справедливой при любом выборе векторов рг, рь ..., р» в (21), (23), поэтому условие ортогональности вектора р»+г к векторам Аре, Арь ..., Ар» здесь приводит к равенствам <р»ть йч> = О, д; = Х'(иг) — Х'(игтг), д = О, 1, ..., й. (29) Условия (29) имеют смысл и для неквадратичных фундщий, и ими пользуются для определения р»+1 в общем случае. Обычно вектор р»ш ищут в виде [11, 41, 46, 48, Ш, 250, 330) р»т, †,Н»„гХ'(и»тг), Н»+г = Н» + дгН», (30) где матрица ЬН» определяется из условий (29).
Нетрудно видеть, что перечисленные условия (29), (30) матрицу ХдН» определяют неоднозначно и в аависимости от того, как распорядиться этим произволом, можно получить различные варианты метода сопряженных направлений. Если на каком- либо шаге Н» = О, то метод (21), (23), (29), (30) обновляют, полагая А» = =Х вЂ” единичная матрица. Приведем один из вариантов этого метода, в котором матрицы Н» определяются по правилу Н =Н вЂ” ~, ть=Х'(и„) — Х'(иь), Н =Х. ( Еь)( эта) В [19) предлагается и исследуется метод сопряженных направлений, поаволяющнй аа конечное число итераций найти точку минимума квадратичной функции (1) на множестве, аадаваемом линейными ограничениями типа равенств и неравенств.
Исследование сходимости различных вариантов метода сопряженных направлений, более тонкие оценки скорости сходимости читатель может найти в [11, 19). 329 МЕТОД НЬЮТОНА 6 9) У и р а ж н е н н я. 1. Показать, что точка яь полученная методом сопряженных направлений для квадратичной функцкн (т) прн Хе=я, есть точка мкннмума этой функции на гкперплоскостн, проходящей через точку в, н натянутой на векторы Х'(ие), Х'(и,), ..., Х'(иь,). 2. Описать метод сопряженных направлении для функции Х(и) = = )Аи — Ъ (', и ш Е", где А — матрица порядка т )х п, Ь ев Е . 5 9.
Метод Ньютона До сих пор мы рассматривали методы первого порядка— так называются методы минимизации, использующие лишь первые производные минимизируемой функции. В этих методах для определения направления убывания функции используется лишь линейная часть разложения функции в ряд Тейлора. Если минимизируемая функция дважды непрерывно дифференцируема и производные Х'(и), Х" (и) вычисляются достаточно просто, то возможно применение методов минимизации второго порядка, которые используют квадратичную часть разложения этой функции в ряд Тейлора.
Поскольку квадратичная часть разложения аппроксимирует функцию гораздо точнее, чем линейная, то естественно ожидать, что методы второго порядка сходятся быстрее, чем методы первого порядка, Ниже будут описаны два метода второго порядка: в этом параграфе будет рассмотрен метод Ньютона, имеющий квадратичную скорость сходимости на классе сильно выпуклых функций, а в следующем параграфе — метод с кубической скоростью сходимости на этом же классе. Здесь мы пользуемся следующей терминологией, принятой в литературе: говорят, что последовательность (иь) сходится к точке ив с линейной скоростью или со скоростью геометрической прогрессии (со знаменателем о), если, начиная с некоторого номера, выполняется неравенство ) иь+т — ие !~~у) ие — ие )(0(д(1); при выполнении неравенства !иез-,— ие)(~де)иа — ие), где (е)ь) — О, говорят о сверхлинейной скорости сходимости последовательности (и„) к ие, а если здесь де = С ) иь — и )'-', т.
е. ( иве.,— и ) (С ) ие — ие )', то говорят о скорости сходимости, порядка з (при з = 2 получим квадратичную скорость сходимости, прн г = 3 — кубическую). Для некоторых методов выше была установлена линейная скорость сходимости на классе сильно выпуклых функций; в тех случаях, когда )иа — и ~ =-0(1/)с), скорость сходимости ниже линейной; для метода сопряженных направлений можно показать сверхлинейную скорость сходимости (19). 1.
Опишем метод Ньютона для задачи Х(и) - ш1; иш У, (1) где У(и)ы Се(У), У вЂ” выпуклое замкнутое мнопсество из Е" (например, сХ= Е"). Пусть ие еи сХ вЂ” некоторое начальное приближелие. Если известно й-е приближение иь то приращение 330 методы минимизАции Функций мнОГих пегеменных ~гл. 5 функции 7(и) ~ С'((7) в точке и, можно представить в виде Х(и) — у(ид) = (у' (ид), и — ид',д + + — (Х" (ид)(и — ид), и — ид) + о() и — ид)д). Возьмем квадратичную часть этого приращения з д (и) = (Х' (ид), и — ид) + —, (У" (ид) (и — ид), и — ид> (2) и определим вспомогательное приближение йд из условий ид е= (7, Хд (ид) = ш1 Хд (и).
и (3) Следующее (й+1)-е приближение будем искать в виде иц., = ид+ ад(йд — и,), О ~ ад < 1. (4) В зависимости от способа выбора величины а, в (4) можно получить различные варианты метода (2) — (4), называемого методом Ньютона, Укажем несколько наиболее употребительных способов выбора а,. 1) В (4) можно принять а„=1, й=О, 1, ... (5) В этом случае, как следует из (4), идд, = йд (й = О, 1, ...), т. е. условие (3) сразу определяет следующее (й+ 1)-е приближение. Иначе говоря, ид+, ен(7, зд(ид+,) = 1Н1зд(и), й = О, 1, ... (6) В частности, когда О'=Е", в точке минимума функции Хд(и) ее производная Уд(и) обращается в нуль, т. е. з д (ид+г) = Х' (ид) + з'" (и„) (ид+д — ид) = О. (7) Это значит, что на каждой итерации метода (2) — (5) или (6) нужно решать линейную алгебраическую систему уравнений (7) относительно неизвестной разности ид.д,— и,. Если матрица атой системы 7" (и,) — невырожденная, то из (7) имеем ид+,=и„— (Х (и„)) '7 (и„), й=О, 1, (8) и,„, = ид — (г'(ид) ) 'Р(ид), й = О, 1, ..., (9) Широко известный метод Ньютона для решения системы уравнений г' (и) = (Г, (и), ..., г „(и) ) = О, и ~и Е", представляет собой итерационный процесс (4, 54) з а1 МЕТОД НЬЮТОНА где г"'(и) — матрица, 1-я строка которой равна ро(и) = (р, и...
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
