4.3. ニュートン法

2020/1/8公開

アルゴリズム

1. 初期値$x _ {(0)} \in \mathbb{R} ^ n$を定める（定め方は任意である）

2. 収束するまで次の更新式を用いて更新を繰り返す

$$\begin{aligned} x _ {(k+1)} &= x _ {(k)} + \Delta x _ {(k)} \\ &= x _ {(k)} - H _ {x _ {(k)}} ^ {-1} \operatorname{grad} f ( x _ {(k)} ) \end{aligned}$$

原理

ニュートン法（Newton's method）は現在の点で目的関数を2次近似して、近似した関数の極値を与える点へと更新することを繰り返して最適解へと向かっていく手法である。

ニュートン法でも最急降下法のときと同様に

$$\operatorname{grad} f (x) = 0 \tag{4.3.1}$$

を満たすような点$x$を見つける。ただしニュートン法では以下で与えられる関数の2次近似を用いる。

$$f _ {\rm II} (x) = f(\overline{x}) + \left< \operatorname{grad} f(\overline{x}), \Delta x \right> + \left< \operatorname{Hess} f(\overline{x}) \Delta x, \Delta x \right> \tag{4.3.2}$$

2次近似した関数の極値を与える点$x$を見つけるには

$$\nabla f _ {\rm II} (x) = 0 \tag{4.3.3}$$

となる場所を見つければよい。(4.3.2) 式の右辺では$\overline{x}$は定数であり$\Delta x$が$x$の関数であることに注意する。具体的には (1.2.2) 式の書き換えを用いているので $\Delta x = x - x _ {(k)}$である。このことを考慮しつつ (4.3.2) 式の両辺を$x$で微分すると

$$\nabla f _ {\rm II} (x) = \operatorname{grad} f (\overline{x}) + \operatorname{Hess} f (\overline{x}) \Delta x \tag{4.3.4}$$

となるから、$\nabla f _ {\rm II}(x) = 0$となるとき

$$- H _ {x ^ k} \Delta x = \operatorname{grad} f (x _ {(k)}) \tag{4.3.5}$$

である。ただし Hessian operator は Hesse 行列による表記に直した。Hesse 行列が正則ならば連立方程式 (4.3.5) を満たす解は、両辺に左から$- H _{x _ {(k)}} ^ {-1}$をかけることで

$$\Delta x = - H _ {x _ {(k)}} ^ {-1} \operatorname{grad} f (x _ {(k)}) \tag{4.3.6}$$

と唯一通りに定まる。なお、(4.3.6) 式による更新が最適解へ向かうためには Hesse 行列が常に正則であることに加えて正定値でなければならない。

収束性

ニュートン法は2次収束のアルゴリズムである。

特徴

ニュートン法は2次収束のアルゴリズムで、極値の近傍では比較的少ない回数のイテレーションで極値へ収束する。一方で実験的には極値から離れた点では最急降下法などの手法に比べて収束性が悪いことが知られており、

1. 最適解の近くまでは最急降下法や共役勾配法によって近づき、最適解の近くでニュートン法に切り替える

2. 修正ニュートン法を用いる

といった方法で最適解から離れた領域での挙動を改善する必要がある。

ニュートン法ではイテレーションのたびに Hesse 行列の逆行列を計算する必要がある。$n \times n$の正方行列の逆行列を計算するには$O(n ^ 3)$の時間計算量が必要であり、本書で紹介する手法のうちではもっとも重たい部類に入る。大規模問題に対してはまったく適用できないと考えてよい。

連続最適化の歴史は「いかにして Hesse 行列の逆行列の計算を回避するか」の歴史といっても過言ではないので、現代で使われることは少ない。