最適化数学まとめ(2.2 ニュートン法)

ニュートン法とは

ニュートン法とは端的に言えば、ある関数を2次近似することで関数を最適化する手法です（ここでは関数の極値を求めるものを扱う）。2次近似とは、ある関数のテイラー展開を2次の項までで表したものです。
今回は１変数のニュートン法について考えます。

１変数のニュートン法

前提として、1階導関数だけではなく2階導関数も計算できるものとします。
ある関数$f(x)$を$x$軸上の点$\bar{x}$周りの点$\bar{x}+\Delta{x}$でテイラー展開すると以下のようになります。（$\Delta{x}=|x-\bar{x}|$,$x$は求めたい値）

$f(\bar{x}+\Delta{x})=f(\bar{x})+f'(\bar{x})\Delta{x}+\frac{1}{2}f''(\bar{x})\Delta{x^2}+\ldots\ldots(1)$

$\ldots$以降は３次以上の項であり、$\Delta{x}$が小さい場合に急速に小さくなるため、３次以降の項は無視します。
(1)の2次までの項の極値を求めるために、$\Delta{x}$で微分して$0$と置くと以下のようになります。

$f'(\bar{x})+f''(\bar{x})\Delta{x}=0\ldots(2)$

(2)を$\Delta{x}$について解くと、$\Delta{x} = -\frac{f'(\bar{x})}{f''(\bar{x})}\ldots(3)$
となります。
(3)より、解$x$の近似値は$x=\bar{x}-\frac{f'(\bar{x})}{f''(\bar{x})}\ldots(4)$
となります。
解$x$の近似値が一定の範囲に収束するまで(4)を反復する方法をニュートン法と呼びます。
反復計算をいつ止めるかについては、以下を参照してください。
いつ反復計算をやめるべきか？
具体的なアルゴリズムは以下の通りになります。

procedure Newton($f'(x),f''(x)$)
1.$x$の初期値を与える。
2.$\bar{x}\leftarrow x$と置き、次のように$x$を更新する。
$x\leftarrow\bar{x}-\frac{f'(\bar{x})}{f''(\bar{x})}$
3.ステップ2に戻り、これを$|x-\bar{x}|<\delta$となるまで繰り返す。
4.$x$を返す。
（金谷、2005、p.86）

pythonでは、SciPyというライブラリを使うと簡単に実装できます。

Newton.py

from scipy import optimize
# f(x)=x^2-2の0地点を求める(x=√2)
f = lambda x : x**2 - 2
optimize.newton(f,0)
# 出力
1.414213562373095

参考にしたもの

「これなら分かる最適化数学」（金谷、２０１５）
SciPy
機械学習のためのニュートン法 (1 変数から多変数まで)
二分法・ニュートン法・勾配降下法をPythonで理解する
いつ反復計算をやめるべきか？～収束判定基準の設定方法～