Метод Ньютона минимизации функции многих переменных

До сих пор мы рассматривали методы безусловной минимизации первого порядка, для реализации которых использовались лишь первые производные минимизируемой функции. В этих методах для определения направления убывания функции использовалась лишь линейная часть разложения функции в ряд Тэйлора. Если же минимизируемая функция дважды непрерывно дифференцируема, то возможно применение методов минимизации второго порядка, которые используют квадратичную часть разложения этой функции в ряд Тэйлора. Поскольку квадратичная аппроксимация гораздо точнее линейной, естественно ожидать, что методы второго порядка сходятся быстрее, чем методы первого порядка.

Опишем метод Ньютона для задачи

,

где - дважды непрерывно дифференцируемая функция. Пусть известно -е приближение . Разложение функции по формуле Тейлора в окрестности точки можно представить в виде

Отсюда видно, что поведение функции с точностью до величин порядка описывается квадратичной функцией

(7.1)

Очередное -е приближение к точке минимума функции найдем минимизируя ее квадратичную аппроксимацию , т.е. точку найдем как точку минимума функции из условия

(7.2)

Пусть матрица Гессе положительно определена при всех , следовательно, невырождена ). Тогда существует обратная матрица . Отметим, что квадратичная функция с положительно определенной матрицей сильно выпукла и уравнение (7.2) определяет единственную точку глобального минимума функции . Умножим слева обе части равенства (7.2) на матрицу и найдем точку минимума квадратичной функции (7.1), аппроксимирующей в окрестности точки :

(7.3)

Итерационный процесс (7.3), начатый из произвольной точки , называется методом Ньютона минимизации функции многих переменных и является обобщением метода Ньютона в одномерном случае.

Очевидно, для квадратичной функции с положительно определенной матрицей применение метода Ньютона обеспечивает получение точки глобального минимума ровно за один шаг из любой точки .

Для выпуклой функции, отличной от квадратичной, применение этого метода обеспечивает, как правило, быструю сходимость. Дело в том, что на каждом шаге итерационного процесса (7.3) используется информация о поведении функции в окрестности точки , содержащаяся не только в значениях первых, но и вторых ее частных производных. Поэтому при прочих равных условиях следует ожидать более быструю сходимость метода Ньютона по сравнению с градиентными методами.

При выборе достаточно хорошего начального приближения минимизирующая последовательность для сильно выпуклой дважды дифференцируемой функции сходится к точке минимума с квадратичной скоростью . Если же точка выбрана недостаточно близкой к точке , то последовательность (7.3) может расходиться.

Отметим, что даже сходящаяся последовательность метода Ньютона не всегда обеспечивает монотонное убывание , т.е. неравенство для некоторых может нарушаться. Этот недостаток устранен в обобщенном методе Ньютона:

,

где величина находится на каждом шаге из условия исчерпывающего спуска по направлению .

Недостатком метода Ньютона является необходимость вычисления и обращения матрицы Гессе на каждой итерации.

Пример 7.1. Методом Ньютона решить задачу

,

Градиент , матрица Гессе

Найдем обратную матрицу . С помощью формулы (7.3) получаем Так как , то задача решена: . Целевая функция квадратична, поэтому решение задачи получено за одну итерацию.

Описанный метод Ньютона может применяться лишь для минимизации функций, у которых матрица вторых частных производных обратима. При этом, как оказывается, обратная матрица должна быть ограничена. Этими свойствами обладают сильно выпуклые дважды непрерывно дифференцируемые функции. Они, как известно, ограничены снизу и у них существует единственная точка минимума . Для таких функций имеет место следующая теорема.

Теорема 7.1. Если - дважды непрерывно дифференцируемая функция, удовлетворяющая условиям

(7.4)

при любых и в методе , выбирается из условия

, (7.5)

то независимо от выбора начальной точки последовательность сходиться к точке минимума .

Д о к а з а т е л ь с т в о. Если

,

то по теореме о среднем с учетом условия (7.4) получаем

Следовательно,

Воспользуемся выражением . Умножая это равенство слева на матрицу , получим , следовательно, . Тогда, умножая скалярно обе части последнего равенства на получим .

Далее в силу (7.4) имеем

и, следовательно, .

Нетрудно видеть, что неравенство (7.5) будет обязательно выполняться, если , т.е. если . Тем самым показана обоснованность выбора из условия (7.5). Так как при , то из неравенства

(7.6)

следует, что при любом . Отсюда с учетом ограниченности снизу вытекает, что при . Теперь из (7.6) нетрудно установить, что при , а в силу того что

это означает, что при . Из условия сильной выпуклости следует сходимость последовательности к решению .

Контрольные вопросы

1. К методам какого порядка относится метод Ньютона минимизации функции многих переменных?

2. Дайте определение матрицы Гессе.

3. Что лежит в основе метода Ньютона минимизации функции многих переменных?

4. Опишите метод Ньютона минимизации функции многих переменных?

5. Какой итерационный процесс лежит в основе метода Ньютона минимизации функции многих переменных?

6. Что можно сказать о сходимости минимизирующей последовательности , построенной с помощью метода Ньютона для сильно выпуклой дважды дифференцируемой функции ?

7. В каких случаях последовательность , построенная с помощью метода Ньютона, может расходиться?

8. Опишите обобщенный метод Ньютона минимизации функции многих переменных?

9. Перечислите достоинства и недостатки метода Ньютона минимизации функции многих переменных

Дата добавления: 2014-01-06