XIV Аттетков и др. Методы оптимизации (1081420), страница 35
Текст из файла (страница 35)
Опишем алгоритм варианта метода Ньютона поиска точки х* минимума дважды дифференцируемой целевой функции «(х), х б К", в котором направление спуска определяется путем решения СЛАУ (5.17). Предварительно выбираем начальную точку хо е Б'." и значение ез > О в условии ~дгас1«(х ')~ < ез прекращения итераций. Полагаем к = 1 и переходим к основной части алгоритма. 1. В точке х~ ' находим ягаг1«(х~ ') и матрицу Гессе Н(х~ ') целевой функции.
Если ~бгас1«(хг ")~ < ез., то итерации прекращаем, принимая х* х" 1 и «(х*) «(х~ '). Если при этом матрица Н(х~ 1) положительно определенная, то х' — точка минимума целевой функции, а иначе необходимо провести дополнительное исследование поведения функции в окрестности точки х*. При ~ 3тас1«(х~ 1) ~ > ез и положительно определенной матрице Н(хв ~) полагаем Нь = Н(х~ ~) и переходим к и.3. В противном случае переходим к п.2.
2. Подбираем значение цг > О, при котором матрица Нь (5.16) будет положительно определенной, и переходим к и. 3. 3. Из решения СЛАУ (5.17) находим вектор р" и затем точку х~ = х~ 1+ р~. Полагаем ь: = А+ 1 и возвращаемся к и. 1. 236 б. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ 5.4. Модификации метода Ньютона Напомним, что в,методе Ньклиона для построения релансационной последовательности (хн1 при поиске минимума дважды непрерывно дифференцируемой и ограниченной снизу в 1Сн целевой функции 1(х) используют рекуррентное соотношение вида (5.14) х =х +хьр . где р -- вектор., задающий на Й-й итерации ньютоновское направление спуска из точки х (на первой итерации из начальной тонни хв). Выше (см.
5.3) перечислены некоторые способы выбора значения хь. Обычно собственно метод Ньютона связывают с таким вариантом выбора этого значения,. когда на Й-й итерации принимают хьр = — Н (х" ) 8гас11(х ' ), где Н(х ) матрица Гессе целевой функции с элементами, вычисленными в точке хь '. Если принять во внимание (5.15), то следует считать, что в методе Ньютона хь = 1. Одна из модификаций метода Ньютона поиска точки х* минимума функции 1(х) связана с применением для выбора значения хь метода дробления шага., при котором на каждой итерации выполняется неравенство* т'(х~ ) — 7'(х~) > — сохе(8гас1('(х~ ), рь), в Е И, (5.18) где ш Е (О, 1/2). Если на 1с-й итерации это неравенство не выполнено при начальном значонии хя = хв = 1,.
то процедуру дробления шага проводят в соответствии с формулой хь = ь', где о Е (О, 1) — выбранный постоянный но;нусуициент дробления исага, а 1 номер этапа дробления, на котором будет выполнено (5.18). Алгоритм с дроблением шага и нахождением направления спуска путем решения системы линейных алгебраических уравнений (СЛАУ) (5.17) можно представить следующим образом. Смл Полин Э., а также: Пшеннннма Б.Б., Динилнн Ю.М.
о54. Модификации метода Ньютона Па предварительном этапе выбираем начальную точку хо б К", параметр ез ) О точности поиска в условии )8гае1«(х~ ~)! < ез прекращения итераций, коэффициент ц дробления шага и значение щ е (О, 1«2) в (5.18). Вычисляем значение «(хо) целевой функции «(х) в точке х, полагаем Й = 1, жь = 1 и переходим к основной части алгоритма. 1. В точке х", найденной на (Й вЂ” 1)-й итерации (на первой итерации в точке х"), вычисляем градиент ягае1«(х" ') и матрицу Гессе Н(ха 1) целевой функции. Если ~8гае1«(ха ')~ < < ез, то итерации прекращаем, принимая х = ха ' и «(х*) = = «1х~ ').
В противном случае переходим к п. 2. 2. Из решения С,ЛАУ (5.17) находим вектор р", точку х" = = хь 1+ теяра и значение «(х") в этой точке. Если при этом выполнено неравенство (5.18), то полагаем теь = 1, й: = й+ 1 и возвращаемся к п. 1. В противном случае переходим к п. 3. 3. Полагаем ьеа.= мха и возвращаемся к п.2. Другой способ выбора значения на в (5.14) основан на применении на каждой й-й итерации исчерпывающего спуски в направлении, определяемом вектором р, т.е.
связан с минимий зацией функции фа(к) = «(х" ~ + тер"). Общая трудоемкость этого способа может оказаться значительной вследствие необходимости на каждой итерации для поиска минимума этой функции использовать один из методов одномерной минимизации (см. 2). Алгоритм, в котором реализуется такой способ выбора значения ню отличается от описанного выше тем, что во втором пункте алгоритма после нахождения вектора р минимизируется функция ф(н), а затем полученное значение ня используется для вычисления точки ха =х~ +ьеара. После этого осуществляется переход к первому пункту алгоритма. Отметим, что на предварительном этапе нет необходимости задавать значения ц, щ и оея = 1. Пример 5.7.
Используем рассмотренный алгоритм для поиска минимума той же функции «(хч, хз) = (х1~ — хз) + (х1 — 1), 238 5. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЛДЕОВ что и в примере 5.6, выбрав начальную точку хс = ( — 1, — 2) и задавшись значением ез = 10 з параметра точности поиска.
Процесс поиска точки минимума х' = (1, 1) этой функции для двух разли шых алгоритмов показан рис. 5.9: а — алгоритм с дроблением шага (и = 0,5, ш = 0,25): 6 алгоритм с выбором параметра чь, входящего в формулу (5.14), с помощью исчерпывающсто спуска. Результаты вычислений приведены в табл. 5.7, в которой колонки а и 6 соответствуют двум указанным алгоритмам, а в колонке в содержатся результаты расчетов по методу Ньютона с выбором хь = 1 в формуле (5.14). Из результатов расчетов видно., что спуск в ньютоновском направлении уже на первой итерации приводит к значительно большему убыванию целевой функции и дает более точное приближение к искомой точке минимума. При одном и том же зна ~ении ез = 10 з в вариантах 6 и в требуется всего пять итераций, в то время как в варианте а -- семь итераций. Рис. 5.9 ат4. ЛХоаификации ьлетоаа Ньютона Таблииа 5.7 Отметим, что рассмотренные модификации метода Ньютона менее чувствительны к выбору начальной точки х по сравнению с „классическим' вариантом этого метода, соответствующим значению леь = 1 в !5.14).
Можно показать*, что если целевая у!унниил является сильно выпуклой и ее матрица Гессе Н(х) для любых точек х, у Е Кн удовлетворяет неравенству то при произвольном выборе начальной точки обе рассмотрен- ные выше модификации метода Ньютона обладают квадратич- ной скоростью сходимости. При этом справедлива оценка )х — х'! < — (х — х*(, Й Е Ы., ! (5.20) где Л! оценка снизу наименьшего из собственных значений матрицы Гессе Н(х) целевой функции в окрестности точки х', содержащей то !ку х~, если в этой окрестности матрица Гессе является положительно определенной, т.е.
Л!!х!э < (Н(х)х., х) для всех точек х из этой окрестности. Ясно, что попытка реализовать рассмотренные алгоритмы наталкивается на те же проблемы, что и при выборе теь = 1 в Смл Пшеничный Б.Н., Данилин Ю.м. ( — 0,.7143, 0,4286) (0,0226., — 0,5832) (0,4735, 0,.0209) (0,8478, 0,5786) (0,9667, 0,9203) !0,9991, 0,9971) (1,0000, 1,0000) ( — 0,6888, 0,6455) (0,1152, — 0,5155) (0,9260, 0,6683) (0,9821, .0,9697) (1,0000, 1,0000) ( — 0,7143, .0,4286) (0,7594, — 1,5951) (0,8044, 0,6451) (0,9992, 0,9605) (1.,0000, 1,0000) 240 й. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ р = — Н '(х~)дгае1~(х ), .ЙЕИ. (5.21) Если в начальной точке хв матрица Гессе Н(хв) целевой функции не является положительно определенной, то в (5.21) вместо Н(хв) можно использовать матРицУ Н, = П,1н+ Н(хв), вычисленную в соответствии с (5.16) при й = 1.
Оказывается, что использование (5.21) приводит к линейной скоросвш локальной сходи ноави, причем справедлива оценка )х — х*) < д)х ' — х*(, Й Е И, д = сопв1. (5.22) Выбор начальной точки хв влияет на знаменатель д геометрической прогрессии: чем ближе хв к искомой точке х*, тем меньше значение в. Другой способ разрешения указанной выше проблемы состоит в периодическом „обновлении" матрицы Гессе в (5.21).
В этом случае на первых К итерациях в (5.21) используют матрицу Н(х~) (или Нм если матрица Н(хв) не является положительно определенной), а на (К+1)-й итерации ее заменяют матрицей Н(х~) (или Нк ьм если матрица Н(х~) не окажется положительно определенной матрицсй) и т.д. Выбор значения К зависит от целевой функции. Если целевая функция сильно выпукла и удовлетворяет условию (5.19), то алгоритм с ьобновлениемн матрицы Гессе при произвольном выборе на шльной точки будет обладать сверхливвйной скоростью сходииости'. Сыл Пшеничный Б.Н., Динилин Ю.М. (5.14) (см. 5.3).
Главная из них состоит в том, что на каждой к-й итерации необходимо вычислять и обращать матрицу Гессе Н(х" ) целевой функции или же искать направление спуска путем решения С,ЛАУ (5.17), где матрица Йя опреде~иется равенством (5.16). Один из способов разрешения этой проблемы заключается в использовании для выбора направления спуска вместо (5.15) соотношения 241 о.о.
кваоиныотоновеквв методы При этом для любого из рассмотренных выше способов выбора в (бз.14) значения нь справедлива оценка )х" — х*~ < С~х~л Н вЂ” х'~ е"., Й Е И, С = сопв$. При К = 1, т.е. при „обновлении" матрицы Гессе на каждой итерации, эта оценка равносильна (5.20), а при довольно редком „обновлении", т.е. при больших значения Л, она приближается к (5.22).
5.5. Квазиньютоновские методы Среди алгоритмов многомерной минимизации следует выделить группу алгоритмов, которые объединяют достоинства метода наискорейшего спуска и метода Ньютона. Такие алгоритмы принято относить к так называемым квазиньюпьоновским метподам. Особенность этих алгоритмов состоит в том, что при их применении нет необходимости вычислять и обращать матрицу Гессе целевой функции ~(х) и в то же время удается сохранить высокую скорость сходимости алгоритмов, присущую методу Ньютона и его модификациям (см. 5.3 и 5.4).
Элементы релакеаиионной последоватаельношпи (хк) в алгоритмах квазиньютоновских методов минимизации непрерывно дифференцируемой в и" целевой функции 1(х) строят в соответствии с рекуррентным соотношением х = х + ньр, но направление спуска на каждой к-й итерации задают в виде Р~ = — Аьдгас1 ~(хь ') = Авизь, й Е И (ое.23) Здесь шк = — рас11'(х~ ) -- антиградпентп целевой функции в точке х ', а Аь положительно определенная матрица поряд/с — 1 ка и, обновляемая на к-й итерации. Отметим, что направление, задаваемое на каждой к-й итерации вектором р" (5.23), является направлением спуска, так как с учетом (ое.23) (бгЫ ~(х~ '), р ) = — (ш~, Аьи~~) ( О.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
