Ф.П. Васильев - Методы оптимизации (1125241), страница 90
Текст из файла (страница 90)
Укажем несколько наиболее употребительных способов выбора сзь, 1) В (4) можно принять аз=1, й=0,1,... (5) В этом случае, как следует из (4), х,т! = х, й = О, 1,..., т. е. условие (3) сразу определяет следующее (й + 1)-е приближение. Иначе говоря, х,т! ЕХ, уь(х т!) =!и!Гь(х), й =0,1, (6) В частности, когда Х = Е", в точке минимума функции Ях) ее производная уь'(х) обращается в нуль, т.
е, Яхь „!) = уз(хь) +7'з(х )(х „, — х„) =О, (7) Это значит, что на каждой итерации метода (2)-(5) или (6) нужно решать линейную алгебраическую систему уравнений (7) относительно неизвестной разности хат ! — х„. Если матрица этой системы ул(хь) — невырожденная, то из (7) имеем хь „— — хь — (7 "(хь)) !7'(хь), й = О, 1,... (8) Широко известный метод Ньютона для решения системы уравнений Р"(х) = (Р;(х),..., Г„(х)) =О, х Е Е", представляет собой итерационный процесс )?4; 89; 550; 635] х ! — — х — (г"(хь)) !Р(х ), й =О, 1,..., (9) где уч(х) — матрица, з-я строка которой равна Г,.'(х) =(Гы,..., г''л.).
Сравнение формул (8) и (9) показывает, что метод (8) решения задачи (1) в 11(7'о(х)) ' 11 ( и ', х Е Е (16) 5 17'(хо)) < 2ссгд, (13) 302 Гк З, МЕТОДЫ МИНИМИЗАЦИИ сууихцИй МНОГИХ ПЕ ЕМЕННЫХ случае Х =.Е" представляет собой известный метод Ньютона для решения уравнения Г'(х) =О, определяющего стационарные точки функции Г(х). Отсюда происходит название метода (2) — (4) и в общем случае. 2) В качестве сг, в (4) можно принять сс„= Л", где ~ — минимальный среди г > 0 номер, для которых выполняется неравенство [603[ г(х,) — Ях, + Л'(х„— х,)) > сЛс[~,(хЯ (10) где Л, г — параметры метода, 0 < Л; г < 1. 3) Возможен выбор сг„в (4) из условий [6031 0< со, < 1, д„(сг ) = ппп д (сг), д„(сг)= Г(х„+со(хг — х )).
(11) ос~41 Заметим, что метод (2) — (4) с выбором длины шага ог по правилам (!О), (11) аналогичен соответствующим вариантам метода условного градиента, где для определения х„использовалась линейная часть приращений, а в методе Ньютона — квадратичная часть (2). Если г",(х) из (2) сильно выпукла, а Х = Е" илн Х задается линейными огранйчениями типа равенств или неравенств, то для определения х, из (3) могут быть использованы методы из $8, 9. Следует заметить, что задача (3) в общем случае может оказаться весьма сложной и сравнимой по объему требуемой для своего решения вычислительной работы с исходной задачей (1). Метод Ньютона для решения задачи (1) обычно применяют в тех случаях, когда вычисление производных Г'(х), уо(х) не представляет особых трудностей и вспомогательная задача (3) решаетсн достаточно просто.
Достоинством метода Ньютона является высокая скорость сходимости. Поэтому, хотя трудоемкость каждой итерации этого метода, вообще говоря, выше, чем в методах первого порядка, но общий объем вычислительной работы, необходимой для решения задачи (1) с требуемой точностью, при применении метода Ньютона может оказаться меньше, чем при применении других более простых методов.
2. Сначала исследуем сходимость метода Ньютона (2) — (4) с выбором шага сг„из условия (5) при условии Х = Е" или, проще говоря, метода (8), Теорема 1. Пусть функция 7(х) сильно выпукла на Е", г"(х) е е Сг(Е ) и, кроме того, 1~У (х) 7 (у)!)(»7(х — у(, х, уЕЕ", 5 =сонэ!> О. (12) Пусть начальное приближение х выбрано таким, что гдг и > 0 — постоянная из теоремы 4.3.4, а д — некоторая константа, 0 < д < 1.
Тогда последовательность (х,), определяемая условиями (8), существует, сходится к точке х„минймума,г'(х) на Е", причем саравгдлива оценка (х„— х„! < 2и5 'дг, й = О, 1,... (14) До к аз а тел ь ство. Существование и единственность точки х„установлена в теореме 4.3,1, Согласно теореме 4.3.4 (~о(х)б, б) >бс[б)~, х Е Е", 4 Е Е". (15) $10, МЕТОД НЬЮТОНА 303 Отсюда следует, что система уравнений уо(х)с = 0 имеет единственное решение б =0 и, следовательно, матрица 7"(х) невырожденная при всех хе Е". Это значит, что система (7) при каждом й = О, 1,, имеет, и притом единственное, решение, т.
е. последовательность (хс) однозначно определяется условиями (8). Кроме того, полагая в (15) б = (7"(х)) 'г, получим и)(Тсс(Х)) 'г)г< (г,(Гсс(Х)) 'г) <[г0(7""(Х)) 'г( ИЛИ )(уо(Х)) 'о[< ~о)и Прн всех г Е Е". Это значит, что Введем числовую последовательность а, = [г'(х„)[ и покажем, что а, <2ссгХ 'дг", й =0,1,...
(17) При й =0 неравенство (17) следует из условия (13). Пусть (17) справедливо при некотором й > О. Йз условия (8) и формулы (2.6.5) имеем Т'(х„„,)=Т'(х,)+ 1 7'"(х„+с(хг „,— х,))(х,,— х„)с(с= о = '1Цо(х ) — с о(х,+1(х > — хг))[сЫ(уо(хг)) 'с '(хг). о Отсюда и из (8), (12), (16) с помощью предположения индукции получим а„, ( (й,с2)~хг, — х„~бс 'а„( (Асс(2ссг))агг ( < (г с(2 г))(2„гр )г(, г")г (2 г сг ), г"' Н еравенства (17) доказаны.
Тогда из теоремы 4.3.3 с учетом равенства 7'(х,) = 0 имеем бс(х„— х„)г ( (Г'(х ) — Г'(х,), х„— х,) ( )~'(х„)((х — х„[ или (х„— х.) ( а, сс ', Отсюда и из неравенства (17) следует оценка (14). Теорема 1 доказана. П Как видно из оценки (14) и как показывает практика, метод Ньютона (8) сходится очень быстро, Однако у него есть один существенный недостаток: для его сходимости начальная точка х должна выбираться достаточно близкой к искомой точке х,. Это требование в теореме ! выражено условием (13), означающим, что 1хо — х.) < а р ' < (2сссс5)д.
Приведем пример, показывающий, что при отсутствии хорошего начального приближения метод (8) могкет расходиться. П р имер 1. Пусть — — 'гмг+О.(1+ б)Х'~ 3Х/«»бс с( ) 4б — + 21х1 — 4 б )х( > б где х е .Е', а б — сколь угодно малое фиксированное положительное число, 0 < б < 1. Нетрудно видеть, что Г(х) е С'(Е') и, кроме того, ~"(х) > 1 при всех х е Е', так что У(х) сильно выпукла на Е'. Далее, ясно, что 7; = О, х, =О. В качестве начального приближения возьмем х = б.
Из (8) получим последовательность х„ = ( — 1)" 2, й = 1, 2,..., которая расходится, хотя начальное приближение хо отличается от х, = 0 на малое число б. ! 304 Гл. 5. МЕТОДЕ! МИНИМИЭАПИИ фУНКПИЬ) МНОГИХ ПЕРЕМЕННЫХ $10. МЕТОД НЬЮТОНА 303 !/ (х) / (у)[<ь[х — у[, х,усх, е =соим (18) Тогда последовательность (х,) однозначно определяется условиями (6), при лгобом еы боре начальлоео приближеии х .
Если (19) д =- (Е/(2р))[х, — хо[ < 1 то последовательность (хй), определяемая условиями (6), сходится к тачке х„— реше нию задачи (!), причем справедлива оценка х ~ < ~ф ! ~ уг < ф~' уг"(! уг")- й О ! т=й (20) здесь и > 0 — постоянная из теоремы 4.3.4. Доказательство, В силу теоремы 4.3.1 функция /(х) ограничена снизу и достигает своей нижней грани на Х в единственной точке х„Иэ теоремы 4,3.4 следует (/л(х)5,6)>Р~Е~~, хЕХ, ЕЕЕх, (21) где Ех — подпространство, параллельное аффинной оболочке множества Х. Так как /й л(х) = = /" (х ), то иэ предыдущего неравенства и теоремы 4.3И вытекает сильная выпуклость функции /й(х) на множестве Х при всех й=о, 1,...
Снова обращаясь к теореме 431, заключаем, что условия (6) однозначно определяют точку хй + о Таким образом, существование последовательности (хй) из (6) доказано, Применив теорему 4,2.3 к функции /й(х) на Х, получим (/й(хй „~),х — жй+!) )яо, хе х й= о, 1, (22) Так как /й'(х) и /'(хй) + /л(хй)(х — хй), то неравенство (22) перепишется в.виде (/~(хй) +/л(хй)(хй+ ~ — хй), х — хй+~) > О, х Е Х, й =О, 1, (23) Может случиться, что ей+1 —— хй. Тогда на (23) имеем (/'(хй), х — хй) ) 0 при всех х е Х Согласно теореме 4.2.3 в этом случае хй = х„— задача (1) решена.
Поэтому можем считать что хй Фей ~ при всех й =О, 1,... Положим в (23) х= ей. Получим (/'(хй)+/е(хй)(хй „~ — хй), хй — хй ~) ) О. Отсюда и иэ (21) имеем и[хай! — хй[ <(/ (хй)(хйй,-хй),хй „!-хй) < (/(жй),жй — хй+,), й =О, 1,... (24) Оценим правую часть (24) сверху.
Для атагов (22) заменим й на 1с-1, Получим (/й !'(хй), х— хй) > О, х е Х. Полагая здесь х = хе+ !, имеем (/„!'(жй),хй — хй „г) <О, й=!,2, Отсюда, иэ формулы (2.6.5) и условия (18) следует Ое(х ), хй — хй „) < (/'(хй) — /й !~(хй), хй — хй+ ~) = = (/'(жй) — /'(хй ) — / (х )(хй — х, ~), хй — хй+~) = 1 = ()[/в(хй + г(хй — хй 1)) — /л(хй !))дг(хй — хй ~), хй — хй „~) < о г ч 2 [х~ — хй 
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
