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

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

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

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

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