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

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

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

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

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

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

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

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

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

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

${\displaystyle {\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 {\displaystyle t=-{\frac {f'(x_{k})}{f''(x_{k})}}.}}$

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

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

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

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

Вищі виміри

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

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

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

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

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

Збіжність

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

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

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

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

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

Доведення

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

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

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

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

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

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

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

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

Отже,

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

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

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

Примітки

1. . Lamar University. Архів оригіналу за 28 серпня 2019. Процитовано 28 серпня 2019.