📂最適化理論

近接作用素

定義¹

ベクトル空間 $X$のノルムを$\left\| \cdot \right\|_{X}$とする。関数$f : X \to \mathbb{R}$に対する プロキシマルオペレーター $\operatorname{prox}_{\lambda f} : X \to 2^{X}$を次のように定義する。$\lambda > 0$に対して、

$$\begin{align} \operatorname{prox}_{\lambda f} (\mathbf{x}) &:= \argmin\limits_{\mathbf{v}} \left\{ \lambda f(\mathbf{v}) + \dfrac{1}{2}\left\| \mathbf{v} - \mathbf{x} \right\|_{X}^{2} : \mathbf{v} \in X \right\} \\ &= \argmin\limits_{\mathbf{v}} \left\{ f(\mathbf{v}) + \dfrac{1}{2\lambda}\left\| \mathbf{v} - \mathbf{x} \right\|_{X}^{2} : \mathbf{v} \in X \right\} \nonumber \end{align}$$

$\argmin$は最適解を意味する。

わかりやすい定義

上記の定義が難しい場合は、次のように理解しても構わない。関数$f : \mathbb{R}^{n} \to \mathbb{R}$に対するプロキシマルオペレーター$\operatorname{prox}_{\lambda f} : \mathbb{R}^{n} \to \mathbb{R}^{n}$を次のように定義する。

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

説明 ²

定義$(1)$によると$\operatorname{prox}_{\lambda f} (\mathbf{x})$は$f$の関数値を最小化することと$\mathbf{x}$に近づくことの間の妥協点を意味する。つまり、$\mathbf{x}$の近辺で$f$の値を最も小さくする点であると言える。$f$を最適化する問題にある種の正則化を添加したものと見ることができる。$\lambda$の値によって、どの項を減らすことにより大きい価値を置くかが決まる。点$\operatorname{prox}_{\lambda f} (\mathbf{x})$を$f$に対する$\mathbf{x}$の プロキシマルポイント という。

proximalは「近接の」、「近い」という意味だが、$\operatorname{prox}_{\lambda f} (\mathbf{x})$は$\mathbf{x}$に近い点の中で$f$の最適解を見つけるという意味でproximalと名付けられたようだ。

$\operatorname{prox}_{\lambda f} (\cdot)$の計算が容易な関数$f$を prox friendly という。

$X = \mathbb{R}^{n}$の場合には$f$が凸関数であれば$\operatorname{prox}_{\lambda f} (\mathbf{x})$は一意^uniqueである。

プロキシマルオペレーターを使用して最適化問題を解くアルゴリズムを プロキシマルアルゴリズム という。以下が含まれる。

• プロキシマル最小化アルゴリズム
• プロキシマル勾配メソッド
• Proximal Alternating Linearized Minimization(PALM)アルゴリズム

性質³

• Separable sum: 関数$f$が$f(\mathbf{u}, \mathbf{v}) = \phi (\mathbf{u}) + \psi (\mathbf{v})$のように区切れる場合、次が成り立つ。 $$\operatorname{prox}_{\lambda f} (\mathbf{x}, \mathbf{y}) = (\operatorname{prox}_{\lambda \phi} (\mathbf{x}), \operatorname{prox}_{\lambda \psi} (\mathbf{y}))$$ 二つ以上の変数に対して$f(x) = \sum_{i}^{n}f_{i}(x_{i})$のように完全に区切られる場合は、 $$(\operatorname{prox}_{\lambda f} (x))_{i} = \operatorname{prox}_{\lambda f_{i}} (x_{i})$$
• Postcomposition: $f(\mathbf{x}) = \alpha \phi (\mathbf{x}) + b$、$\alpha \gt 0$に対して次が成り立つ。 $$\operatorname{prox}_{\lambda f} (\mathbf{x}) = \operatorname{prox}_{\alpha \lambda \phi} (\mathbf{x})$$
• Precomposition: $f(\mathbf{x}) = \phi (\alpha \mathbf{x} + b)$、$\alpha \ne 0$に対して次が成り立つ。 $$\operatorname{prox}_{\lambda f} (\mathbf{x}) = \dfrac{1}{\alpha}\left( \operatorname{prox}_{\alpha^{2} \lambda \phi} (\alpha \mathbf{x} + b) - b \right)$$ $f(\mathbf{x}) = \phi (Q \mathbf{x})$であり$Q$が直交である場合、次が成り立つ。 $$\operatorname{prox}_{\lambda f} (\mathbf{x}) = Q^{T}\operatorname{prox}_{\lambda \phi} (Q\mathbf{x})$$
• Affine addition: $f(\mathbf{x}) = \phi (\mathbf{x}) + \mathbf{a}^T\mathbf{x} + b$に対して次が成り立つ。 $$\operatorname{prox}_{\lambda f} (\mathbf{x}) = \operatorname{prox}_{\lambda \phi} (\mathbf{x} - \lambda \mathbf{a})$$
• Regularization: $f(\mathbf{x}) = \phi (\mathbf{x}) + \frac{\rho}{2} \left\| \mathbf{x} - \mathbf{a} \right\|_{2}^{2}$に対して次が成り立つ。 $$\operatorname{prox}_{\lambda f} (\mathbf{x}) = \operatorname{prox}_{\tilde{\lambda} \phi} ((\tilde{\lambda}/\lambda)\mathbf{x} + (\rho \tilde{\lambda}) \mathbf{a})$$ この時、$\tilde{\lambda} = \lambda / (1+\lambda \rho)$である。