Метод Ньютона. 
Численные методы. 
Основы научных вычислений

Методы безусловной оптимизации второго порядка используют вторые частные производные минимизируемой функции/(х). Суть этих методов состоит в следующем. Необходимым условием экстремума функции многих переменных /(х) в точке х* является равенство нулю ее градиента в этой точке: grad (/(x*)) = 0. Разложение grad (/(x)) в окрестности точки х® в ряд Тейлора с точностью до членов первого порядка позволяет переписать предыдущее уравнение в виде.

где Н (х) — матрица Гессе (10.5) минимизируемой функции. Следовательно, итерационный процесс для построения последовательных приближений к решению задачи минимизации функции /(х) описывается выражением.

Полученный метод минимизации является методом Ньютона для системы (10.1) (глава 5).

В данном методе величина шага вдоль направления р^(<,) полагается равной единице. Последовательность точек {х⁽^}, получаемая в результате применения итерационного процесса, при определенных предположениях сходится к некоторой стационарной точке х* функции /(х). Если матрица Гессе Н (х) положительно определена, точка х* будет точкой строгого локального минимума функции /(х). Последовательность {х®} сходится к точке х* только в том случае, когда матрица Гессе целевой функции положительно определена па каждой итерации. Если функция/(х) является квадратичной, то, независимо от начального приближения х⁽⁰*, с помощью метода Ньютона ее минимум находится за один шаг. Это объясняется тем, что направление спуска р^(/г* = -H (x^)^-1(x⁽^)grad (/(x^)) в любых точках х⁽⁰* всегда совпадает с направлением в точку минимума х*. Если же функция /(х) не квадратичная, но выпуклая, метод Ньютона гарантирует ее монотонное убывание от итерации к итерации.

Существенным недостатком метода Ныотоиа является зависимость сходимости для невыпуклых функций от начального приближения х⁽⁰ Если х⁽⁰* находится достаточно далеко от точки минимума, то метод может расходиться, т. е. при проведении итерации каждая следующая точка будет более удаленной от точки минимума, чем предыдущая. Сходимость метода, независимо от начального приближения, обеспечивается выбором не только направления спуска р (*> = -H (x^(<,)) —¹(x^w)gracK/(x^(<,))), но и величиной шага а вдоль этого направления. Соответствующий алгоритм называют методом Ныотоиа с регулировкой шага. Итерационный процесс в таком случае определяется выражением.

Величина шага а^ выбирается из условия минимума функции /(х) по а в направлении движения, т. е. в результате решения задачи одномерной минимизации:

Такой подход требует гораздо большего объема вычислений по сравнению с методом Ньютона (10.7), так как на каждом шаге требуется решать задачу одномерной минимизации и обращать матрицу Н (х⁽^). Вследствие накопления ошибок в процессе счета матрица Гессе на некоторой итерации может оказаться отрицательно определенной или ее нельзя будет обратить. В таких случаях в подпрограммах оптимизации полагается Н (х⁽^)^-1 = I, где I — единичная матрица. Очевидно, что итерация при этом осуществляется, но методу наискорейшего спуска.

Количество вычислений на итерации методом Ньютона, как правило, значительно больше, чем в градиентных методах. Это объясняется необходимостью решения на каждом шаге системы уравнений с матрицей вторых производных целевой функции. Однако на получение решения с достаточно высокой степенью точности с помощью метода Ньютона обычно требуется намного меньше итераций, чем при использовании градиентных методов. Поэтому метод Ньютона более эффективен. Он обладает квадратичной скоростью сходимости в зависимости от требований, которым удовлетворяет минимизируемая функция/(х). Тем не менее в некоторых задачах трудоемкость итерации методом Ньютона может оказаться очень большой за счет необходимости вычисления матрицы вторых производных минимизируемой функции, что потребует затрат значительного количества машинного времени. В ряде случаев целесообразно комбинированное использование градиентных методов и метода Ныотоиа. В начале процесса минимизации, когда точка х⁽⁰* находится далеко от точки экстремума х*, можно применять какой-либо вариант градиентных методов. Далее, при уменьшении скорости сходимости градиентного метода можно перейти к методу Ньютона.

Пример 10.3 (метод Ньютона) Рассмотрим функцию Розенброка (10.3). Градиент этой функции определен в (10.6), а матрица Гессе имеет вид.

Зададим х^<()) = (0, 0) и е = 10 ⁵. Процесс поиска минимального значения показан на рис. 10.3, и он сходится всего за 2 итерации.

Рис. 103. Процесс спуска к минимальному значению в методе 11ьютона