쌍대 상승법

최적설계 수치해석 마지막 수정: 2026-08-12 04:22:41

1. 개요[편집]

쌍대 상승법 Dual Ascent
다른 이름	쌍대 경사법, 가격 조정법(price adjustment)
대상 문제	min f(x) s.t. Ax = b
반복	x ← argmin_x L(x,y) / y ← y + α(Ax − b)
성립 조건	원시 최소화가 유일해야 쌍대 기울기가 잘 정의됨
스텝 상한	f가 μ-강볼록이면 α < 2μ/‖A‖²
최대 장점	f가 분리 가능하면 원시 스텝이 완전 병렬

쌍대 상승법은 제약 최적화 문제를 라그랑주 쌍대함수의 경사상승으로 푸는 방법이다. 제약을 직접 다루는 대신 승수(쌍대변수)를 하나 세워 두고, “현재 승수에서 원시 문제를 풀고 → 제약 위반량만큼 승수를 올린다”를 반복한다.

등식 제약 문제

\min_x\; f(x) \quad \text{s.t.}\quad Ax=b

에 대해 라그랑지안은 $L(x,y)=f(x)+y^\top(Ax-b)$ 이고 쌍대함수는

q(y) \;=\; \inf_x L(x,y) \;=\; -f^*(-A^\top y) - b^\top y

다(르장드르-펜셸 변환 참고). $q$ 는 아핀 함수들의 하한이므로 무조건 오목이고, 따라서 $\max_y q(y)$ 는 원 문제가 아무리 사나워도 볼록 문제다. 여기에 경사상승을 먹인 것이 전부다.

x^{k+1} = \arg\min_x L(x, y^k), \qquad y^{k+1} = y^k + \alpha^k\,(Ax^{k+1}-b)

두 줄 중 아름다운 것은 두 번째다. 쌍대 기울기가 곧 제약 위반량이라 별도 미분이 필요 없다. 제약을 넘치게 쓰면 그 자원의 “가격” $y$ 를 올리고, 남으면 내린다 — 경제학에서 나온 알고리즘답게 가격 조정 그대로다.¹ 문제는 이 알고리즘이 가정이 까다롭고 잘 깨진다는 것이고, 그 결함을 하나씩 메우는 과정이 증강 라그랑주법과 교대방향 승수법의 계보를 만들었다.

2. 왜 기울기라고 부를 수 있는가[편집]

$q$ 의 부미분은 다네스킨 정리 계열의 결과로 계산된다. 최소화기 집합을 $X(y)=\arg\min_x L(x,y)$ 라 하면 (적절한 정칙성 아래)

\partial q(y) = \overline{\mathrm{conv}}\ \bigl\{\,Ax - b \;:\; x \in X(y)\,\bigr\}

즉 최소화기가 유일하면 부미분이 한 점이 되어 $q$ 가 그 점에서 미분 가능하고, $\nabla q(y) = Ax^+(y)-b$ 라는 위의 갱신식이 정당해진다. 반대로 최소화기가 여럿이면 $q$ 는 그 지점에서 각져 있고, $Ax^{k+1}-b$ 는 여러 부경사 중 하나를 임의로 고른 것에 불과하다. 부경사 방향은 상승 방향이라는 보장이 없으므로, 이 경우 고정 스텝의 “상승법”은 그냥 틀린 이름이고 감소하는 스텝을 쓰는 부경사법으로 갈아타야 한다.

이 조건이 얼마나 빡빡한지는 선형 목적함수 하나로 드러난다. $f(x)=c^\top x$ 면

q(y) = \inf_x\,(c+A^\top y)^\top x - b^\top y = \begin{cases} -b^\top y & c+A^\top y = 0\\ -\infty & \text{그 외}\end{cases}

거의 모든 $y$ 에서 쌍대함수가 $-\infty$ 다. 원시 스텝이 발산해 버려서 알고리즘이 첫 반복에 죽는다. 선형계획법 하나 못 푸는 최적화 알고리즘인 셈. 필요한 것은 최소한 엄격 볼록(유일성)이고, 수렴률을 말하려면 강볼록까지 필요하다.

3. 스텝 크기[편집]

$f$ 가 $\mu$ -강볼록이면 켤레함수 $f^*$ 는 미분 가능하고 $\nabla f^*$ 가 $1/\mu$ -립시츠다. 이 성질이 쌍대로 전달되어

\lVert \nabla q(y_1) - \nabla q(y_2)\rVert \le \frac{\lVert A\rVert^2}{\mu}\,\lVert y_1-y_2\rVert

가 되고, 매끄러운 오목함수에 대한 경사상승의 표준 조건이 그대로 적용된다.

0 < \alpha < \frac{2\mu}{\lVert A\rVert^2}

강볼록성 $\mu$ 가 작을수록 스텝이 쪼그라든다. 그리고 강볼록성은 원시 문제의 성질이지 사용자가 고를 수 있는 값이 아니다. 이것이 쌍대 상승법의 실용적 사망 원인이다 — 목적함수가 조금만 평평해져도(예: 특이값이 작은 데이터 행렬, $\ell_1$ 벌점, 지시함수) $\mu \to 0$ 이고 스텝은 0 으로 간다. 수렴률도 쌍대 헤세 $A(\nabla^2 f)^{-1}A^\top$ 의 조건수에 걸린다.

여기에 하나 더. 원시 반복 $x^k$ 는 수렴을 보장받지 못한다. 수렴하는 것은 $y^k$ 이고, $x^k$ 는 대개 마지막까지 제약을 어긴 채로 남는다( $Ax^k-b$ 가 곧 기울기이므로 0 이 되는 것은 극한에서다). 그래서 “언제 멈춰도 실현 가능한 해가 나오는” 알고리즘이 아니고, 원시해 복원(primal recovery)이 별도의 골칫거리로 따라붙는다.

4. 쌍대 분해 — 이걸 보려고 참는다[편집]

단점 목록이 이렇게 긴데도 이 알고리즘이 교과서에서 안 없어지는 이유는 하나다. 목적함수가 분리 가능하면 원시 스텝이 완전히 병렬로 쪼개진다.

f(x)=\sum_{i=1}^{N} f_i(x_i), \qquad Ax = \sum_{i=1}^{N} A_i x_i = b

라그랑지안은 $L(x,y)=\sum_i \bigl(f_i(x_i)+y^\top A_i x_i\bigr) - y^\top b$ 로 $i$ 별로 완전히 분리된다. 승수 $y$ 가 고정되어 있는 한 각 블록은 서로를 전혀 모른 채 자기 문제만 풀면 된다.

x_i^{k+1} = \arg\min_{x_i}\ \bigl(f_i(x_i) + y^{k\top}A_i x_i\bigr) \quad (i=1,\dots,N \text{ 병렬})

그다음 각 블록이 $A_i x_i^{k+1}$ 만 중앙에 올려 보내고, 중앙은 합을 내 $y$ 를 한 번 갱신해 다시 뿌린다. 통신은 반복당 블록당 벡터 하나 올리고 하나 내리기가 전부다. 이 구조를 쌍대 분해(dual decomposition)라 부르며, 원 데이터가 블록 밖으로 나가지 않으므로 연합 학습이나 분산 최적화 계열의 사고 틀이 여기서 나왔다.² 자원 배분·네트워크 흐름·전력망 최적화에서 “가격을 방송하고 각자 최적 반응을 회신한다”는 시장 메커니즘 해석이 그대로 붙는 것도 이 구조 덕분이다.

문제는 앞 절의 결함이 여기서 그대로 반복된다는 것이다. 분리 가능한 $f_i$ 가 하필 선형이거나(자원 배분에서 흔하다) 평평하면 각 블록의 최소화기가 유일하지 않아 알고리즘이 흔들린다. 분해 가능성과 튼튼함을 동시에 갖고 싶다는 요구가 다음 절이다.

5. 계보 — 무엇이 무엇을 고쳤는가[편집]

방법	부분문제	분해 가능성	튼튼함
쌍대 상승법	$\min f(x)+y^\top Ax$	완전 병렬	엄격 볼록 필요, 스텝 민감
증강 라그랑주법	위 + 이차 벌점	깨짐	볼록이면 충분, 스텝= $\rho$ 자동
교대방향 승수법	블록별 한 스윕	2블록까지 회복	ALM 수준 유지

증강 라그랑주법은 $\frac{\rho}{2}\lVert Ax-b\rVert^2$ 를 얹어 부분문제를 강제로 강볼록으로 만든다. 유일성 문제가 사라지고, 게다가 승수 스텝을 $\rho$ 로 잡으면 쌍대 실현가능성이 자동으로 유지돼 스텝 튜닝 자체가 없어진다. 근접점 알고리즘의 언어로는 “각진 $q$ 를 모로 포락으로 다듬은 뒤 상승법을 돌린 것”이며, 다듬어진 함수는 항상 미분 가능하므로 위의 유일성 조건이 통째로 필요 없어진다. 유도는 증강 라그랑주법 문서에 있다.

대신 그 제곱항이 $x_i$ 들을 서로 얽어 분해 가능성을 죽인다. $\lVert \sum_i A_ix_i - b\rVert^2$ 를 전개하면 교차항 $x_i^\top A_i^\top A_j x_j$ 가 나오니 당연하다. 이 지점이 계보의 분기점이고, ADMM 은 “동시 최소화 대신 한 블록씩 한 번만 훑는다”는 절충으로 분해 가능성을 절반 되찾는다. 세 알고리즘의 관계를 한 줄로 요약하면 — 쌍대 상승은 병렬성만, 승수법은 튼튼함만, ADMM 은 둘을 반씩.

6. 부경사 버전과 정수 문제[편집]

원시 최소화의 유일성을 포기하고 감소하는 스텝( $\sum \alpha^k=\infty$ , $\sum(\alpha^k)^2<\infty$ )을 쓰면 쌍대 부경사법이 된다. 수렴은 $O(1/\sqrt{k})$ 로 느리지만 가정이 거의 없어서, 조합 최적화의 라그랑주 완화에서 표준 도구다. 정수 제약을 남긴 채 어려운 제약만 승수로 올리면 $q(y)$ 가 어떤 $y$ 에서든 최적값의 하한을 주므로(약쌍대성), 상승법을 돌리는 것 자체가 분지한정법의 한계를 조이는 작업이 된다. 외판원 문제의 헬드-카프 하한이 이 방식으로 계산되는 대표 사례다.

다만 비볼록·정수 문제에서는 쌍대 간극이 0 이 아니다. 쌍대를 아무리 잘 풀어도 원시 최적해가 안 나오고 하한만 나온다. “쌍대를 풀었으니 끝”이 성립하는 것은 강쌍대성이 성립할 때뿐이며, 이 구별을 흐리는 것이 이 계열의 가장 흔한 오해다.³

7. 실전에서 만나는 얼굴[편집]

우자와 알고리즘. 이차 목적함수 + 선형 제약(스토크스 문제, 접촉 구속)에 쌍대 상승법을 그대로 쓴 것이다. 이 경우 쌍대 헤세가 슈어 보수라 스텝 상한과 수렴률이 손으로 계산된다. 유한요소 쪽에서 이 알고리즘이 지금도 현역인 이유.
원시-쌍대 알고리즘. 원시 최소화를 정확히 하지 않고 근위 스텝 한 번으로 대체한 것. 정확한 argmin 을 못 푸는 상황에서 쌍대 상승의 골격만 남긴 형태로 볼 수 있다.
더글러스-래치포드 분할. 계보를 작용소 쪽에서 다시 쓰면, ADMM 은 쌍대 문제에 DR 을 돌린 것이고 그 축퇴 사례가 쌍대 상승이다. 단조 작용소 문서의 통일 표에서 위치를 확인할 수 있다.

8. 관련 문서[편집]

실제로 우자와가 이 알고리즘을 발표한 곳이 애로·후르비츠와 함께 낸 1958년 Studies in Linear and Nonlinear Programming 이고, 세 사람 중 둘은 나중에 노벨 경제학상을 받는다. 최적화 알고리즘을 배우다 보면 어느 순간 경제학자 이름만 잔뜩 나오는 구간이 오는데 여기가 그 구간이다. ↩
“각자 자기 데이터로 풀고 요약만 올린다”는 그림은 예쁘지만, 쌍대 상승법 그대로는 반복이 수천 번 필요해서 통신이 병목이 된다. 그래서 현대 분산 최적화는 대부분 ADMM 이나 그 변형으로 갔다. 아이디어의 지분은 쌍대 분해에 있고 실적은 후손이 챙긴 셈. ↩
정수 계획 하는 사람들이 “쌍대 상승으로 하한을 개선했다”고 말할 때, 최적해를 찾았다는 뜻이 아니다. 반대로 볼록 쪽 사람이 “쌍대를 풀면 원시가 나온다”고 말할 때는 강쌍대성을 전제하고 있다. 같은 단어로 다른 이야기를 하고 있으니 학회장에서 대화가 미묘하게 엇나간다. ↩