📂최적화이론

Proximal Alternating Linearized Minimization (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} $$

이는 쉽게 말해서 두 변수에 대한 교대 최적화를 프락시멀 그래디언트 메서드로 실시하는 것이다.

설명^{1 2}

논문의 초록^abstract에서 말하기를, PALM 알고리즘이란 볼록하지않고^nonconvex 매끄럽지않은^nonsmooth 최적화 문제를 풀기위한 방법이라고 소개한다. 다음과 같은 최적화문제를 생각해보자.

$$ \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$를 선형근사하겠다는 것을 의미한다. 두 변수 $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} \\ % &\approx \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y) \rangle \\ \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} \\ % &\approx \langle x - x^{(k)}, \nabla_{x}H(x^{(k)},y) \rangle \\ \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$의 두 변수 $x, y$를 번갈아가면서 최적화하는 교대 알고리즘을 적용하자. 그러면 문제 $(1)$은 다음과 같은 두 부분문제로 나뉜다.

$$ \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} $$

첫번째 수식의 경우, 두번째와 세번째항은 최적화에 아무런 영향을 끼치지 않으므로 제거하여도 같은 문제이다. 마찬가지로 두번째식에서 첫번째와 세번째항을 제거해도 같은 문제이다. 따라서 위의 알고리즘을 다음과 같이 고쳐쓸 수 있다.

$$ \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

  이제 첫번째 수식에서 두번째, 세번째항을 묶어 다음과 같이 두자.

  $$ \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} $$

■