📂최적화이론

프락시멀 오퍼레이터

정의¹

벡터공간 $X$의 놈을 $\left\| \cdot \right\|_{X}$라 하자. 함수 $f : X \to \mathbb{R}$에 대한 프락시멀 오퍼레이터^{proximal operator} $\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 point}라고 한다.

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 algorithm}이라 한다. 다음의 것들이 있다.

• 프락시멀 최소화 알고리즘
• 프락시멀 그래디언트 메서드
• 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)$이다.