📂最適化理論

近接勾配法

定義 ¹

微分不可能な目的関数$H(\mathbf{x}) : \mathbb{R}^{n} \to \mathbb{R}$が微分可能な関数$f$と微分不可能な関数$g$に分解されるとする。

$$ H(\mathbf{x}) = f(\mathbf{x}) + g(\mathbf{x}) $$

以下の繰り返しアルゴリズムで$H$の最適化問題を解く方法をプロキシマル勾配法^{proximal gradient method}という。

$$ \mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda g}(\mathbf{x}^{(k)} - \lambda \nabla f(\mathbf{x}^{(k)})) $$

説明

勾配降下法とプロキシマル最適化を一緒に使うから、プロキシマル勾配法という。

導出

※ $f(\mathbf{x})$をテイラーの定理で近似して導出する方法は、式の展開がスムーズではないと思われ、アルゴリズムの式を納得するのが難しいから、紹介しない。

最適化したい関数は$H$であり、これを微分可能な部分$f$と微分不可能な部分$g$に分けて考える。つまり、$f$と$g$を同時に最適化したいのだ。しかし、$f$は微分可能であるため、勾配降下法を通じて、次のステップの最適点を得ることができる。

$$ \mathbf{x}_{f} = \mathbf{x} - \lambda \nabla f(\mathbf{x}) $$

この点から遠くないところで同時に$g$を最適化する点は、プロキシマル最適化で得ることができる。

$$ \mathbf{x}_{\ast} = \operatorname{prox}_{\lambda g}(\mathbf{x}_{f}) = \argmin\limits_{\mathbf{v}} \left\{ g(\mathbf{v}) + \dfrac{1}{2\lambda}\left\| \mathbf{v} - \mathbf{x}_{f} \right\|_{2}^{2} : \mathbf{v} \in \mathbb{R}^{n} \right\} $$

したがって、次のような最適解の更新式を得る。

$$ \begin{align*} \mathbf{x}^{(k+1)} &= \operatorname{prox}_{\lambda g}(\mathbf{x}^{(k)} - \lambda \nabla f(\mathbf{x}^{(k)})) \\ &= \argmin\limits_{\mathbf{v}} \left\{ g(\mathbf{v}) + \dfrac{1}{2\lambda}\left\| \mathbf{v} - \left( \mathbf{x}^{(k)} - \lambda \nabla f(\mathbf{x}^{(k)}) \right) \right\|_{2}^{2} : \mathbf{v} \in \mathbb{R}^{n} \right\} \end{align*} $$

■