20-04-01 ADMM

다음 문제를 보자.

\begin{equation} \min_x f(x) + g(z) \quad \text{subject to} \quad Ax + Bz = c \end{equation}

앞에서처럼, 목적식을 다음과 같이 확장할 수 있다.

\begin{equation} \min_x f(x) + g(z) + \frac{\rho}{2} \lVert Ax + Bz - c \rVert_2^2 \quad \text{subject to} \quad Ax + Bz = c \end{equation}

여기서, \(\rho > 0\) 이다.

그리고, augmented Lagrangian을 다음처럼 정의할 수 있다.

\begin{equation} L_{\rho} (x,z,u) = f(x) + g(z) + u^T(Ax + Bz - c) + \frac{\rho}{2} \lVert Ax + Bz - c \rVert_2^2 \end{equation}

ADMM은 \(k=1,2,3 \dots\)에 대해서 다음의 step을 수행한다.

\[\begin{alignat}{1} x^{(k)} & = \arg\min_x L_{\rho} (x,z^{(k-1)},u^{(k-1)}) \\ z^{(k)} & = \arg\min_z L_{\rho} (x^{(k)},z,u^{(k-1)}) \\ u^{(k)} & = u^{(k-1)} + \rho (Ax^{(k)} + Bz^{(k)} - c) \end{alignat}\]

첫번째 식에서 구한 \(x^{(k)}\)가 \(z^{(k)}\)에 이용된다는 점은 매우 중요하다. 만일, 이렇게 하지 않으면 수렴되지 않을 수 있다.

일반 Method of multiplier에서는 처음 두 스텝이 다음의 joint 최소화로 바뀌게 된다는 점을 주의하자.

\begin{equation} (x^{(k)}, z^{(k)}) = \arg\min_{x,z} L_{\rho} (x,z,u^{(k-1)})
\end{equation}