Метод Ньютона

Метод Ньютона

1. Эвристические соображения, приводящие к методу Ньютона безусловной оптимизации.

Если исходить из того, что необходимым этапом нахождения решения задачи

f(x) ® min,

(1)

где f: Rm ® R, является этап нахождения стационарных точек, т. е.точек, удовлетворяющих уравнению

F(x) =(def) f ¢(x) = Q,

(2)

(обозначение F для f ¢ мы будем сохранять на протяжении всего параграфа), то можно попытаться решать уравнение (2) известным методом Ньютона решения нелинейных уравнений

xn+1 = xn - [F ¢(xn)]-1F(xn).

(3)

Для задачи (1) этот метод называется методом Ньютона безусловной оптимизации и задается формулой

xn+1 = xn - [f ¢¢(xn)]-1f ¢(xn).

(4)

Формула (3) может быть выведена, исходя из следующих соображений. Пусть xn — некоторое приближенное решение уравнения (2). Тогда если заменить функцию F в уравнении (2) ее линейным приближением

F(x) » F(x) =(def) F(xn) + F ¢(xn)(x - xn)

и взять в качестве следующего приближения решение уравнения

F(x) = Q,

(5)

то мы получим формулу (3).

Применительно к задаче (1) эти соображения выглядят так. Пусть так же, как и в п. 3.2 у нас уже есть некоторое приближенное решение xn задачи (1). Заменим в ней функцию f ее приближением второго порядка:

f(x) » j(x) =(def) f(xn) + (f ¢(xn), x - xn) + 

1

2

(f ¢¢(xn)(x - xn), x - xn)

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

j(x) ® min.

(6)

З а д а ч а  4.1*. Докажите, что если f ¢¢(xn) > 0, то решение задачи (6) задается формулой (4).

Геометрическая интерпретация формул (3) и (4) приведена на рис. 10а и 10б.

Рис. 10.

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

2. Теорема о локальной сверхлинейной сходимости метода Ньютона.

Пусть f дважды непрерывно дифференцируема, а x* — невырожденная стационарная точка. Тогда найдется окрестность Vx* точки x* такая, что приближения (4), начатые из произвольной начальной точки x0 Î Vx*, сверхлинейно сходятся к x*.

Д о к а з а т е л ь с т в о. Очевидно, F = f ¢ Î C1 и поэтому

lim x®x*

||F ¢(x) - F ¢(x*)|| = 0.

(7)

Поскольку F ¢(x*) невырожден, в силу (7) при x достаточно близких к x* невырожден и оператор F ¢(x) и более того,

lim x®x*

||[F ¢(x)]-1 - [F ¢(x*)]-1|| = 0. 

Поэтому, в частности, при x достаточно близких к x*

||[F ¢(x)]-1|| £ C.

(8)

Далее, в силу того, что F дифференцируема, а x* — стационарная точка,

F(x) = F(x*) + F ¢(x*)(x - x*) + o(x - x*) = F ¢(x*)(x - x*) + o(x - x*),

Но тогда в силу (8)

x - x* - [F ¢(x)]-1F(x) = [F ¢(x)]-1F ¢(x)(x - x*) - [F ¢(x)]-1F(x) = = [F ¢(x)]-1[F ¢(x)(x - x*) - F(x)] = o(x - x*).

или

x - [F ¢(x)]-1F(x) - x* = o(x - x*).

В частности, при x = xn

xn+1 - x* = xn - [F ¢(xn)]-1F(xn) - x* =(def) =(def) j(xn - x*) = o(xn - x*).

(9)

Возьмем теперь в качестве Vx*, например, окрестность {x Î Rm: ||y(x - x*)|| £ ||x - x*||/2}. В силу (9), очевидно, если x0 Î Vx*, то

||xn+1 - x*|| £ 

1

2

||xn - x*|| £ ... £ 

1

2n+1

||x0 - x*|| 

и, следовательно, xn ® x* при n® ¥. Более того, для произвольного q Î (0, 1) найдется e > 0 такое, что ||y(x - x*)|| £ q||x - x*|| при ||x - x*|| £ e. Но тогда, если ||xn - x*|| £e, то ||xn+1 - x*|| £ q||xn - x*||. Из последнего утверждения очевидным образом вытекает нужное соотношение ||xn - x*|| £ Cqn.

3. Обсуждение метода Ньютона.

Таким образом, метод Ньютона, с одной стороны, может сходиться с более высоким чем градиентный метод порядком, а, с другой стороны, для его сходимости требуются достаточно хорошие начальные приближения (по крайней мере так требуется в доказанной теореме). Простой геометрический пример (см. рис. 11) подтверждает эту особенность метода (мы приводим пример для уравнения (2); соответствующий пример для задачи (1) получается "интегрированием" рис. 11).

Рис. 11.

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

К этому сводятся основные преимущества (высокий порядок сходимости) и недостатки (локальный характер сходимости и больший объем вычислений) метода Ньютона.

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

4. Теорема о квадратичной сходимости метода Ньютона.

Пусть f Î C2 и, более того, f ¢¢ удовлетворяет условию Липшица с константой L. Пусть f сильно выпукла с константой l. Пусть Vx* — окрестность решения задачи (1), состоящая из точек x Î Rm таких, что

||f ¢(x)|| < 

2l2

L

.

Тогда для x0 Î Vx* метод Ньютона квадратично сходится:

||xn - x*|| £ 

2l

L

q2n, 

где q = L||f ¢(x0)||/2l2 < 1.

Д о к а з а т е л ь с т в о. По теореме 2.9 и 2.10 в условиях нашей теоремы решение x* задачи (1) существует и единственно. Воспользуемся аналогом формулы Ньютона — Лейбница для функции f ¢:

f ¢(xn + h) - f ¢(xn) = 

ò

1 0

f ¢¢(xn + sh)h ds. 

 

Вычитая из обеих частей этого равенства f ¢¢(xn)h = ò01f ¢¢(xn)h dsи учитывая, что f ¢¢ удовлетворяет условию Липшица, получаем (ср.).

 

||f ¢(xn + h) - f ¢(xn) - f ¢¢(xn)h|| £  

êê êê

ò

1 0

[f ¢¢(xn + sh) - f ¢¢(xn)]h ds

êê êê

 £

 

£ 

ò

1 0

||f ¢¢(xn + sh) - f ¢¢(xn)|| · || h|| ds £ 

ò

1 0

Ls||h||2ds = 

L

2

||h||2. 

Положим в полученной оценке h = -[f ¢¢(xn)]-1f ¢(xn):

||f ¢(xn + h) - f ¢(xn) + f ¢¢(xn)[f ¢¢(xn)]-1f ¢(xn)|| = || f ¢(xn+1)|| £

£ 

L

2

||[f ¢¢(xn)]-1f ¢(xn)||2 £ 

L

2

||[f ¢¢(xn)]-1||2·||f ¢(xn)||2. 

(10)

5. Продолжение обсуждения метода Ньютона.

Из доказанной теоремы следует, что чем меньше константа Липшица отображения x ® f ¢¢(x), т. е. чем ближе это отображение к константе, и, следовательно, чем ближе функция f к квадратичной, тем быстрее сходится метод Ньютона. В частности, если f квадратична: f(x) = (Ax, x)/2 + (b, x) + c, то метод Ньютона конечен, а именно, сходится за один шаг, причем из любой начальной точки.

6. Методы Ньютона с регулировкой шага.

Эти методы еще называют методами Ньютона — Рафсона, или демпфированными методами Ньютона. Они строятся по аналогии с градиентными методами с переменным шагом. Общий вид их таков

xn+1 = xn - an[f ¢¢(xn)]-1f ¢(xn).

Длина шага может выбираться с помощью алгоритма дробления шага (см. п. 3.9), требуя, например, выполнения неравенства

f(xn+1) = f(xn -an[f ¢¢(xn)]-1f ¢(xn)) £ £ f(xn) - ean(f ¢(xn), [f ¢¢(xn)]-1f ¢(xn)),

или, как в методе наискорейшего спуска полагая

an = argmina³0{f(xn - a[f ¢¢(xn)]-1f ¢(xn))}.

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

7. Метод Левенберга — Маркардта.

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

xn+1 = argmin j(x) =(def) argmin {f(xn) + (f ¢(xn), x - xn) +

 

+ 

1

2

(f ¢¢(xn)(x - xn), x - xn) + 

ln

2

||x - xn||2}, 

где ln — некоторый параметр (вообще говоря, свой на каждом шаге). Первые три слагаемых в определении функции j представляют собой квадратичную аппроксимацию функции f, а последнее слагаемое — "штраф", не позволяющий точке xn+1 уходить далеко от точки xn (с идеями метода штрафов мы еще столкнемся ниже). Минимум (по крайней мере, стационарная точка) функции j вычисляется в явном виде из следующего уравнения (относительно x)

Q = j¢(x) = f ¢(xn) + f ¢¢(xn)(x -xn) + ln(x- xn).

Как легко видеть,

xn+1 = argmin j(x) = xn - [f ¢¢(xn) + lnI]-1f ¢(xn).

(13)

Последняя формула и есть метод Левенберга — Маркардта.

Очевидно, что если ln = 0, то (13) представляет собой метод Ньютона, а если ln велико, то (поскольку [f ¢¢(xn) + lnI]-1 » (ln)-1I при больших ln) формула (13) близка к градиентному методу. Поэтому, подбирая значения параметра ln, можно добиться, чтобы метод (13), во-первых, сходился глобально, и во-вторых, квадратично. Можно, например, выбирать ln из следующих соображений: угол между направлениями шага и антиградиента должен быть острым, а значение функции на каждом шаге должно квалифицировано убывать. В этом случае ln должно удовлетворять следующим условиям (здесь мы обозначаем "антинаправление" шага [f ¢¢(xn) + lnI]-1f ¢(xn) через yn)

(yn, f ¢(xn))

||yn|| · || f ¢(xn)||

 ³ e1,

 

f(xn+1) £ f(xn) - e2(yn, f ¢(xn)),

где e1 Î (0, 1) и e2 Î (0, 1/2) — параметры.

8. Еще один недостаток метода Ньютона. Модифицированный метод Ньютона.

В некоторых задачах более существенным недостатком метода Ньютона является его большая вычислительная трудность: на каждом шаге требуется вычисление оператора (матрицы) f ¢¢(xn) и его (ее) обращение, что при больших размерностях стóит в вычислительном плане очень дорого. Один из способов обхода этих трудностей состоит в "замораживании" оператора f ¢¢(xn) — использовании на каждом шаге [f ¢¢(x0)]-1 взамен [f ¢¢(xn)]-1:

xn+1 = xn - [f ¢¢(x0)]-1f ¢(xn).

(14)

Геометрическая интерпретация модифицированного метода Ньютона (14) изображена на рис. 12.

Рис. 12.

Можно показать, что при естественных ограничениях модифицированный метод Ньютона сходится лишь линейно (это плата за уменьшение объема вычислений). Можно также не замораживать оператор [f ¢¢(xn)]-1 навсегда, а обновлять его через определенное число шагов, скажем k:

xn+1 = xn - [f ¢¢(x[n/k]·k)]-1f ¢(xn);

(15)

здесь [a] в верхнем индексе обозначает целую часть числа a. Можно доказать, что если функция f сильно выпукла и f ¢¢ удовлетворяет условию Липшица, то

||xn+k - x*|| £ C||xn - x*||k+1,

т. е. за k шагов порядок погрешности уменьшается в k + 1 раз, что соответствует следующей оценке погрешности на каждом шаге:

||xn+1 - x*|| £ C||xn - x*||kÖk+1.

Другими словами, метод (15) является методом kÖk+1-го порядка сходимости. Таким образом, метод (15) занимает промежуточное положение между методом Ньютона (k = 1) и модифицированным методом Ньютона (14) (k = ¥) как по скорости сходимости, так и по объему вычислений.

Другой способ уменьшения объема работы, связанного с вычислением функции f ¢¢(xn) описывается в следующем пункте.

9. Метод секущих.

Напомним, что метод секущих решения уравнения (2) заключается в приближенной замене функции F в этом уравнении не касательной y = F(xn) + F ¢(xn)(x - xn), а секущей гиперплоскостью. Например, в одномерном случае — прямой y = F(xn) + (F(xn) - F(xn-1))(x - xn) /(xn - xn-1) (см. рис. 13). Эта замена приводит (в скалярном случае!) к следующему методу решения задачи (1):

xn+1 = xn - 

xn - xn-1

f ¢(xn) - f ¢(xn-1)

f ¢(xn), 

который и называется методом секущих. Известно, что для достаточно гладких выпуклых функций порядок сходимости этого метода равен t, где t = (Ö5 + 1)/2 » 1.618 — известная константа (называемая золотым сечением).

Рис. 13.

В многомерном случае поступают следующим образом. Пусть xn, xn-1, ..., xn-m — уже вычисленные m + 1 итерации. Для каждой компоненты fj¢ функции f ¢ (j = 1, ..., m) построим в Rm+1 гиперплоскость Sj, проходящую через m + 1 точку (xi, fj¢(xi)) (i = n - m, ..., n) графика этой компоненты. Пусть P — "горизонтальная" проходящая через нуль гиперплоскость в Rm+1: P = {(x, y) Î Rm×R; y = 0}. В качестве xn+1 возьмем точку пересечения гиперплоскостей P и Sj:

xn+1 Î P Ç

æ è

m Ç j = 1

Sj

ö ø

(в общем положении эта точка единственна).

Несложные рассуждения показывают, что xn+1 можно вычислять так. Пусть a0, ..., an — решение системы

m å i = 0

aif ¢(xn-i) = 0,   

m å i = 0

ai = 1. 

(16)

Тогда

xn+1 = 

m å i = 0

aixn-i. 

Затем описанные действия повторяются для точек xn+1, xn, ..., xn-m+1.

Отметим, что поскольку на каждом шаге в системе (16) меняется лишь один столбец, то ее решение на каждом шаге можно обновлять с помощью специальной процедуры, не требующей большого объема вычислений.

Отметим, что метод секущих, в отличие от ранее рассматривавшихся методов, не является одношаговым в том смысле, что для вычисления следующей итерации ему не достаточно информации, полученной на предыдущем шаге — нужна информация, полученная на m + 1 предыдущих шагах. Такие методы называются многошаговыми. В следующем параграфе мы рассмотрим ряд таких методов. Методы же Ньютона и градиентный являются одношаговыми: для вычисления xn+1 требуется знать поведение функции и ее производных только в точке xn.