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

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

Маючи двічі диференційовну функцію ${\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^{*}}$ квадратично.