next up previous
Next: 最適化アルゴリズムの一般形 Up: 制約なし最適化問題の解法 Previous: 最急降下法

Newton法

最急降下法が持つ収束の遅さという欠点を克服する方法のひとつにNewton法がある。

再び式(1)の最小点を求める問題を考える。 式(1)を $ \vec{x}_{k}$のまわりでTaylor展開して2次の項まで残すと,

\begin{displaymath}\begin{split}f(\vec{x})\simeq f(\vec{x}_{k})+\nabla f(\vec{x}...
..._{k})^T\nabla^2 f(\vec{x}_{k})(\vec{x}-\vec{x}_{k}) \end{split}\end{displaymath} (10)

が得られる。 ここに,

$\displaystyle \nabla^2 f= \begin{bmatrix}\displaystyle \frac{\partial^2 f}{\par...
...ots& \displaystyle \frac{\partial^2 f}{\partial x_n \partial x_n} \end{bmatrix}$ (11)

である。 $ \nabla^2 f$$ f$のHesse行列と呼ばれる。 $ f$が2階連続微分可能であれば $ \nabla^2 f$は対称行列になる。

さて, 式(10)の近似の精度が十分に良ければ, 式(10)の右辺が最小になる$ \vec{x}$を求めることで, 最小点の良い近似が得られると期待される。 ところで, $ \vec{x}^{\ast}$が関数$ f$の 極小点であれば$ f$のHesse行列は正定値となることが証明できる。 上記は「スカラー関数がある点で極小値を取る(下に凸になる)ときには その関数の2回微分は正になる」という事実の$ n$次元への拡張になっている。

記法の簡単のために $ H=\nabla^2 f(\vec{x}_{k})$, $ \vec{p}=(\nabla f(\vec{x}_{k}))^T$, $ \vec{\xi}=\vec{x}-\vec{x}_{k}$ とおいて式(12)の右辺を書き直すと

$\displaystyle f(\vec{x}_{k})+\vec{p}^T\vec{\xi}+ \frac{1}{2}\vec{\xi}^T H \vec{\xi}$ (12)

となる。式(12)を

\begin{displaymath}\begin{split}f(\vec{x}_{k})-\frac{1}{2}\vec{p}^T H^{-1}\vec{p...
...c{\xi}+H^{-1}\vec{p})^T H (\vec{\xi}+H^{-1}\vec{p}) \end{split}\end{displaymath} (13)

のように書き直し, $ H$が正定値であることに注意すると, 式(13)は

$\displaystyle \vec{\xi}=-H^{-1}\vec{p}$ (14)

のときに最小値を取ることがわかる。 式(14)をもとの記号を使って書き直して

$\displaystyle \vec{d}_{k}=-(\nabla^2 f(\vec{x}_{k}))^{-1} (\nabla f(\vec{x}_{k}))^T$ (15)

と定義し, $ \vec{\xi}+\vec{x}_{k}$を改めて $ \vec{x}_{k+1}$とおくと,

$\displaystyle \vec{x}_{k+1}=\vec{x}_{k} +\vec{d}_{k}$ (16)

という式が得られる。

最適化したい関数が2次である場合には式(16) が最も良い $ \vec{x}_{k+1}$を与えるのであるが, 関数が2次でない場合には $ \vec{x}_{k+1}$をベクトル $ \vec{d}_{k}$の方向に1以外の大きさで動かした方が 良い結果を与えることもある。 そのような場合に対処するためには, ステップ幅 $ \alpha_{k}$を適当に定めて,

$\displaystyle \vec{x}_{k+1}=\vec{x}_{k}+ \alpha_{k}\vec{d}_{k}$ (17)

とする。

以上により,

N1)
適当に初期値 $ \vec{x}_{0}$を定め, $ k=0$とする
N2)
$ \nabla f(\vec{x}_{k})=\vec{0}^T$なら終了
N3)
線形方程式

$\displaystyle \nabla^2 f(\vec{x}_{k}) \vec{d}_{k}= -(\nabla f(\vec{x}_{k}))^T$ (18)

を解いて探索ベクトル $ \vec{d}_{k}$を求める
N4)
ステップ幅 $ \alpha_{k}$を適当に定めて

$\displaystyle \vec{x}_{k+1}=\vec{x}_{k}+ \alpha_{k}\vec{d}_{k}$ (19)

により解を更新する
N5)
$ k=k+1$とする
というNewton法のアルゴリズムが得られる。

Newton法は一般に最急降下法と比べて極めて高速であり, 特に関数$ f$が2次のときには1回の反復で最適解が得られるという 利点がある一方で, 初期値が十分最適値に近くないと収束性が保証されない, $ \nabla^2 f$が正定値でないと利用できない, $ \nabla^2 f$が正確に求められていないと不安定になる, $ \nabla^2 f$の計算に手間がかかる, という欠点がある。 また, 最急降下法と異なり, Newton法では, ステップ幅 $ \alpha_{k}$を 1に固定しても良い収束特性が得られることも多い。 なお, 関数に複数の極小点があるときには求められるのは 極小点のどれかであって最小点とは限らないことは 最急降下法と同じである。

Newton法の変種に, $ \nabla^2 f$を直接計算するのではなく, $ \vec{x}_{k}$の更新と並行して逐次的に近似してゆくアルゴリズムもある。 このような一連のアルゴリズムを準Newton法と呼ぶ。


next up previous
Next: 最適化アルゴリズムの一般形 Up: 制約なし最適化問題の解法 Previous: 最急降下法
Shigeru HANBA
平成15年11月16日