원시-쌍대 알고리즘

편집 역사 토론
최적설계 수치해석 컴퓨터 그래픽스 마지막 수정: 2026-08-12 04:14:27

1. 개요[편집]

원시-쌍대 알고리즘
Primal–Dual Algorithm (PDHG)
다른 이름Chambolle–Pock, PDHG, 원시-쌍대 혼합 경사법
제안Chambolle–Pock (2011) · 조상은 Arrow–Hurwicz (1958)
대상 문제minx g(x) + f(Kx) — K는 선형작용소
한 반복쌍대 근위 상승 1회 + 원시 근위 하강 1회 + 외삽
스텝 조건τσ‖K‖2 < 1
대표 사용처전변분 잡음제거, 영상 복원 일반

원시-쌍대 알고리즘은 볼록 문제를 원시변수와 쌍대변수의 안장점 문제로 바꿔 놓고, 두 변수를 각각 근위 연산자 한 번씩으로 번갈아 갱신하는 1차 최적화 알고리즘이다. 좁은 의미로는 샹볼과 포크가 2011년에 정리한 형태(Chambolle–Pock, 흔히 PDHG)를 가리킨다.1

출발점은 이런 문제다.

min⁡x  g(x)+f(Kx)\min_{x}\; g(x) + f(Kx)

gg 와 ff 는 각각 prox 가 싼 닫힌 진 볼록 함수인데, 하필 ff 앞에 선형작용소 KK 가 끼어 있어서 f∘Kf\circ K 의 prox 가 닫힌 형태로 안 나오는 상황. 영상 처리에서는 이게 예외가 아니라 기본값이다(K=∇K=\nabla, f=f= 노름, g=g= 데이터 적합항). 근접 경사법은 f∘Kf\circ K 의 prox 를 요구하니 쓸 수 없고, 교대방향 승수법은 매 반복 K⊤KK^\top K 가 들어간 선형계를 풀라고 한다.

원시-쌍대의 처방은 KK 를 prox 안으로 넣지 말고 밖으로 빼내는 것이다. ff 를 르장드르-펜셸 변환으로 되돌려 f(Kx)=sup⁡y⟨Kx,y⟩−f∗(y)f(Kx) = \sup_y \langle Kx, y\rangle - f^*(y) 로 쓰면 문제가 안장점 형태가 된다.

min⁡xmax⁡y  ⟨Kx,y⟩+g(x)−f∗(y)\min_{x}\max_{y}\; \langle Kx, y\rangle + g(x) - f^*(y)

이제 KK 는 양변수를 잇는 쌍선형항 안에만 남아, 알고리즘에는 곱셈 KxKx 와 K⊤yK^\top y 로만 등장한다. 즉 KK 를 행렬로 저장할 필요조차 없고 전진·수반 곱만 있으면 된다.2 대가로 반복은 최소화가 아니라 안장점 추적이 되며, 여기서 생기는 회전 성분이 이 알고리즘 설계의 모든 어려움을 만든다.

2. 알고리즘[편집]

한 반복은 세 줄이다. xˉ0=x0\bar{x}^0 = x^0 에서 출발해

yn+1=proxσf∗(yn+σKxˉn)xn+1=proxτg(xn−τK⊤yn+1)xˉn+1=xn+1+θ (xn+1−xn)\begin{aligned} y^{n+1} &= \mathrm{prox}_{\sigma f^*}\bigl(y^n + \sigma K \bar{x}^n\bigr) \\ x^{n+1} &= \mathrm{prox}_{\tau g}\bigl(x^n - \tau K^\top y^{n+1}\bigr) \\ \bar{x}^{n+1} &= x^{n+1} + \theta\,(x^{n+1} - x^n) \end{aligned}

읽는 법은 이렇다. 첫 줄은 쌍대변수에 대한 근위 상승 한 스텝(안장점 함수는 yy 에 오목하므로 올라간다), 둘째 줄은 원시변수에 대한 근위 하강 한 스텝, 셋째 줄이 외삽(extrapolation)이다. 표준 선택은 θ=1\theta = 1 이고, 이때 xˉn+1=2xn+1−xn\bar{x}^{n+1} = 2x^{n+1} - x^n 이라 “직전 이동을 한 번 더 한 자리”를 쌍대 스텝에 먹인다.

θ=0\theta = 0 으로 두면 외삽이 사라지고 순수한 교대 경사 상승-하강, 즉 애로-후르비츠 방법(Arrow–Hurwicz, 1958)이 된다. 그리고 그게 정확히 문제 지점이다 — 단조 작용소 문서에 정리된 대로 안장점 문제의 작용소에는 반대칭(회전) 성분이 있어서, 단순 교대 갱신은 해 주위를 나선으로 돌며 밀려 나갈 수 있다. θ=1\theta=1 의 외삽은 그 회전을 반 스텝 앞질러 보정하는 장치이고, 이 한 줄이 알고리즘을 수렴하게 만든다.3

쌍대 prox 는 대개 직접 구현하지 않고 모로 항등식으로 원시 prox 에 넘긴다.

proxσf∗(v)=v−σ proxf/σ(v/σ)\mathrm{prox}_{\sigma f^*}(v) = v - \sigma\,\mathrm{prox}_{f/\sigma}(v/\sigma)

덕분에 f∗f^* 의 명시적 형태를 몰라도 ff 의 prox 만 있으면 된다(모로 포락 참고). ff 가 노름이면 f∗f^* 는 쌍대 노름 공의 지시함수이므로 쌍대 스텝은 그냥 공 위로의 사영이 된다.

3. 스텝 조건은 어디서 오는가[편집]

수렴 조건은 딱 하나다.

τσ∥K∥2<1,∥K∥=σmax⁡(K)\tau\sigma\lVert K\rVert^2 < 1, \qquad \lVert K\rVert = \sigma_{\max}(K)

τ\tau 와 σ\sigma 를 각각 얼마로 둘지는 자유이고 곱만 묶여 있다. 이 비대칭성이 실무에서는 튜닝 손잡이가 된다 — 원시 쪽이 잘 안 움직이면 τ\tau 를 키우고 σ\sigma 를 그만큼 줄인다. 균형 잡힌 기본값은 τ=σ=1/∥K∥\tau = \sigma = 1/\lVert K\rVert.

이 조건이 어디서 오는지는 두 가지 독립적인 설명이 있고, 둘 다 같은 부등식을 뱉는다.

(1) 계량을 바꾼 근접점법. 세 줄을 u=(x,y)u = (x,y) 로 묶어 정리하면 반복이 정확히

0∈T(un+1)+M (un+1−un),M=(1τI−K⊤−K1σI)0 \in T(u^{n+1}) + M\,(u^{n+1} - u^n), \qquad M = \begin{pmatrix} \tfrac{1}{\tau}I & -K^\top \\ -K & \tfrac{1}{\sigma}I\end{pmatrix}

꼴이 된다. 여기서 TT 는 안장점 문제의 KKT 작용소다. 즉 **원시-쌍대 알고리즘은 계량 MM 아래에서 돌린 근접점 알고리즘**이며, 근접점법의 무조건 수렴 이론을 그대로 상속받는다. 유일한 요구는 M≻0M \succ 0 인데, 슈어 보수를 취하면 1τI−σK⊤K≻0\frac{1}{\tau}I - \sigma K^\top K \succ 0, 즉 τσ∥K∥2<1\tau\sigma\lVert K\rVert^2 < 1 이다.4

(2) 선형화 ADMM. MM 의 좌상 블록에서 나온 1τI−σK⊤K\frac{1}{\tau}I - \sigma K^\top K 는 ADMM 쪽에서도 낯익은 물건이다. 문제 min⁡g(x)+f(z)\min g(x) + f(z) s.t. Kx=zKx = z 에 ADMM 을 돌리면 xx-갱신이 σK⊤K\sigma K^\top K 가 낀 선형계라 비싼데, 이 이차항을 xnx^n 주위에서 선형화하고 근접항 12∥x−xn∥D2\frac{1}{2}\lVert x-x^n\rVert^2_{D} 를 얹으면 prox 한 번으로 끝난다. 그 DD 가 바로 1τI−σK⊤K\frac{1}{\tau}I - \sigma K^\top K 이고, D≻0D \succ 0 이 다시 같은 조건이다. 요컨대 원시-쌍대 알고리즘은 선형화(전처리) ADMM 과 같은 알고리즘이다. 그리고 K=IK=I 면 애초에 선형화할 것이 없어져 그냥 ADMM 이 되고, ADMM 은 쌍대에 돌린 더글러스-래치포드 분할이므로 세 알고리즘이 한 점에서 만난다.

∥K∥\lVert K\rVert 를 모를 때가 문제인데, 대개는 멱반복 몇 번으로 추정하거나 이산 미분처럼 상한이 알려진 경우(22차원 이산 그래디언트는 ∥∇∥2≤8\lVert \nabla\rVert^2 \le 8)를 쓴다. 아예 스칼라 τ,σ\tau,\sigma 를 대각행렬로 바꿔 행·열 노름으로 자동 결정하는 대각 전처리 변형(Pock–Chambolle 2011)도 있고, 이쪽은 ∥K∥\lVert K\rVert 추정을 아예 없애 준다.

4. 정준 사용처 — 전변분 복원[편집]

이 알고리즘의 간판 응용은 ROF 모형이다.

min⁡u  12∥u−b∥2+λ TV(u)    ⟺    min⁡umax⁡∥p∥∞≤λ⟨∇u,p⟩+12∥u−b∥2\min_u\; \tfrac12\lVert u-b\rVert^2 + \lambda\,\mathrm{TV}(u) \;\;\Longleftrightarrow\;\; \min_u \max_{\lVert p\rVert_\infty \le \lambda} \langle \nabla u, p\rangle + \tfrac12\lVert u-b\rVert^2

K=∇K=\nabla, g(u)=12∥u−b∥2g(u)=\frac12\lVert u-b\rVert^2, f∗=f^*= 쌍대 공의 지시함수다. 그러면 각 스텝이 화소별 닫힌 형태로 떨어진다 — 쌍대 스텝은 화소마다 벡터를 반지름 λ\lambda 공으로 사영하는 것, 원시 스텝은 (u+τb)/(1+τ)(u+\tau b)/(1+\tau) 라는 나눗셈 한 번. 행렬은 어디에도 없고 반복당 비용이 그래디언트·발산 각 한 번이라, GPU 에서 그대로 돈다. 모형·아티팩트·λ\lambda 선택 등 ROF 자체의 내용은 전변분 잡음제거 문서에 있으니 여기서 반복하지 않는다.

같은 골격이 데이터항만 갈아 끼우면 통째로 재활용된다는 점이 진짜 매력이다. gg 를 12∥Au−b∥2\frac12\lVert Au-b\rVert^2 로 두면 디컨볼루션·전산 단층촬영 재구성, ℓ1\ell_1 데이터항으로 두면 임펄스 잡음 제거, KK 를 그래디언트와 관측행렬을 쌓은 블록으로 두면 광학 흐름이나 영상 분할의 볼록 완화가 된다. 비매끄러운 항 여러 개를 세로로 쌓아 하나의 KK 로 묶는 것이 이 계열의 표준 공작법이다.

5. 수렴률과 가속[편집]

  • 일반 볼록. 에르고딕 평균 ( xˉN,yˉN)(\,\bar{x}^N,\bar{y}^N) 의 부분 원시-쌍대 간극이 O(1/N)O(1/N) 으로 줄어든다. 여기서 간극이란 max⁡yL(xˉN,y)−min⁡xL(x,yˉN)\max_y \mathcal{L}(\bar x^N,y) - \min_x \mathcal{L}(x,\bar y^N) 로, 계산 가능한 정지 판정량이다. 이게 이 알고리즘의 실용적 장점 중 하나 — 최적값을 몰라도 현재 해의 품질에 상한을 매길 수 있다.
  • 한쪽이 강볼록. gg 가 γ\gamma-강볼록이면 θn=1/1+2γτn\theta_n = 1/\sqrt{1+2\gamma\tau_n}, τn+1=θnτn\tau_{n+1}=\theta_n\tau_n, σn+1=σn/θn\sigma_{n+1}=\sigma_n/\theta_n 으로 파라미터를 매 반복 조정해 O(1/N2)O(1/N^2) 로 승급한다. ROF 는 데이터항이 강볼록이라 이 조건에 그냥 들어맞는다.
  • 양쪽 다 강볼록. 고정 θ<1\theta<1 로 선형 수렴.

주의할 점 — O(1/N2)O(1/N^2) 가속은 파라미터를 정확한 강볼록 계수에 맞춰야 나온다. γ\gamma 를 과대평가하면 수렴이 깨지진 않지만 이론 보장이 사라지고, 과소평가하면 그냥 느려진다. 실무에서 잘못 잡은 γ\gamma 로 “가속이 안 되네요” 하는 사례가 흔하다.

6. 변형과 이웃[편집]

  • Condat–Vũ (2013). 목적함수에 매끄러운 항 hh 가 하나 더 있으면(min⁡g(x)+h(x)+f(Kx)\min g(x)+h(x)+f(Kx)) xx-스텝에 ∇h\nabla h 의 전진 스텝을 끼운다. 스텝 조건이 1τ−σ∥K∥2≥Lh2\frac{1}{\tau} - \sigma\lVert K\rVert^2 \ge \frac{L_h}{2} 로 바뀌며, 매끄러운 항의 립시츠 상수가 여유를 갉아먹는 구조가 그대로 보인다.
  • 여분 계산(extragradient). 코르펠레비치(1976)의 고전. 시험 스텝을 한 번 밟아 본 뒤 그 지점의 기울기로 본 스텝을 밟는다. 외삽 대신 함수 평가를 한 번 더 사는 셈이며, 생성적 적대 신경망 학습 안정화에서 재발견됐다.
  • PDHG 와 ADMM 사이. 위에서 봤듯 둘은 전처리 하나 차이다. 판단 기준은 단순하다 — K⊤KK^\top K 가 낀 선형계를 한 번 인수분해해서 캐시할 수 있으면 ADMM, 그럴 수 없거나 KK 가 연산자로만 주어지면 원시-쌍대.
  • 우자와 알고리즘. 쌍대 스텝을 “정확한 원시 최소화 + 승수 상승”으로 바꾸면 원시-쌍대의 조상격인 쌍대 상승법 계열이 된다. 실제로 이 계열은 영상처리 문헌에서 한동안 “분할 부정확 우자와(split inexact Uzawa)“라는 이름으로도 불렸다.

7. 실무 메모[편집]

  • τ,σ\tau,\sigma 는 곱만 지키면 되지만 비율이 수렴 속도를 지배한다. 원시·쌍대 잔차를 둘 다 찍어 보고 한쪽만 느리면 비율을 옮긴다. ADMM 의 ρ\rho 적응과 정확히 같은 감각이다.
  • 간극을 정지 조건으로 써라. 반복 수를 하드코딩하는 코드가 많은데, 위의 부분 간극은 몇 줄이면 계산된다.
  • 에르고딕 평균은 이론용이다. 실제로는 마지막 반복 xNx^N 이 평균보다 거의 항상 낫다(특히 해가 조각별 상수처럼 날카로울 때 평균은 그 날카로움을 뭉갠다). 이론 곡선과 구현이 갈리는 대표적 지점.
  • 비볼록에는 보장이 없다. gg 나 ff 가 비볼록이면 위의 근접점 해석이 통째로 무너진다. 돌아가긴 잘 돌아가지만 그건 휴리스틱이다.

8. 관련 문서[편집]

9. Footnotes[편집]

  1. Chambolle, A., Pock, T. (2011). “A First-Order Primal-Dual Algorithm for Convex Problems with Applications to Imaging”, J. Math. Imaging Vis. 40(1). 알고리즘 본체는 논문 3페이지에 세 줄로 끝나고 나머지는 전부 증명과 실험이다. 영상처리 대학원생이 “일단 이거부터 짜 보라”는 말을 듣는 그 알고리즘. ↩

  2. 그래서 이 계열 코드는 K(x) 와 KT(y) 두 함수만 주면 나머지가 그대로 돌아가는 구조로 짜는 게 국룰이다. 유한차분이든 FFT 든 라돈 변환이든 함수 두 개만 갈아 끼우면 되니, 한 번 짜 두면 정말 졸업할 때까지 쓴다. ↩

  3. 외삽이 없어도 실전에서 그럭저럭 도는 경우가 많아서 ”θ\theta 는 그냥 있어도 그만 없어도 그만”이라 생각하기 쉽다. 그런데 애로-후르비츠는 스텝을 충분히 작게 잡거나 강볼록성이 있어야 수렴하고, 일반 볼록에서는 반례가 있다. 공짜로 붙는 한 줄이니 그냥 붙이자. ↩

  4. He, B., Yuan, X. (2012)의 재해석. 이 관점이 나오기 전에는 스텝 조건이 “증명을 밀어 보니 나온 부등식”에 가까웠는데, 계량 MM 의 양정부호성이라는 정체가 밝혀지고 나서 대각 전처리·가속·확장이 줄줄이 따라 나왔다. 알고리즘을 이해한다는 게 뭔지 보여 주는 사례. ↩