logo

프락시멀 그래디언트 메서드 📂최적화이론

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

정의 1

미분불가능목적함수 H(x):RnRH(\mathbf{x}) : \mathbb{R}^{n} \to \mathbb{R}가 미분가능한 함수 ff와 미분불가능한 함수 gg로 분해된다고 하자.

H(x)=f(x)+g(x) H(\mathbf{x}) = f(\mathbf{x}) + g(\mathbf{x})

다음과 같은 반복 알고리즘으로 HH에 대한 최적화문제를 푸는 방법을 프락시멀 그래디언트 메서드proximal gradient method라 한다.

x(k+1)=proxλg(x(k)λf(x(k))) \mathbf{x}^{(k+1)} = \operatorname{prox}_{\lambda g}(\mathbf{x}^{(k)} - \lambda \nabla f(\mathbf{x}^{(k)}))

설명

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

유도

f(x)f(\mathbf{x})를 테일러 정리로 근사하여 유도하는 방식은 수식 전개가 매끄럽지않아 알고리즘 공식을 납득하기 어렵다고 생각하기 때문에 소개하지 않는다.

우리가 최적화하고 싶은 함수는 HH인데 이를 미분가능한 부분 ff와 미분이 불가능한 부분 gg로 나눠서 생각한다. 다시말해 ffgg를 동시에 최적화하고 싶은 것이다. 그런데 ff는 미분이 가능하므로, 경사하강법을 통해 다음 스텝의 최적점을 얻을 수 있다.

xf=xλf(x) \mathbf{x}_{f} = \mathbf{x} - \lambda \nabla f(\mathbf{x})

이 점에서 멀리 떨어져있지 않으면서 동시에 gg를 최적화하는 점은 프락시멀 최적화로 얻을 수 있다.

x=proxλg(xf)=arg minv{g(v)+12λvxf22:vRn} \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\}

따라서 다음과 같은 최적해의 업데이트 공식을 얻는다.

x(k+1)=proxλg(x(k)λf(x(k)))=arg minv{g(v)+12λv(x(k)λf(x(k)))22:vRn} \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*}


  1. Parikh, Neal, and Stephen Boyd. “Proximal algorithms.” Foundations and trends® in Optimization 1.3 (2014), Ch4.2 Proximal gradient method ↩︎