劣勾配を用いた最適化

凸関数$f: \mathbb{R}^d \rightarrow \mathbb{R}$の最小化を目指す．
$\bm{g} \in \mathbb{R}^d$を，点$\bm{x} \in \mathbb{R}^d$における劣微分の元（劣勾配）とする．すなわち，任意の$\bm{y} \in \mathbb{R}^d$について以下を満たす．

$\begin{aligned} f(y) \geq f(x) + \langle \bm{g}, \bm{y} - \bm{x} \rangle \end{aligned}$

多分$f$が凸関数じゃないと，劣微分が空集合な点が存在してしまう．
以下のように$\bm{x}$を更新することにする．

$\begin{aligned} \bm{x} \leftarrow \bm{x} + \eta \bm{g} \end{aligned}$

今，$\langle \bm{g}, \bm{x} + \eta \bm{g} - \bm{x} \rangle = \eta \|\bm{g}\|^2 \geq 0$なら，$f(\bm{x} + \eta \bm{g}) \geq f(\bm{x})$なので，$\eta < 0$とすれば，$f(\bm{x} + \eta \bm{g}) < f(\bm{x})$となり，この更新式で目的関数は単調に減少していく．

Written with StackEdit.