最適化 Newton法メモ

自分の言葉で書いて覚えるため（誤りがあればご指摘ください）

関数 $f(\vec{x})$ の2次までのTaylor展開

$f(\vec{x} + \vec{h}) = f(\vec{x}) + dot(\nabla f(\vec{x}), \vec{h}) + \frac{1}{2} dot(\vec{h^T}, \nabla^2 f(\vec{x})\vec{h})$

ここで $\nabla^2 f(\vec{x})$ はHesse行列

右辺を最小化にするような $\vec{h}$ によって $\vec{x}_{next} = \vec{x} + \vec{h}$ と更新することで
$f(\vec{x})$ をより小さくする $\vec{x}$ が得られる。
そのために $\vec{h}$ で微分して $$=0$$ となるような $\vec{h}$ を求める

$\frac{\mathrm{d} f(\vec{x}+\vec{h})}{\mathrm{d} \vec{h}} = \frac{\mathrm{d} f(\vec{x})}{\mathrm{d} \vec{h}} + \frac{\mathrm{d} dot(\nabla f(\vec{x}), \vec{h})}{\mathrm{d}\vec{h}} + \frac{1}{2} \frac{\mathrm{d} dot(\vec{h^T}, \nabla^2 f(\vec{x})\vec{h})}{\mathrm{d} \vec{h}} = 0$

右辺第一項は変数 $\vec{h}$ が無いので $$0$$

右辺第二項は内積をベクトル $\vec{h}$ で微分するので $\nabla f(\vec{x})$

右辺第三項は二次の同次多項式の二次形式 $dot(\vec{x^T}, A\vec{x})$ の微分なので、

$\frac{1}{2} \frac{\mathrm{d} dot(\vec{h^T}, \nabla^2 f(\vec{x})\vec{h})}{\mathrm{d} \vec{h}} = \frac{1}{2} (\nabla^2 f(\vec{x}) + \nabla^2 f(\vec{x})^T)\vec{h}$

ここで $$f(x)$$ が二階微分可能な場合にはHesse行列 $\nabla^2 f(x)$ は対称行列となるため、

$\frac{1}{2} (\nabla^2 f(\vec{x}) + \nabla^2 f(\vec{x})^T)\vec{h} = \frac{1}{2} (\nabla^2 f(\vec{x}) + \nabla^2 f(\vec{x}))\vec{h} = \frac{1}{2} (2 \nabla^2 f(\vec{x}) \vec{h}) = \nabla^2 f(\vec{x}) \vec{h}$

まとめると

$\frac{\mathrm{d} f(\vec{x}+\vec{h})}{\mathrm{d} \vec{h}} = 0 + \nabla f(\vec{x}) + \nabla^2 f(\vec{x}) \vec{h} = \nabla f(\vec{x}) + \nabla^2 f(\vec{x}) \vec{h} = 0$

変形して
$\nabla^2 f(\vec{x}) \vec{h} = -\nabla f(\vec{x})$

両辺の左からHesse行列 $\nabla^2 f(\vec{x})$ の逆行列 $\nabla^2 f(\vec{x})^{-1}$ をかけると

$\vec{h} = -\nabla^2 f(\vec{x})^{-1} \nabla f(\vec{x})$

このように求めたベクトル $\vec{h}$ をNewton方向とよび、ステップ幅 $\alpha ( 0 < \alpha \leq 1)$ を用いて

$\vec{x}_{next} = \vec{x} + \alpha \vec{h} = \vec{x} - \alpha \nabla^2 f(\vec{x})^{-1} \nabla f(\vec{x})$

で $\vec{x}$ を更新していくアルゴリズムをNewton法というらしい
( $\alpha$ は大抵1らしい. そういう $\vec{h}$ を計算したんだから)

実際には高次元の場合に $\nabla^2 f(\vec{x})$ の逆行列の計算コストが増大するため、
逆行列を近似して計算するらしい→準Newton法
あとそもそもHesse行列が正則じゃないと逆行列が求められないし、
Hesse行列が正定値でない場合に得られるNewton方向は
関数値が増える方向だったりするのでいろいろ欠点もある

最後の式 $\vec{x}_{next} = \vec{x} - \alpha \nabla^2 f(\vec{x})^{-1} \nabla f(\vec{x})$ は1変数関数 $$f(x)$$ についてのNewton法である

$x_{next} = x - \frac{f'(x)}{f''(x)}$

を多変数関数に拡張したものといえる( 逆数 $\frac{1}{f''(x)}$ が逆行列 $\nabla^2 f(\vec{x})^{-1}$ に対応)

求根アルゴリズムであるNewton法(Newton-Raphson法)は
関数 $$f(x) = 0$$ となるような $$x$$ を求めるために

$x_{next} = x - \frac{f(x)}{f'(x)}$

で更新するが、Newton法で極値を求める場合には $$f(x)$$ の極値( $$f'(x) = 0$$ の点 )を求めるために

$x_{next} = x - \frac{f'(x)}{f''(x)}$

として更新をするということらしい

参考とさせていただいた書籍およびサイト