XIV Аттетков и др. Методы оптимизации (1081420), страница 34
Текст из файла (страница 34)
5.5. Для сравнения также даны результаты вычислений, в которых параметр ул определялся в соответствии с формулой (5.10) (табл. 5.6). Траектории поиска точки минимума х' = (1, 1) для всех трех вариантов вычислений показаны на рис. 5.6: а -- вариант с формулой (5.8); б — вариант с формулой (5.9); в — вариант с формулой (5.10). Из приведенных результатов видно, что необходимое количество итераций Х при поиске точки минимума является наименьшим в случае, когда используется формула (5.10), а наихудшим оказался вариант с формулой (5.8). Для сравнения отметим, что для достижения той же точности при использовании метода наискорейшего спуска требуется Х = 96 итераций. 5.3.
Метод Ньютона Если целевая функция 1'(х) является дважды дифференцируемой в К", то эффективность процесса, поиска точки х" ее минимума можно повысить, используя информацию не только о градиенте 8гаь11(х) этой функции, но и о ее матрице Гессе Н(х). Алгоритмы такого поиска обычно относят к методу Ньютона. В простейшем варианте алгоритма на каждой Й-й итерации целевая функция аппроксимируется в окрестности точки х~ (на первой итерации в окрестности начальной точки хо) квадратичной функцией рь1х) и затем определяется гочка х~ минимума функции ул(х).
На следующей, (й+1)-й итерации строится новая квадратичная аппроксимация уже в окрестности точки х . При помощи формулы Тейлора с остаточным членом в форме Пеано представим целевую функцию в окрестности точки 230 о. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ х в виде У( ) У( ь — 1)+(,дУ( й — 1) й — 1)+ 1 +-(Н(х' ')(х — х"-'),х — х' ')+о(~х — х" '~а). Пренебрегая последним слагаемым в правой части, получаем квадратичную функцию ~ря(х) = Т(х~ 1)+ (рас11"(х~ 1), х — хв 1) + + — (Н(х~ 1)(х — х~ 1), х — хь 1). 1 Если матрица Гессе Н(х" ') целевой функции, вычисленная в точке хь ', является положительно определенной, то точка х~ минимума функции ~рв(х) единственна и может быть найдена из условия, что ее градиент равен нулевому вектору: утас1 рь(х) =дас11(хь 1) +Н(х~ 1)(х — х~ 1) = 0„. Отсюда получаем хь =ха ' — Н (хв ')дга11('(х~ '), Йе1Ч.
(5.13) Отметим, что (5.13) можно трактовать как рекурронтное соотношение итерационной процедуры метода Ньютона, предназначенного для решения системы дга111(х) = О„нелинейных уравнений [У). Этим можно объяснить и название метода, применяемого для минимизации целевой функции 1 (х). Если размерность и пространства Бв велика, то вычисление на каждой й-й итерации матрицы Н '(х" '), обратной к матрице Гессе целевой функции, может оказаться весьма трудоемкой процедурой. В таком случае точку хв целесообразнее искать путем минимизации функции 1рь(х), например методом сонрллеенных направлений или методом градиентов. Подробнее этот вопрос рассмотрен ниже. 231 5.3.
Рнетод Хьютовя Точку минимума функции уь(х) можно считать лишь вспомогательным приближением и, обозначив эту точку х", для построения релаксаиионной послгл)овательносгпи (х~) использовать рекуррентное соотношение х~ =хл ~+тгь(х — х~ 1) =х~ ~+ни)в~, й еИ, (5.14) в котором значение ня > О можно выбрать различными способами. Вектор ря = х~ — х~ задает на к-й итерации направление спуски Если матрица Н(хв 1) положительно определенная, то это нькьпоновское направление спуска. Действительно, с учетом (5.13) и (5.14) этот вектор можно представить в виде р = — Н '(х' ') уас)~(х~ '), к Е И, (5.15) так что (ботас)Дх~ ),р ) = = — (дгас))(х~ 1),Н в(х~ )цгас))(х~ )) (О. Геометрически это означает, что вектор р" образует тупой угол с градиентом целевой функции, вычисленным в точке х" 1 (рис.
5.7). .Ясно, что если в (5.14) выбрать тгь = 1, то (5.13) и (5.14) будут равносильны. Однако значение хь > О можно найти как ( .ы1) 1(хг ')((гас(у(хя ~) Рис. 5.7 232 б. МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ точку наименьшего значения функции фг(н) = 1(,в + нр ) или же при помощи исчерпывающего спуска в направлении вектора рь (согласно замечанию 4.2, эти значения могут не совпадать). Для выбора значения не можно также использовать метод дробления шага. Если целевая функция является квадратичной вида (5.3) с положительно определенной матрицей ф то исчерпывающий спуск из произвольной начальной точки х Е К" в ньютоновском направлении приводит в точку ж* минимума этой функции за одну итерацию (см.
4.5). Для неквадратичной функции ньютоновское направление в общем случае не проходит через точку ее минимума, хотя часто оказывается к этой точке ближе, чем направление антиградиенти Нели это так, то спуск в ньютоновском направлении за одну итерацию позволяет достичь более существенного убывания минимизируемой неквадратичной функции и получить более близкое приближение к искомой точке т* минимума по сравнению со спуском в направлении антиградиента.
Если график целевой функции имеет овражную структуру, то вектор ре (5.15) может составлять с осью оврага меньший угол, чем антиградиент. Эта особенность при минимизации таких функпий делает алгоритмы метода Ньютона более эффективными, чем алгоритмы метода градиентного спуска. Пример 5.6. На примере минимизации функции 1'(х~., яв) = = (а~~ — хг) + (х1 — 1) сравним алгоритмы метода Ньютона при мя = 1 в (5.14) (рис. 5.8, а) и,метода наискорейшего спуска (рис. 5.8, б). Выбраны начальная точка яо = ( — 1, — 2), в которой ~(жо) = 13, и параметр точносенга поиска ез = 10 з. В случае метода Ньютона (см.
рис. 5.8, а) получено приближенное значение точки минимума ж* = (0,999., 0,999) за Х = 5 итераций, в то время как в случае метода наискорейшего спуска (см. рис. 5.8, б) приближенное значение точки минимума ж* (0,999, 0,998) достигнуто за Х = 96 итераций. Из резуль- ацз. Ыетод Ньютона Рис.
8.8 татов вычислений видно, что метод Ньютона по сравнению с методом наискорейшего спуска дает значительное уменьшение количества итераций и быстрее обеспечивает заданную точность решения задачи. Обратим внимание на то, что в методе Ньютона Х(х') < < Х(хв) (см. рис. 5.8, а), т.е. метод Ньютона привел к последовательности, не являющейся релаксационной. Такое может происходить при тел = 1 и при больших отклонениях начальной точки от точки минимума. Сходимость метода Ньютона существенно зависит от выбора начального приближения. Можно показать*, что если целевая функция сильно выпуклая и для любых точек х, у С К" относительно матрицы Гессе ХХ(х) целевой функции выполнено неравенство ~)ЕХ(х) — ХХ(у) ~~ < А~х — у~, А ) О, а начальное приближение выбрано удачно (точка хв расположена достаточно 'Си.: Васильев Ф.П.
234 эт МЕТОДЫ ПЕРВОГО И ВТОРОГО ПОРЯДКОВ близко к точке х* минимума), то алгоритм метода Ньютона при значении зсь = 1 в (5.14) обладает квадратичной скоростью сходижости, т.е. справедлива оценка ~х" — х" ~ ( С~х ' — х*)~, Й С И,. С = сопя1. Это позволяет для такой функции использовать в качестве условия прекращения итераций выполнение первого неравенства (4.18) ~х" — х~ 1~ ( еы где е~ заданное достаточно малое положительное число.
Но в случае, когда целевая функция не является сильно выпуклой или же начальное приближение находится далеко от искомой точки х*, метод Нькетона может расходиться. Квадратичная скорость сходимости, а также возможность контроля за соблюдением достаточного условия минимума целевой функции д 1х) на каждой Й-й итерации при помощи матрицы Гессе Н(ха ') этой функции способствуют высокой эффективности рассматриваемого алгоритма. Однако при его практической реализации возникают две проблемы.
Первая из них --. это сохранение положительной определенности матрицы Гессе Н(хь ) целевой функции на каждой к-й итерации, так как иначе вектор р = — Н (х )Кгас1~(х ) может не соответствовать направлению спуска, вдоль которого эта функция убывает. Более того, матрица Н(х~ ') может быть вырожденной и не иметь обратной матрицы. Эту проблему можно решить, если направление спуска задавать вектором Р = — (ВЯ, + Н(х~ )) 8гас1д (х~ ), гДе Уа еДиничнаЯ матрица порядка и, а пе ) 0 . параметр, выбираемый так, чтобы в точке х матрица Нр = Пе1„+ Н1х~ 1), к Е И, (5.16) была положительно определена*.
В связи с этим более серьезной проблемой является необходимость вычисления и обращения на каждой итерации матрицы *См.: Базара М., Шетти К., а также: Реклейтис Г., Рейеиадран А., Рэгсдел К. 235 О.З. Лгетод Ньютона порядка и, что в случае большой размерности пространства КЯ является достаточно трудоемкой операцией. На практике обычно не вычисляют матрицу., обратнук~ к положительно определенной матрице Ню а вектор р находят из решения сиь стемы линейных алгебраических уравнений (СЛАУ) Йьр = — ягас1«(х~ ')., АЕЯ. (5. 17) Эту СЛАУ можно решить различными численными методами, например прямыми и итерационными (П1], (1У). Можно также решать СЛАУ путем минимизации квадратичной функции (Ньрг,р")«2+ (рас1«(хь '), р") методами сопряженных направлений или градиентов, поскольку выполнение (5.17) является необходимым и достаточным условием минимума такой функции.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
