📂최적화이론

프락시멀 그래디언트 메서드

정의 ¹

미분불가능한 목적함수 $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)})) $$

설명

경사하강법과 프락시멀 최적화를 같이 쓰기 때문에 proximal gradient method이다.

유도

※ $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*} $$

■