더글러스-래치포드 분할

1. 개요

더글러스-래치포드 분할 Douglas–Rachford Splitting
약칭	DRS, DR
기원	Douglas–Rachford (1956, 열전도) → Lions–Mercier (1979, 작용소)
대상 문제	0 ∈ A(x) + B(x) — A, B는 극대단조
반복 사상	T = ½(I + RBRA),  R = 2J − I
해	고정점 z가 아니라 그림자점 JA(z)
동치	쌍대 문제에 적용하면 ADMM (Gabay 1983)

더글러스-래치포드 분할은 두 단조 작용소의 합에 대한 포함 문제

$$0 \in A(x) + B(x)$$

를, $A$ 와 $B$ 를 각각의 리졸번트로만 건드려 푸는 작용소 분할 기법이다. 최적화 언어로 옮기면 $\min_x f(x)+g(x)$ 에서 $A=\partial f$, $B=\partial g$ 인 경우이며, 두 항이 모두 비매끄러워도 된다는 것이 이 방법의 존재 이유다.

비교하면 위치가 분명해진다. 근접 경사법(전진-후진)은 한쪽이 매끄럽고 그래디언트가 코코어시브일 것을 요구하고, 근접점 알고리즘은 $A+B$ 통째의 리졸번트를 요구한다. DR 은 양쪽 다 prox 만 있으면 되고 그 이상 아무것도 안 묻는다. 대가는 $x$ 를 직접 반복하지 않는다는 기묘한 구조인데, 그것이 이 문서의 절반이다.

2. 두 뿌리 — 열전도에서 작용소로

이름의 주인은 1956년 더글러스와 래치포드다. 원래 논문은 최적화와 아무 상관이 없었고, 2·3차원 열전도 방정식을 방향별로 쪼개 푸는 암시적 시간 적분 도식이었다.¹ $\partial_t u = (A+B)u$ 에서 $x$ 방향 확산과 $y$ 방향 확산을 번갈아 암시적으로 처리하는 그 계열 — ADI 법의 형제다. 오늘날 최적화 문헌의 DR 은 이 도식의 정상 상태 극한에 해당한다.

작용소 버전을 만든 것은 리옹과 메르시에(1979)다. 이들은 ”$e^{-\lambda A}$ 를 리졸번트 $(I+\lambda A)^{-1}$ 로 바꾸면 비선형·다가작용소에도 그대로 통한다”는 것을 보였고, 동시에 사촌인 피스먼-래치포드 분할($T_{\mathrm{PR}} = R_B R_A$, 평균 없이 반사 두 번)도 같은 틀에서 정리했다. 두 방법의 운명이 갈리는 지점이 정확히 그 평균 한 번이다 — 뒤에서 다시 본다.

3. 반사와 평균

극대단조 $A$ 의 리졸번트 $J_{\lambda A}=(I+\lambda A)^{-1}$ 에 대해 반사 리졸번트를 정의한다.

$$R_{\lambda A} = 2J_{\lambda A} - I$$

$J$ 가 견고 비확장이라는 사실은 정확히 ”$R$ 이 비확장”과 동치다(단조 작용소 문서의 동치 목록 참고). $A=N_C$ 면 $J=P_C$(사영)이고 $R_C = 2P_C-I$ 는 집합 $C$ 에 대한 반사다 — 점에서 $C$ 로 수선을 내리고, 그 발을 지나 같은 거리만큼 더 간다.

DR 반복은 두 반사를 합성한 뒤 항등사상과 평균 낸 것이다.

$$z^{k+1} = T z^k, \qquad T = \tfrac12\bigl(I + R_{\lambda B}R_{\lambda A}\bigr)$$

코드로 풀어 쓰면 한 반복이 리졸번트 두 번과 벡터 연산 몇 줄이다.

$$\begin{aligned} x^{k+1/2} &= J_{\lambda A}(z^k) \\ x^{k+1} &= J_{\lambda B}\bigl(2x^{k+1/2}-z^k\bigr) \\ z^{k+1} &= z^k + x^{k+1} - x^{k+1/2} \end{aligned}$$

마지막 줄이 이 알고리즘의 성격을 다 보여 준다. $z$ 는 두 리졸번트의 결과가 어긋난 만큼만 움직인다. 두 결과가 같아지면 $z$ 는 멈추고, 그때가 해다.

4. 그림자점 — 해는 z 가 아니다

DR 을 처음 구현하는 사람이 반드시 한 번 밟는 지뢰가 이것이다. 수렴하는 $z^k$ 자체는 해가 아니다. 해는 그 그림자점(shadow point)

$$x^\star = J_{\lambda A}(z^\star)$$

이다. 왜 그런지는 고정점 조건을 풀면 세 줄이면 나온다. $z^\star = Tz^\star$ 는 $J_{\lambda B}(R_{\lambda A}z^\star) = J_{\lambda A}(z^\star)$ 와 같은 말이다. $x^\star = J_{\lambda A}(z^\star)$ 라 두면 리졸번트의 정의로부터 $z^\star = x^\star + \lambda a$, $a\in A(x^\star)$ 이고, 두 번째 리졸번트 조건을 정리하면 $-a \in B(x^\star)$ 가 나온다. 따라서

$$0 = a + (-a) \in A(x^\star)+B(x^\star)$$

$z^\star$ 는 해 $x^\star$ 에 쌍대변수 $\lambda a$ 를 얹어 놓은 점인 셈이다. 그래서 $z$ 는 원시·쌍대 정보를 한 벡터에 접어 넣은 좌표이고, 해집합이 하나뿐이어도 $z^\star$ 는 여러 개일 수 있다. 실전에서 “잔차는 0 으로 가는데 $z$ 가 이상한 데 있다”고 당황하는 상황의 정체가 이것이며, 정지 판정도 $\lVert z^{k+1}-z^k\rVert$ 로 재고 결과는 반드시 $x^{k+1/2}$(또는 $x^{k+1}$)를 내보내야 한다.²

5. 왜 수렴하는가 — 목적함수가 등장하지 않는다

증명이 짧다는 것이 이 방법의 미학이다.

1. $R_{\lambda A}$, $R_{\lambda B}$ 는 비확장(리졸번트가 견고 비확장이므로).
2. 비확장 사상의 합성은 비확장. 따라서 $R_{\lambda B}R_{\lambda A}$ 는 비확장.
3. $T=\frac12(I+\text{비확장})$ 은 $\frac12$-평균화 사상. 크라스노셀스키-만 정리로 $z^k$ 는 $\mathrm{Fix}\,T$ 의 한 점으로 (약)수렴.
4. 앞 절에서 $\mathrm{Fix}\,T$ 의 그림자가 해집합과 일치함을 봤다.

함수값이 한 번도 나오지 않는다. $f,g$ 가 볼록이기만 하면 되고 미분 가능성·유한값·강볼록성 어느 것도 필요 없다. 스텝 $\lambda>0$ 도 아무 값이나 수렴한다. 대신 3단계는 $z^k$ 의 수렴만 주므로 그림자열이 정말로 해로 가는지는 별도 논증이 필요했고, 일반적인 경우의 증명은 한참 뒤에 정리됐다.

사촌인 피스먼-래치포드가 여기서 탈락한다. $T_{\mathrm{PR}}=R_{\lambda B}R_{\lambda A}$ 는 비확장이지만 평균화가 아니므로 3단계를 못 쓴다(예: 두 반사가 합쳐져 회전이 되면 영원히 돈다). 한쪽이 강단조여야 비로소 수축이 되며, 그때는 DR 보다 빠르다. 완화 파라미터 $\alpha\in(0,2)$ 로 $z^{k+1}=z^k+\alpha\bigl(x^{k+1}-x^{k+1/2}\bigr)$ 를 쓰면 $\alpha=1$ 이 DR, $\alpha=2$ 가 피스먼-래치포드로, 둘은 한 계열의 양 끝이다.

수렴은 무조건이지만 속도는 $\lambda$ 에 지독하게 민감하다. $A$ 가 $\mu$-강단조이고 $L$-립시츠인 경우 최적 스텝이 $\lambda^\star = 1/\sqrt{\mu L}$ 근처, 즉 두 극단의 기하평균에서 나온다는 결과가 알려져 있고, 실무 감각도 그쪽이다 — 한쪽 부분문제만 지배하게 만들지 말고 두 리졸번트가 비슷한 강도로 당기게 맞춰라.

6. 두 볼록집합 — 교대 반사

가장 그림이 잘 그려지는 사례는 실현가능성 문제 $\text{find } x\in C\cap D$ 다. $f,g$ 를 지시함수로 두면 리졸번트가 사영이 되어

$$z^{k+1} = \tfrac12\Bigl(z^k + R_D R_C\,z^k\Bigr), \qquad R_C = 2P_C - I$$

즉 **”$C$ 에 반사하고, $D$ 에 반사하고, 출발점과 평균 낸다”**가 전부다. 이 형태를 평균 교대 반사(averaged alternating reflections)라고 부른다. 고전적인 교대 투영법(폰 노이만의 교대 사영)과 비교하면 성격이 뚜렷이 다르다 — 사영은 항상 집합 쪽으로 끌어당기지만 반사는 집합을 관통해 반대편으로 넘긴다. 그래서 DR 궤적은 두 집합 사이를 크게 가로지르며 접근하고, 얕은 각도로 만나는 두 집합 사이에서 교대 사영이 지루하게 기어가는 상황에서도 훨씬 과감하게 움직인다.

7. 교집합이 없으면

$C\cap D=\varnothing$ 인 볼록 실현가능성 문제에 DR 을 돌리면 알고리즘은 조용히 발산한다. 정확히는 $\lVert z^k\rVert\to\infty$ 인데, 무작정 터지는 게 아니라 매 반복의 이동량이 두 집합 사이의 간극 벡터로 수렴한다.

$$z^{k+1}-z^k \;\longrightarrow\; v = P_{\overline{D-C}}(0)$$

즉 $z$ 는 간극 방향으로 일정 속도로 미끄러져 나간다. 그런데 그림자열은 유한한 곳에 남아 최근접 쌍(best approximation pair, $\lVert c-d\rVert$ 를 최소화하는 $c\in C$, $d\in D$)으로 수렴한다.³ 실무적 함의는 분명하다 — DR 코드에서 반복 벡터의 노름이 선형으로 커지고 있으면 버그가 아니라 문제에 해가 없다는 진단이며, 그때 출력해야 할 것은 여전히 그림자점이다.

8. ADMM 과의 동치

가베이(1983)의 결과가 이 문서에서 가장 자주 인용되는 문장일 것이다. 문제 $\min f(x)+g(z)$ s.t. $Ax+Bz=c$ 의 쌍대 문제에 DR 분할을 적용하면 정확히 교대방향 승수법이 된다. ADMM 의 $z$-갱신과 승수 갱신을 묶어 정리하면 위의 세 줄과 문자 그대로 같은 식이 나온다.

이 동치가 ADMM 이론의 뼈대를 통째로 설명한다. ADMM 이 왜 $\rho>0$ 이면 어떤 값이든 수렴하는가 — DR 의 $\lambda$ 가 임의여도 되기 때문. ADMM 이 왜 볼록성만 요구하는가 — 위 4단계 증명에 함수값이 없기 때문. ADMM 의 스케일된 승수 $u$ 가 왜 잔차의 누적처럼 생겼는가 — 그게 $z$ 좌표의 쌍대 성분이기 때문. 유도와 실무 세부는 교대방향 승수법 문서로 넘긴다.

한 층 더 올라가면 에크스타인과 베르체카스(1992)가 DR 자체가 어떤 작용소에 대한 근접점 알고리즘임을 보였고, 그 덕에 부정확 해법과 완화 파라미터를 포함한 일반형의 수렴이 한꺼번에 정리됐다. 근접점 알고리즘 문서의 “이 바닥 알고리즘의 절반” 이야기가 여기까지 이어진다.

9. 비볼록에서 왜 잘 도는가

이론적으로는 여기서 모든 보장이 끝난다. 집합이 비볼록이면 사영이 다가가 되고, 반사는 비확장이 아니며, 크라스노셀스키-만은 쓸 수 없다. 그런데 실제로는 놀랍도록 잘 돈다.

• 위상 복원. 푸리에 진폭만 관측하고 위상을 잃은 신호를 복원하는 문제는 “측정된 진폭을 갖는 집합”(구면, 비볼록)과 “지지·실수성 제약 집합”(볼록)의 교집합 문제다. 피눕의 HIO 알고리즘이 사실상 DR 과 같은 반복이라는 것이 볼록해석 쪽에서 재해석됐고, 결정학·회절 영상에서 수십 년간 실전 도구였다.
• 조합 퍼즐. 스도쿠, 8-퀸, 부분합 문제를 “집합 여러 개의 교집합 찾기”로 쓰고 DR 을 돌리면 상당한 규모까지 풀린다. 엘저 계열의 차분 사상(difference map) 연구가 이 실험들의 출처다.
• 왜? 정설은 없지만 자주 인용되는 설명은 이렇다. 교대 사영은 국소 최근접 쌍에 갇히면 못 나오는데, 반사는 집합을 관통하므로 갇힌 자리에서 밀려난다. 실제로 비볼록 DR 궤적을 그려 보면 국소 함정 주변을 크게 배회하다가 다른 골짜기로 넘어가는 모습이 자주 보인다.

부분적 이론은 있다. 두 집합이 횡단적으로(transversally) 만나면 교차점 근방에서 국소 선형 수렴이 증명되고, 구면과 직선처럼 아주 단순한 비볼록 쌍에서는 (특별한 시작점 집합을 빼고) 전역 수렴이 증명돼 있다.⁴ 그러나 일반적으로는 DR 의 비볼록 사용은 휴리스틱이며, 시작점에 따라 다른 곳에 앉거나 아예 순환에 빠질 수 있다는 점을 보고서에 정직하게 적는 게 맞다.

10. 관련 문서

• 단조 작용소 · 근접점 알고리즘 · 근접 경사법
• 교대방향 승수법 · 증강 라그랑주법 · 쌍대 상승법
• 원시-쌍대 알고리즘 · 우자와 알고리즘 · 모로 포락
• 연산자 분리 · ADI 법 · 반복법
• 볼록 최적화 · 변분부등식 · 전변분 잡음제거
• 압축센싱 · 기저 추구 · 수렴성

11. Footnotes

1. Douglas, J., Rachford, H. H. (1956). “On the numerical solution of heat conduction problems in two and three space variables”, Trans. Amer. Math. Soc. 82. 최적화 세미나에서 이 논문 제목을 처음 보면 다들 한 번 갸웃한다. 1950년대 석유회사 연구소(둘 다 험블 오일 소속이었다)에서 나온 열전도 차분 도식이 반세기 뒤 영상 복원 알고리즘의 이름이 될 줄은 본인들도 몰랐을 것이다. ↩

2. 그래서 DR 구현 첫 시도에서 “수렴은 하는데 답이 제약을 안 만족한다”는 증상이 나오면 십중팔구 $z$ 를 그대로 출력한 것이다. 심지어 $z$ 는 집합 $C$ 안에 들어 있지도 않다. 그림자를 찍어야 하는데 사람을 찍고 있었던 셈. ↩

3. Bauschke, Combettes, Luke (2004). 이 성질 덕분에 DR 을 “실현가능성 판정기”로 쓸 수도 있다 — 반복 이동량이 0 이 아닌 상수 벡터로 수렴하면 그 노름이 곧 두 집합 사이 거리의 추정치다. 발산하는 알고리즘에서 유용한 정보를 뽑아내는 흔치 않은 사례. ↩

4. 횡단성 아래 국소 선형 수렴은 헤세-루크(2013) 계열, 구면과 직선의 전역 수렴은 브누아(2015)의 결과다. “구와 직선”이라는 장난감 문제 하나를 엄밀히 푸는 데 논문 한 편이 필요했다는 사실이, 비볼록 DR 이 실험적으로는 얼마나 잘 되고 이론적으로는 얼마나 어려운지를 동시에 말해 준다. ↩