더글러스-래치포드 분할

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 이 실험적으로는 얼마나 잘 되고 이론적으로는 얼마나 어려운지를 동시에 말해 준다. ↩