[Convex optimization]ALM(Augmented Lagrangian Method)와 ADMM

유한성·2025년 9월 19일

ADMM은 ALM(첨가 라그랑주법)을 ‘변수 분할해서 번갈아 푸는(inexact/alternating) 방식’임

ALM 방식에 대한 설명 보완 예정

1) 문제 형식

선형 제약이 있는 분할형 최적화:

\min_{x,z}\; f(x) + g(z) \quad \text{s.t.}\quad Ax + Bz = c

첨가 라그랑지안(augmented Lagrangian):

\mathcal{L}_\rho(x,z,\lambda) = f(x)+g(z) +\lambda^\top(Ax+Bz-c) +\frac{\rho}{2}\,\|Ax+Bz-c\|_2^2

2) ALM (Augmented Lagrangian Method)

아이디어: 벌점(ρ)까지 넣은 라그랑지안을 각 반복에서 충분히 잘(minimize) 풀고, 그 뒤 라그랑주 승수 업데이트.

전형적 갱신:

\begin{aligned} (x^{k+1},\,z^{k+1}) &= \arg\min_{x,z}\; \mathcal{L}_\rho(x,z,\lambda^{k}),\\ \lambda^{k+1} &= \lambda^{k} + \rho\,\big(Ax^{k+1}+Bz^{k+1}-c\big). \end{aligned}

특징: 한 번의 서브문제가 무겁지만 반복 수는 비교적 적을 수 있음(정확히 풀기 때문).

3) ADMM (Alternating Direction Method of Multipliers)

아이디어: ALM을 변수 블록으로 쪼개서 교대로(가우스-자이델식) 최소화.

전형적 갱신:

\begin{aligned} x^{k+1} &= \arg\min_{x}\; \mathcal{L}_\rho\!\big(x,\,z^{k},\,\lambda^{k}\big),\\ z^{k+1} &= \arg\min_{z}\; \mathcal{L}_\rho\!\big(x^{k+1},\,z,\,\lambda^{k}\big),\\ \lambda^{k+1} &= \lambda^{k} + \rho\,\big(Ax^{k+1}+Bz^{k+1}-c\big). \end{aligned}

특징: 각 서브문제가 작고(simple/prox-friendly), 대규모/분산 계산에 적합.
다만 한 번의 업데이트가 덜 정확해서 반복 수는 더 필요할 수 있음.

요약: ALM = ‘정확히 풀고 승수 업데이트’, ADMM = ‘블록별로 번갈아가며 풀고 승수 업데이트’
⇒ ADMM은 inexact ALM 또는 ALM + 교대 최소화로 볼 수 있습니다. (이론적으로는 듀얼에서의 Douglas–Rachford 분할과도 동치)