Terasaki's blog

勉強したことをまとめたブログ

Newton法

今回は最適化手法の1つであるNewton法の原理と、Newton法の収束速度について説明したいと思います。

1変数関数 $f(x)$ の最小化問題を考えます。まず、 $\bar{x}+\Delta x$ まわりで関数 $f(x)$ を次のようにTaylor展開します。
$$ f(\bar{x}+\Delta x) = f(\bar{x}) + f'( \bar{x} ) \Delta x + \frac{1}{2}f''(\bar{x}) \Delta x^2 + \cdots $$

ここで、 $\Delta x$ に関する3次以上の項を十分小さいとみなして無視すると、
$$ f(\bar{x}+\Delta x) \approx f(\bar{x}) + f'(\bar{x})\Delta x + \frac{1}{2}f''(\bar{x})\Delta x^2 $$

この式は $\Delta x$ に関する2次関数になっています。そこで、極値を求めるために上式を $\Delta x$ に関して微分し、 $0$ とおきます。
$$ \begin{aligned} f'(\bar{x}) + f''(\bar{x})\Delta x & = 0 \\ \\ \Delta x & = -\frac{f'(\bar{x})}{f''(\bar{x})} \end{aligned} $$

したがって、初期値として $x_0$ を与え、次式を使って $ x_1 , x_2 , \cdots $ を逐次求めることで、最適解を近似的に求めることが出来ます。

$$ x_{i+1} = x_{i}-\frac{f'(x_i)}{f''(x_i)} $$

この手法をNewton法といいます。実際のプログラムではある程度反復したら終了する必要がありますが、数列が収束したかどうかを判定する条件として例えば $ \|x_{i+1}-x_{i}\| < \delta $ などを用います( $\delta$ は小さな正の数)。

Newton法は多変数関数に拡張できます。 二階微分可能な$n$ 変数関数 $f(x)$ の勾配を $ \nabla f(x) $ 、 Hesse行列を $H(x)$とすると、更新式は

$$ x_{i+1} = x_{i} - H(x_i)^{-1} \nabla f(x_i) $$

と表されます。ただし、Hesse行列の逆行列を計算するのは非効率的であるため、$d_{i} \in \mathbb{R}^n $ についての連立方程式

$$ H(x_i)\ d_{i} = -\nabla f(x) $$

を解くことで探索方向 $d_{i}$ を求め、

$$ x_{i+1} = x_{i} + d_{i} $$

で解を更新します。

Newton法は2次収束するという重要な性質を持っています。2次収束とは、 $i+1$ 回目の誤差が $i$ 回目の誤差の2乗に比例して減少していくような収束のことです。すなわち、 $x^*$ に収束するある点列 $\{x_i\}$ が次式を満たすとき、その点列は2次収束するといいます。

$$ \| x_{k+1} - x^* \| \leq M \| x_{k} - x^* \|^2 $$

ここで $ M $ は実数です。例えば $i$ ステップ目で誤差が $0.1$ のとき、 $i+1$ ステップ目ではほぼ $0.01$ 、その次のステップではほぼ $0.0001$ , $\cdots $ というように、非常に速く収束していきます。

証明

真の解を $ x^* $ として $ i $ 回目の解と真の解の差を $ \varepsilon_i = x_i - x^*$ とおきます。Newton法の更新の式の両辺から $x^*$ を減じると、
$$ \varepsilon_{i+1} = \varepsilon_{i}-\frac{f'(x_i)}{f''(x_i)} $$

ここで、 $f'(x_i) = f'(x^*+\varepsilon_i)$ 、 $f''(x_i) = f''( x^* + \varepsilon_i) $ のそれぞれのTaylor展開は、 $f'(x^*)=0$ であることを用いると、

$$ \begin{aligned} f'(x_i) & = f''(x^*)\varepsilon_i +\frac{1}{2}f'''(x^*)\varepsilon_i^2 + O\left(\varepsilon_i^3\right) \approx f''(x^*)\varepsilon_i +\frac{1}{2}f'''(x^*)\varepsilon_i^2 \\ \\ f''(x_i) & = f''(x^*) +f'''(x^*)\varepsilon_i + O\left(\varepsilon_i^2\right) \approx f''(x^*) +f'''(x^*)\varepsilon_i \end{aligned} $$

のようになります。この2式を誤差の漸化式に代入すると、
$$ \varepsilon_{i+1} \approx \varepsilon_{i}-\frac{f''(x^*)\varepsilon_i +\frac{1}{2}f'''(x^*)\varepsilon_i^2}{f''(x^*) +f'''(x^*)\varepsilon_i} $$

が得られます。右辺を通分し、分母を $f''(x^*) +f'''(x^*)\varepsilon_i \approx f''(x^*)$ と近似すると、最終的に以下の式が得られます。

$$ \varepsilon_{i+1} \approx \frac{f'''(x^*)}{2f''(x^*)}\varepsilon_i^2 $$

この式は、 $i+1$ 回目の誤差が $i$ 回目の誤差の2乗に比例することを示しています。したがって、Newton法が2次収束することが導かれました。