ニュートン法

$$g(v) := f(x + v) \approx f(x) + f'(x)^Tv + \frac{1}{2} v^T f''(x) v$$
$f$が凸だとすると，この２次近似も凸である．この近似式のヘッシアンは$f''(x)$なので，これが半正定値であればこの２次近似は凸．今，$f$が凸なので，そのヘッシアン$f''(x)$は半正定値行列．よってこの２次近似は凸．
この２次近似は凸なので，$g(v)=0$となる点がグローバルな最適解．これはFirst-order conditionから言える．以下のように求められる．

$$v = -f''(x)^{-1}f'(x)$$

つまり，$x \leftarrow x - f''(x)^{-1}f'(x)$と更新すれば良い．

ざっくり理解．

EquationTest

以下の点xにおける１次近似を最小化する方向vを求める．

$$f(x + v) \approx f(x) + f'(x)^Tv$$

最適化問題：

$$\begin{align*} \min_{v} &\ f'(x)^T v \\ s.t. &\ \|v\|^2_2 \leq 1 \end{align*}$$

$$L(v, \alpha) = f'(x)^Tv + \alpha (\|v\|^2_2 - 1)$$
where $\alpha \geq 0$.

$$\begin{align*} \frac{\partial L}{\partial v} = 0 &\Rightarrow f'(x) + \alpha v = 0 \\ &\Rightarrow v = - \frac{1}{\alpha} f'(x) \end{align*}$$

ここから，$v \propto -f'(x)$とわかる．

Written with StackEdit.