Метод Ньютона в оптимізації

Порівняння градієнтного спуску (зелений) та методу Ньютона (червоний) для мінімізації функції (з невеликими розмірами кроків). Метод Ньютона використовує інформацію кривини (тобто другу похідну), щоб взяти більш прямий маршрут.

В диференціальному численні метод Ньютона — це ітераційний метод пошуку коренів диференційовної функції $F$, які є розв'язками рівняння $F(x)=0$. В оптимізації метод Ньютона застосовується до похідної $f'$ подвійно диференційовної функції $f$ для пошуку коренів похідної (розв'язки $f(x)=0$), також відомих як стаціонарні точки $f.$ Ці розв'язки можуть бути мінімумами, максимумами або сідловими точками.

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

Центральною задачею оптимізації є мінімізація функцій. Розглянемо спочатку випадок одновимірних функцій, тобто функцій однієї змінної. Пізніше ми розглянемо загальніший і корисніший багатовимірний випадок.

Маючи двічі диференційовну функцію ${\displaystyle f:\mathbb {R} \to \mathbb {R} }$, ми прагнемо вирішити оптимізаційну задачу

${\displaystyle \min _{x\in \mathbb {R} }f(x).}$

Метод Ньютона намагається вирішити цю проблему шляхом побудови послідовності ${\{x_{k}\}}$ з початкової здогадки (відправної точки) $x_{0}\in \mathbb {R}$, котра збігається до мінімізатора $x_{*}$ функції $f$, використовуючи послідовність наближень Тейлора другого порядку функції $f$ навколо точок послідовності. Розвинення Тейлора другого порядку функції $f$ в околі $x_{k}$ це

${\displaystyle f(x_{k}+t)\approx f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}.}$

Наступна точка $x_{k+1}$ визначена таким чином, щоб мінімізувати це квадратичне наближення по $t$ і встановити ${\displaystyle x_{k+1}=x_{k}+t}$. Якщо друга похідна додатна, то квадратичне наближення є опуклою функцією $t$, і її мінімум можна знайти, прирівнявши похідну до нуля. Тому

${\displaystyle \displaystyle 0={\frac {\rm {d}}{{\rm {d}}t}}\left(f(x_{k})+f'(x_{k})t+{\frac {1}{2}}f''(x_{k})t^{2}\right)=f'(x_{k})+f''(x_{k})t,}$

мінімум досягається для

${\displaystyle t=-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

Збираючи все разом, метод Ньютона виконує ітерацію

${\displaystyle x_{k+1}=x_{k}+t=x_{k}-{\frac {f'(x_{k})}{f''(x_{k})}}.}$

Геометрична інтерпретація

Геометрична інтерпретація методу Ньютона полягає в тому, що при кожній ітерації ми допасовуємо параболоїд до поверхні $f(x)$ у пробному значенні $x_{k}$, що має ті ж нахил та кривину, що і поверхня в цій точці, а потім переходимо до максимуму або мінімуму цього параболоїда (у більш високих вимірах це також може бути сідлова точка). Зверніть увагу, що якщо $f$ це квадратична функція, то точний екстремум буде знайдений за один крок.

Вищі виміри

Наведену вище ітеративну схему можна узагальнити на $d$ вимірів за допомогою заміни похідної на градієнт (різні автори використовують різні позначення для градієнта включно з $f'(x)=\nabla f(x)=g_{f}(x)\in \mathbb {R} ^{d}$) і оберненої другої похідної на обернену матрицю Гесе (різні автори використовують різні позначення для матриці Гесе включно з $f''(x)=\nabla ^{2}f(x)=H_{f}(x)\in \mathbb {R} ^{d\times d}$). Так отримуємо таку ітеративну схему

$x_{k+1}=x_{k}-[f''(x_{k})]^{-1}f'(x_{k}),\qquad k\geq 0.$

Часто метод Ньютона змінюють, щоб включити маленький розмір кроку $0<\gamma \leq 1$ замість $\gamma =1$:

$x_{k+1}=x_{k}-\gamma [f''(x_{k})]^{-1}f'(x_{k}).$

Це часто роблять, щоб гарантувати, що умови Вольфе задовольняються на кожному кроці методу.

Збіжність

Припустімо, що $f$ двічі неперервно диференційовна на відкритому проміжку $(a,b)$ і існує $x^{*}\in (a,b)$ таке, що $f'(x^{*})\neq 0.$ За умови, що метод Ньютона визначено як

$x_{k+1}=x_{k}-{\frac {f(x_{k})}{f'(x_{k})}},$

і припущення, що $x_{k}\to x^{*}$ коли $k\to \infty .$ Можна стверджувати, що при достатньо великому $k,$

$|x_{k+1}-x^{*}|\leq M|x_{k}-x^{*}|^{2}\$ при $M>{\frac {|f''(x^{*})|}{|f'(x^{*})|}}.$

Тобто, $x_{k}$ збігається до $x^{*}$ квадратично.

Доведення

Нехай $e_{k}=x_{k}-x^{*},$ тобто $x_{k}-e_{k}=x^{*}.$ Згідно з теоремою Тейлора, поклавши $x=x_{k}$ і $h=-e_{k},$ для певного $\xi _{k}$ у проміжку від $x_{k}$ до $x^{*}$ маємо

$f(x_{k}-e_{k})=f(x_{k})-e_{k}f'(x_{k})+{\frac {(e_{k})^{2}}{2}}f''(\xi _{k}).$

Завдяки тому, що $x_{k}-e_{k}=x^{*}$ і $f(x^{*})=0,$ маємо

$0=f(x_{k})-(x_{k}-x^{*}f'(x_{k})+{\frac {(e_{k})^{2}}{2}}f''(\xi _{k}).$

Через те, що похідна $f$ неперервна з $f(x^{*})\neq 0,$ можна сказати, що $f'(x_{k})\neq 0,$ якщо $x_{k}$ достатньо близько до $x^{*}.$ Отже ми можемо поділити на $f'(x_{k})$

$0={\frac {f(x_{k})}{f'(x_{k})}}-(x_{k}-x^{*})+{\frac {(e_{k})^{2}f''(\xi _{k})}{2f'(x_{k})}},$

скориставшись означенням методу Ньютона маємо

$x_{k+1}-x^{*}={\frac {(2e_{k})^{2}f''(\xi _{k})}{2f'(x_{k})}}.$

Отже,

$|x_{k+1}-x^{*}|={\frac {f''(\xi _{k})}{2f'(x_{k})}}|x_{k}-x^{*}|^{2}.$

Завдяки неперервності, $f'(x_{k})$ збігається до $f'(x^{*})$ і, з того, що $\xi _{k}$ гніздиться між $x_{k}$ і $x^{*}$ випливає, що $\xi _{k}$ збігається до $x^{*}$ і тому $f''(\xi _{k})$ збігається до $f''(x^{*}),$ отже, для достатньо великих $k,$

$|x_{k+1}-x^{*}|\leq M|x_{k}-x^{*}|^{2}\$ якщо $M>{\frac {|f''(x^{*})|}{2|f'(x^{*})|}}.$