📂最適化理論

近接交互線形化最小化アルゴリズム (PALM)

概要

Jérôme Bolte、Shoham Sabach、Marc Teboulleの論文Proximal Alternating Linearized Minimization for nonconvex and nonsmooth problemsで紹介された最適化手法であるProximal Alternating Linearized Minimization(PALM)アルゴリズムについて説明する。

アルゴリズム

以下の$(1)$のような最適化問題を解く方法をProximal Alternating Linearized Minimization(PALM)アルゴリズムと呼ぶ。

$$\begin{cases} x^{(k+1)} \in \operatornamewithlimits{prox}_{\frac{1}{c}f} \left( x^{(k)} - \dfrac{1}{c}\nabla_{x}H(x^{(k)}, y^{(k)}) \right) \\ y^{(k+1)} \in \operatornamewithlimits{prox}_{\frac{1}{d}g} \left( y^{(k)} - \dfrac{1}{d}\nabla_{y}H(x^{(k+1)}, y^{(k)}) \right) \\ \end{cases}$$

簡単に言えば、2つの変数に対する交互最適化をプロキシマル勾配法で行うことである。

説明^{1 2}

論文のアブストラクトによると、PALMアルゴリズムは非凸で非滑らかな最適化問題を解くための方法として紹介されている。以下のような最適化問題を考えてみよう。

$$\operatornamewithlimits{minimize}_{x, y} \Psi (x, y) = f(x) + g(y) + H(x, y) \tag{1}$$

ここで$x \in \mathbb{R}^{n}, y \in \mathbb{R}^{m}$であり、$H : \mathbb{R}^{n} \times \mathbb{R}^{m} \to \mathbb{R}$は$C^{1}$関数である。また、$f, g, H$は凸関数ではないとしよう。

Linearized

アルゴリズム名のLinearizedは$H$を線形近似するという意味である。2つの変数$x$と$y$にそれぞれテイラーの定理を適用して、以下のように$H$を近似することができる。

$$\begin{align*} H(x, y) &\approx H(x^{(k)}, y) + (x - x^{(k)})^{T} \nabla_{x}H(x^{(k)},y) \\ &= H(x^{(k)} ,y) + \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y) \rangle \tag{2} \\ \end{align*}$$

$$\begin{align*} H(x, y) &\approx H(x, y^{(k)}) + (y - y^{(k)})^{T} \nabla_{y}H(x,y^{(k)}) \\ &= H(x, y^{(k)}) + \langle y - y^{(k)}, \nabla_{y}H(x,y^{(k)}) \rangle \tag{3} \\ \end{align*}$$

今$\Psi$で$H$を$(2)$に近似し、$\widehat{\Psi}$、$(3)$で近似したものを$\Phi$とする。

$$\begin{align*} \widehat{\Psi}(x,y) &= f(x) + g(y) + H(x^{(k)} ,y) + \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y) \rangle \\ \Phi (x,y) &= f(x) + g(y) + H(x, y^{(k)}) + \langle y - y^{(k)}, \nabla_{y}H(x,y^{(k)}) \rangle \end{align*}$$

以下の内容から、このように置いても結果は同じであることがわかる。しかし、とりあえず上記のように進めよう。

$$\begin{align*} \widehat{\Psi}(x,y) &= f(x) + \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y) \rangle \\ \Phi (x,y) &= g(y) + \langle y - y^{(k)}, \nabla_{y}H(x,y^{(k)}) \rangle \end{align*}$$

Alternating

次に、線形近似を適用し、$\Psi$の2つの変数を交互に最適化する交互アルゴリズムを適用する。すると、問題$(1)$は以下の2つの部分問題に分かれる。

$$\begin{cases} x^{(k+1)} &= \argmin\limits_{x} \widehat{\Psi}(x, y^{(k)}) \\ &= \argmin\limits_{x} f(x) + g(y^{(k)}) + H(x^{(k)} ,y^{(k)}) + \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y^{(k)}) \rangle \\ \\ y^{(k+1)} &= \argmin\limits_{y} \Phi (x^{(k+1)}, y) \\ &= \argmin\limits_{y} f(x^{(k+1)}) + g(y) + H(x^{(k+1)}, y^{(k)}) + \langle y - y^{(k)}, \nabla_{y}H(x^{(k+1)},y^{(k)}) \rangle \\ \end{cases}$$

最初の式では、2番目と3番目の項は最適化に影響を与えないので、削除しても問題は同じである。同様に、2番目の式では、最初と3番目の項を削除しても問題は変わらない。したがって、アルゴリズムは以下のように書き換えることができる。

$$\begin{cases} x^{(k+1)} = \argmin\limits_{x} f(x) + \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y^{(k)}) \rangle \\ y^{(k+1)} = \argmin\limits_{y} g(y) + \langle y - y^{(k)}, \nabla_{y}H(x^{(k+1)},y^{(k)}) \rangle \\ \end{cases} \tag{4}$$

Proximal

今、$(4)$にプロキシマル最適化のための項を追加すると、以下のようになる。

$$\begin{cases} x^{(k+1)} = \argmin\limits_{x} \left\{ f(x) + \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y^{(k)}) \rangle + \dfrac{c}{2}\left\| x - x^{(k)} \right\|_{2}^{2} \right\} \tag{5} \\ y^{(k+1)} = \argmin\limits_{y} \left\{ g(y) + \langle y - y^{(k)}, \nabla_{y}H(x^{(k+1)},y^{(k)}) \rangle + \dfrac{d}{2}\left\| y - y^{(k)} \right\|_{2}^{2} \right\} \\ \end{cases}$$

• 説明1

  最初の式で、2番目と3番目の項を以下のようにまとめる。

  $$\psi (x) = \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y^{(k)}) \rangle + \dfrac{c}{2}\left\| x - x^{(k)} \right\|_{2}^{2}$$

  $\psi$が最小になる点を見つけると、

  $$\begin{align*} \nabla_{x}\psi (x) = 0 &\implies \nabla_{x}H(x^{(k)}, y^{(k)}) + c(x - x^{(k)}) =0 \\ &\implies x = x^{(k)} - \dfrac{1}{c}\nabla_{x}H(x^{(k)}, y^{(k)}) \\ \end{align*}$$

  この点から離れすぎずに、同時に$f$も最小化する点はプロキシマルオペレータで表すことができる。したがって、$x^{(k+1)}$は以下のように更新される。

  $$x^{(k+1)} \in \operatornamewithlimits{prox}_{\frac{1}{c}f} \left( x^{(k)} - \dfrac{1}{c}\nabla_{x}H(x^{(k)}, y^{(k)}) \right)$$

  これはプロキシマル勾配法と同じである。

• 説明2

  最適化問題$(5)$は$\operatornamewithlimits{prox}_{cf} \left( x^{(k)} - \dfrac{1}{c}\nabla_{x}H(x^{(k)}, y^{(k)}) \right)$と同じであることを以下のように示すことができる。

  $$\begin{align*} & \operatornamewithlimits{prox}_{\frac{1}{c}f} \left( x^{(k)} - \dfrac{1}{c}\nabla_{x}H(x^{(k)}, y^{(k)}) \right) \\ &= \argmin\limits_{x} \left\{ f(x) + \dfrac{c}{2} \left\| x - \left( x^{(k)} - \dfrac{1}{c}\nabla_{x}H(x^{(k)}, y^{(k)}) \right) \right\|_{2}^{2} \right\} \\ &= \argmin\limits_{x} \left\{ f(x) + \dfrac{c}{2} \left\| (x - x^{(k)}) + \dfrac{1}{c}\nabla_{x}H(x^{(k)}, y^{(k)}) \right\|_{2}^{2} \right\} \\ &= \argmin\limits_{x} \left\{ f(x) + \dfrac{c}{2} \left\| (x - x^{(k)}) \right\|_{2}^{2} + (x - x^{(k)})^{T}\nabla_{x}H(x^{(k)}, y^{(k)}) + \dfrac{1}{c^{2}}\left\| \nabla_{x}H(x^{(k)}, y^{(k)}) \right\|_{2}^{2} \right\} \\ &= \argmin\limits_{x} \left\{ f(x) + \dfrac{c}{2} \left\| (x - x^{(k)}) \right\|_{2}^{2} + \langle x - x^{(k)}, \nabla_{x}H(x^{(k)}, y^{(k)}) \rangle \right\} \\ \end{align*}$$

上記の説明に従って、最終的に以下の繰り返しアルゴリズムを得る。

$$\begin{cases} x^{(k+1)} \in \operatornamewithlimits{prox}_{\frac{1}{c}f} \left( x^{(k)} - \dfrac{1}{c}\nabla_{x}H(x^{(k)}, y^{(k)}) \right) \\ y^{(k+1)} \in \operatornamewithlimits{prox}_{\frac{1}{d}g} \left( y^{(k)} - \dfrac{1}{d}\nabla_{y}H(x^{(k+1)}, y^{(k)}) \right) \\ \end{cases}$$

■