교대방향 승수법

최적설계 수치해석 통계 마지막 수정: 2026-08-06 04:38:52

1. 개요[편집]

교대방향 승수법 Alternating Direction Method of Multipliers
약칭	ADMM
기원	Glowinski–Marrocco (1975), Gabay–Mercier (1976)
대상 문제	min f(x) + g(z) s.t. Ax + Bz = c
수렴	닫힌 진 볼록 + 안장점 존재 → 임의의 ρ > 0에서 수렴
속도	일반적으로 O(1/k), 강볼록·평활이면 선형

교대방향 승수법(ADMM)은 목적함수가 두 덩어리로 쪼개지고 두 변수 블록이 선형 제약으로만 묶여 있는 문제

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

를, 증강 라그랑지안을 $x$ 와 $z$ 에 대해 번갈아 한 번씩만 최소화하고 승수를 갱신하는 방식으로 푸는 1차 최적화 알고리즘이다. 증강 라그랑지안을

L_\rho(x,z,y) = f(x) + g(z) + y^\top(Ax+Bz-c) + \frac{\rho}{2}\|Ax+Bz-c\|_2^2

로 두면 한 사이클은 다음 세 줄이 전부다.

x^{k+1} = \arg\min_x L_\rho(x,z^k,y^k), \quad z^{k+1} = \arg\min_z L_\rho(x^{k+1},z,y^k), \quad y^{k+1} = y^k + \rho\,(Ax^{k+1}+Bz^{k+1}-c)

핵심 아이디어는 “분해 가능성과 수렴성을 동시에 갖자”는 것이다. 벌점항 $\frac{\rho}{2}\|\cdot\|^2$ 이 $x$ 와 $z$ 를 뒤섞어 놓기 때문에 순수 쌍대 분해처럼 완전 병렬은 못 되지만, 한 블록씩 고정하면 각 부분문제는 원래 $f$ 나 $g$ 하나만 보는 작은 문제가 된다. 그래서 “각각은 쉬운데 합치면 어려운” 문제 — LASSO, 전변분 복원, 합의 학습, 행렬 완성 — 에 통째로 들어맞는다. 2011년 보이드 등의 서베이가 나온 뒤로는 사실상 대규모 볼록 최적화의 기본 공구가 됐다.¹

2. 계보 — 쌍대 상승에서 ADMM까지[편집]

쌍대 상승법. $\min f(x)$ s.t. $Ax=b$ 에서 라그랑지안 $L_0$ 을 $x$ 에 대해 최소화하고 $y \leftarrow y + \alpha(Ax-b)$ 로 올린다. $f$ 가 분리 가능하면 $x$ -단계가 완전 병렬이라 아름답다. 대신 $f$ 가 엄격 볼록하고 유한값이어야 부분문제가 잘 정의된다. 선형 $f$ 하나만 만나도 바로 무너진다.
승수법(Hestenes·Powell, 1969). 라그랑지안에 $\frac{\rho}{2}\|Ax-b\|^2$ 를 더한 증강 라그랑지안을 쓴다. 부분문제가 강볼록해져 훨씬 튼튼해지고, 스텝을 $\rho$ 로 잡으면 쌍대 실현가능성이 자동으로 유지된다. 대신 제곱항이 변수를 커플링해 분해 가능성이 죽는다.
ADMM. 승수법의 $x,z$ 동시 최소화를 한 번의 가우스-자이델 스윕으로 대체한다. 튼튼함(승수법)과 분해 가능성(쌍대 상승)을 절반씩 가져가는 타협이며, 놀랍게도 그 타협이 수렴을 깨지 않는다.

한 층 더 들어가면 ADMM은 쌍대 문제에 더글러스-래치포드 분할을 적용한 것과 정확히 같다(Gabay, 1983). 그래서 연산자 분리·근접 경사법 계열과 한 가족이며, 특수한 경우에는 승수법·근접점법과도 겹친다. 라그랑주 승수법의 현대적 후손 중 가장 실전형이라고 보면 된다.

3. 스케일된 형태와 prox[편집]

실무 코드는 거의 전부 스케일된 형태로 쓴다. 잔차를 $r = Ax+Bz-c$ , 스케일 승수를 $u = y/\rho$ 로 두고 제곱을 완성하면

x^{k+1} = \arg\min_x \Big( f(x) + \frac{\rho}{2}\|Ax + Bz^k - c + u^k\|^2 \Big), \qquad u^{k+1} = u^k + r^{k+1}

가 된다. 선형항과 이차항이 하나로 합쳐져 식이 짧아지고, 승수 갱신이 그냥 “잔차를 누적”으로 읽힌다 — 적분 제어기와 똑같은 구조다.²

$A=I,\ B=-I,\ c=0$ 인 표준 분할에서는 두 부분문제의 정체가 완전히 드러난다.

x^{k+1} = \mathrm{prox}_{f/\rho}(z^k - u^k), \qquad z^{k+1} = \mathrm{prox}_{g/\rho}(x^{k+1} + u^k)

즉 ADMM은 두 개의 근접 연산자를 번갈아 때리는 알고리즘이며, 그 이론적 토대가 모로 포락이다. 따라서 ADMM을 쓸 수 있느냐는 질문은 언제나 “이 부분문제의 prox가 싼가”로 환원된다. $f$ 가 이차형식이면 $x$ -단계는 $(\rho A^\top A + Q)$ 계열의 선형계 풀이라 촐레스키 분해를 한 번 만들어 캐시해 두고 매 반복 전진·후진 대입만 하면 되고, $g$ 가 $\ell_1$ 이면 $z$ -단계는 연성 임계화 한 줄, $g$ 가 지시함수면 사영 한 줄이다.

4. 잔차, 정지 조건, ρ 적응[편집]

ADMM에는 정지 판정에 쓸 수 있는 자연스러운 두 잔차가 있다.

원시 잔차 $r^k = Ax^k + Bz^k - c$ — 제약을 얼마나 어겼는가.
쌍대 잔차 $s^k = \rho A^\top B (z^k - z^{k-1})$ — 최적성 조건 $0 \in \partial f(x) + A^\top y$ 를 얼마나 어겼는가. $z$ 가 더 이상 안 움직이면 0이 된다.

둘 다 0이면 KKT 조건(카루시-쿤-터커 조건)이 정확히 만족된다. 그래서 표준 정지 규칙은 $\|r^k\|_2 \le \epsilon^{\text{pri}}$ 이고 $\|s^k\|_2 \le \epsilon^{\text{dual}}$ 이며, 허용오차는 절대항과 상대항을 섞어( $\epsilon^{\text{pri}} = \sqrt{p}\,\epsilon_{\text{abs}} + \epsilon_{\text{rel}}\max\{\|Ax^k\|,\|Bz^k\|,\|c\|\}$ ) 스케일에 둔감하게 만든다.

$\rho$ 를 키우면 제약 위반에 벌을 세게 물리므로 $\|r\|$ 이 빨리 줄지만 $z$ 가 크게 흔들려 $\|s\|$ 가 커진다. 반대도 마찬가지다. 그래서 두 잔차의 균형을 보고 $\rho$ 를 적응시킨다.

\rho^{k+1} = \begin{cases} \tau\rho^k & \|r^k\| > \mu\|s^k\| \\ \rho^k/\tau & \|s^k\| > \mu\|r^k\| \\ \rho^k & \text{그 외} \end{cases}

$\mu = 10,\ \tau = 2$ 가 흔한 기본값이다. 스케일된 형태를 쓰면 $\rho$ 를 바꿀 때 $u$ 도 반비례로 다시 스케일해 줘야 한다는 점만 조심하면 된다. 다만 $\rho$ 를 매번 바꾸면 $x$ -단계에 캐시해 둔 촐레스키 인수를 버려야 하므로, 초반 몇십 회만 조정하고 이후 고정하는 게 실전 요령이다.

5. 수렴 이론 — 튼튼하지만 느리다[편집]

$f, g$ 가 닫힌 진(closed proper) 볼록 함수이고 증강되지 않은 라그랑지안 $L_0$ 에 안장점이 존재하면 다음이 성립한다.

잔차 수렴: $r^k \to 0$ .
목적함수 수렴: $f(x^k)+g(z^k) \to p^\star$ .
쌍대변수 수렴: $y^k \to y^\star$ (어떤 쌍대 최적해로).

주목할 점은 $\rho > 0$ 이기만 하면 어떤 값이든 수렴한다는 것이다. $A$ 나 $B$ 가 full rank일 필요도 없고, $f$ 가 유한값일 필요도 없으며(지시함수 허용), 미분 가능성도 요구하지 않는다. 이 무조건성이 ADMM의 최대 매력이다.

그런데 수렴 속도는 $\rho$ 에 지독하게 민감하다. 일반 볼록에서는 (에르고딕 평균 기준) $O(1/k)$ 이고, $f$ 가 강볼록·그래디언트 립시츠면 선형 수렴으로 승급하며 이때 최적 $\rho$ 는 조건수의 기하평균 근처에서 나온다. 잘못 잡은 $\rho$ 는 수렴을 깨지는 않고 그저 반복 수를 10배, 100배로 불릴 뿐인데 — 실무에서는 그게 깨지는 것과 다를 바 없다.

여기서 ADMM의 진짜 성격이 드러난다. 적당한 정확도까지는 아주 빠르게 가고, 높은 정확도로는 아주 느리게 간다. 몇십 회 만에 그래프로 봐서 그럴싸한 해가 나오지만 $10^{-8}$ 상대오차를 원하면 내점법이 압도적으로 낫다. 통계·영상 문제처럼 데이터 잡음이 $10^{-2}$ 수준인 곳에서 ADMM이 사랑받고, 이차계획법 솔버의 정확해가 필요한 곳에서 외면당하는 이유가 이것이다.³

6. 합의 ADMM과 분산 최적화[편집]

ADMM이 빅데이터 시대에 재발견된 결정적 계기는 합의(consensus) 정식화다. 데이터를 $N$ 조각으로 나눠 각 조각의 손실을 $f_i$ 라 하면

\min_{x_1,\dots,x_N,\,z} \sum_{i=1}^{N} f_i(x_i) + g(z) \quad \text{s.t.} \quad x_i - z = 0 \;\; (i=1,\dots,N)

로 쓸 수 있다. 이 문제에 ADMM을 적용하면 갱신이 이렇게 갈라진다.

$x_i$ -단계: 각 노드가 자기 데이터만 보고 독립적으로 $\mathrm{prox}_{f_i/\rho}(z^k - u_i^k)$ 를 계산한다. 완전 병렬.
$z$ -단계: 평균 $\bar{x}^{k+1} + \bar{u}^k$ 에 $\mathrm{prox}_{g/\rho}$ 를 적용한다. 통신은 평균 한 번뿐.
$u_i$ -단계: 각 노드가 로컬로 갱신.

즉 map-reduce 한 라운드가 ADMM 한 반복에 정확히 대응한다. 원 데이터는 절대 노드 밖으로 나가지 않고 $x_i$ 요약만 오가므로 연합 학습 계열의 초기 골격도 여기서 나왔다. 변형인 교환(exchange) 문제는 $\sum_i x_i = 0$ 제약으로 자원 배분·전력망 최적화를 같은 틀에 담는다. 병렬 컴퓨팅 관점에서 통신량이 반복당 $O(n)$ 로 고정된다는 점이 특히 좋다.

7. 실무 메모와 비볼록[편집]

부분문제를 정확히 풀 필요는 없다. 부정확 ADMM은 부분문제 오차의 합이 유한하면 수렴이 유지된다. 대규모에서는 $x$ -단계를 CG 몇 회로 끊는 게 표준이다.
선형화 ADMM. $A$ 가 커플링을 심하게 만들어 $x$ -단계가 안 풀리면, 이차항을 근접항으로 대체해 prox 한 번으로 바꾼다(원시-쌍대 계열과 사실상 같은 알고리즘이 된다).
3블록 이상은 조심. 블록이 셋 이상인 직접 확장 ADMM은 볼록 문제에서도 발산하는 반례가 알려져 있다(Chen 등, 2016). 블록을 둘로 묶거나, 근접항·보정 단계가 있는 변형을 써야 한다. “블록 하나 더 붙이면 되겠지”가 가장 흔한 사고 원인이다.
비볼록. $f$ 나 $g$ 가 비볼록이면 위 수렴 정리는 통째로 사라진다. 그럼에도 $\ell_0$ 벌점, 위상 복원, 행렬 분해, 신경망 학습 같은 데서 ADMM은 실무적으로 꽤 잘 돈다. 부분적 보장(예: $g$ 가 매끄럽고 $\rho$ 가 충분히 크면 임계점 수렴)이 있긴 하지만 조건이 까다롭다. 정직하게 쓰자 — 비볼록 ADMM은 휴리스틱이며, 초기값과 $\rho$ 에 따라 다른 곳에 앉는다.

8. 관련 문서[편집]

Boyd, Parikh, Chu, Peleato, Eckstein, “Distributed Optimization and Statistical Learning via the Alternating Direction Method of Multipliers” (2011). 인용 수가 3만을 넘긴 서베이인데, 정작 알고리즘 자체는 1970년대 프랑스 수치해석 학파의 유한요소 논문에서 나왔다. 35년쯤 묵혀 뒀다가 데이터 규모가 커지자 갑자기 시대가 알고리즘을 따라잡은 사례. ↩
$u$ 가 잔차의 누적합이라는 사실은 PID 제어의 적분항과 구조가 같다. 그래서 ADMM 코드를 보다가 ” $\rho$ 는 적분 게인이구나”라고 생각하면 $\rho$ 튜닝 감각이 갑자기 생긴다. 너무 크면 출렁이고 너무 작으면 정상상태 오차(=제약 위반)가 안 죽는 것까지 똑같다. ↩
그래서 논문 그림의 x축이 “반복 횟수”이고 y축이 로그 스케일 상대오차인데 곡선이 초반에 절벽처럼 떨어지다 갑자기 눕는다면, 십중팔구 ADMM 계열이다. 반대로 마지막까지 직선으로 내리꽂히면 내점법이다. 그래프만 보고 알고리즘을 맞히는 건 이 바닥의 소소한 유흥. ↩