📂最適化理論

近接最小化アルゴリズム

定義¹

目的関数 $f : \mathbb{R}^{n} \to \mathbb{R}^{n}$に対する最適化問題を解く時、プロキシマルオペレータを繰り返し適用して最適解 $\mathbf{x}^{(k)}$を更新する方法をプロキシマル最小化アルゴリズム^{proximal minimization algorithm}という。

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

説明

proximal point algorithm、proximal iterationとも呼ぶ。

最適化対象で、$\dfrac{1}{2}\left\| \mathbf{v} - \mathbf{x}^{(k)} \right\|_{2}^{2}$項は今回更新される $\mathbf{x}^{(k+1)}$が$\mathbf{x}^{(k)}$から遠く離れすぎるのを防ぐ。急に全く異なる値へ更新されないようにするということだ。つまり、目的関数全体で見た場合、前のステップから遠く離れすぎずに$f$を最小化する方向へ最適解が更新されると考えられる。