단조 작용소

1. 개요[편집]

단조 작용소 Monotone Operator
정의	⟨u − v, x − y⟩ ≥ 0  (u ∈ Tx, v ∈ Ty)
극대성	그래프가 다른 단조 작용소의 그래프에 진부분으로 담기지 않음
대표 예	볼록함수의 부미분 ∂f (Rockafellar 1970), 정규 원뿔, 반대칭 행렬
리졸번트	JλT = (I + λT)−1 — 단일값·전정의역·견고 비확장
기본 문제	0 ∈ Tx (영점 찾기) — 최소화·안장점·변분부등식을 전부 포괄
덮는 알고리즘	근접점법, 전진-후진, 더글러스-래치포드, 원시-쌍대

단조 작용소는 힐베르트 공간 $\mathcal{H}$ 위의 다가작용소 $T:\mathcal{H}\rightrightarrows\mathcal{H}$ 중, 그래프 위의 임의의 두 점 $(x,u),(y,v)$ 에 대해

$$\langle u-v,\; x-y\rangle \;\ge\; 0$$

를 만족하는 것을 말한다. 한 줄로 줄이면 “증가함수”의 다차원·다가 버전이다. 1차원에서 $T$ 가 함수면 위 조건은 $(f(x)-f(y))(x-y)\ge0$, 즉 단조 증가와 같은 말이다.

이 개념이 중요한 이유는 최적화·변분해석의 서로 달라 보이는 문제들이 전부 ”$0 \in T(x)$ 인 $x$ 를 찾아라” 한 문장으로 통합되기 때문이다. 볼록함수 최소화는 $T=\partial f$ 인 경우, 안장점 문제는 $T$ 가 원시·쌍대 부미분을 엮은 것, 변분부등식과 상보성 문제는 $T = F + N_C$ 인 경우다. 그리고 이 세 문제를 푸는 알고리즘들 — 근접점 알고리즘, 근접 경사법, 더글러스-래치포드, 교대방향 승수법, 원시-쌍대법 — 은 전부 리졸번트라는 한 종류의 사상을 어떻게 조합하느냐의 차이로 정리된다.¹

목적함수를 버리고 작용소만 남기는 것이 손해처럼 보이지만, 실제로는 목적함수가 아예 없는 문제(안장점, 균형 문제, 게임)까지 같은 이론이 덮게 된다는 점에서 이득이다.

2. 정의와 극대성[편집]

작용소는 그래프 $\mathrm{gra}\,T = \{(x,u): u\in Tx\}$ 와 동일시한다. 단조성은 그래프의 성질이고, 여기에 하나가 더 필요하다.

$T$ 가 극대단조(maximal monotone)라는 것은 $\mathrm{gra}\,T$ 가 어떤 단조 작용소의 그래프에도 진부분집합으로 담기지 않는다는 뜻이다. 왜 이게 필요한지는 1차원 예 하나면 충분하다. 정의역을 $[0,1]$ 로 잘라 놓은 항등사상은 단조지만, 정의역 밖의 어떤 점에도 값을 주지 않아 “구멍”이 있다. 이 구멍에 방정식의 해가 들어 있을 수도 있다. 극대성은 그래프에 빈틈이 없다는 조건이고, 이것이 있어야 해의 존재와 알고리즘의 잘 정의됨이 따라온다.

극대성의 실용적 판정 기준을 준 것이 민티 정리(Minty 1962)다.

단조 작용소 $T$ 가 극대단조일 필요충분조건은 어떤(따라서 모든) $\lambda>0$ 에 대해 $\mathrm{ran}(I+\lambda T) = \mathcal{H}$ 인 것이다.

즉 모든 $z$ 에 대해 $x + \lambda u = z$, $u \in Tx$ 를 만족하는 $(x,u)$ 가 존재한다. 이 정리 덕에 극대성이라는 다소 추상적인 조건이 “리졸번트가 전 공간에서 정의된다”는 계산 가능한 사실로 번역된다.

3. 볼록함수의 부미분 — 록카펠라 정리[편집]

가장 중요한 예는 부미분이다. $f$ 가 닫힌 진 볼록함수면 부미분의 정의 $f(y)\ge f(x)+\langle u,y-x\rangle$ 를 $x,y$ 두 방향으로 쓰고 더하기만 하면

$$\langle u-v,\ x-y\rangle \ge 0,\qquad u\in\partial f(x),\ v\in\partial f(y)$$

가 세 줄 만에 나온다. 어려운 것은 극대성이고, 이것이 록카펠라(1970)의 정리다.

$f$ 가 닫힌 진 볼록이면 $\partial f$ 는 극대단조다.

이 정리가 근접점 알고리즘·모로 포락·근접 경사법의 모든 수렴 증명이 딛고 서 있는 바닥이다.

반대 방향도 정확히 알려져 있다. 모든 극대단조 작용소가 어떤 볼록함수의 부미분인 것은 아니다. 부미분이 되려면 단조성보다 강한 순환 단조성(cyclic monotonicity)이 필요하고, 록카펠라(1966)는 “극대 순환단조 = 닫힌 진 볼록함수의 부미분”이라는 완전한 특성화를 줬다.

반례는 손으로 만들 수 있다. 반대칭 행렬 $S^\top = -S$ 로 정의한 선형작용소 $Tx = Sx$ 는

$$\langle Sx - Sy,\ x-y\rangle = \langle S(x-y),\, x-y\rangle = 0 \ \ge 0$$

이라 단조(그리고 연속이므로 극대)지만, 야코비안이 대칭이 아니므로 어떤 함수의 그래디언트도 될 수 없다. 2차원 회전 생성자 $S=\begin{pmatrix}0&1\\-1&0\end{pmatrix}$ 가 그 예다. 이 작용소가 바로 안장점 문제에서 튀어나오는 그 항이고, 안장점 알고리즘이 최소화 알고리즘보다 까다로운 이유의 근원이다 — 감소시킬 목적함수가 없다.

4. 리졸번트와 견고 비확장성[편집]

$T$ 가 극대단조일 때 리졸번트

$$J_{\lambda T} = (I+\lambda T)^{-1}$$

는 민티 정리에 의해 전 공간에서 정의되고, 단조성에 의해 단일값이며, 게다가 견고 비확장(firmly nonexpansive)이다.

$$\bigl\langle J_{\lambda T}x - J_{\lambda T}y,\; x-y \bigr\rangle \;\ge\; \bigl\|J_{\lambda T}x - J_{\lambda T}y\bigr\|^2$$

여기서 코시-슈바르츠를 한 번 쓰면 $\|J_{\lambda T}x - J_{\lambda T}y\|\le\|x-y\|$, 즉 1-립시츠가 따라온다. 견고 비확장은 다음 세 조건과 동치라는 것을 알아 두면 편하다.

• $J$ 가 $\tfrac12$-평균화(averaged): $J = \tfrac12(I+N)$ 인 비확장 $N$ 이 존재.
• 반사 작용소 $R_{\lambda T} = 2J_{\lambda T} - I$ 가 비확장.
• $I - J$ 역시 견고 비확장.

두 번째 항목이 더글러스-래치포드가 왜 “반사하고 반사하고 평균 내는” 모양인지를 설명한다. 대표적인 리졸번트 두 개는 이미 익숙한 물건이다.

• $T=\partial f$ → $J_{\lambda T} = \mathrm{prox}_{\lambda f}$ (근접 연산자)
• $T=N_C$ (볼록집합 $C$ 의 정규 원뿔) → $J_{\lambda T} = P_C$ (사영)

사영이 비확장이라는 초등적 사실과 prox가 비확장이라는 사실이 같은 정리의 두 사례라는 것이 작용소 관점의 첫 배당금이다.

5. 상수의 사전 — 강단조와 코코어시브[편집]

수렴률을 말하려면 단조성에 정량적 눈금이 필요하다.

성질	조건	함수 쪽 대응
단조	내적 ≥ 0	볼록
$\mu$-강단조	내적 ≥ $\mu\lVert x-y\rVert^2$	$\mu$-강볼록
$\beta$-코코어시브	내적 ≥ $\beta\lVert Tx-Ty\rVert^2$	그래디언트가 $1/\beta$-립시츠
$L$-립시츠	상한 $L\lVert x-y\rVert$	그래디언트 립시츠

여기서 함수 쪽 대응의 세 번째 줄이 바이용-아다르 정리다 — $f$ 가 볼록이고 $\nabla f$ 가 $L$-립시츠면 $\nabla f$ 는 자동으로 $1/L$-코코어시브다. 립시츠성만 가정했는데 훨씬 강한 성질이 공짜로 따라오는 이 정리가, 매끄러운 볼록 최소화에서 스텝 크기 $\eta<2/L$ 이 왜 통하는지의 진짜 이유다.

단조 + 립시츠는 코코어시브를 함의하지 않는다. 위의 반대칭 $S$ 가 정확히 반례로, $\langle Sx-Sy,x-y\rangle = 0$ 인데 $\|S(x-y)\|$ 는 0이 아니다. 그래서 전진-후진 분할을 안장점 문제에 그대로 적용하면 발산한다 — 그림으로는 순수한 회전장 위에서 명시적 오일러를 돌리는 것과 같아서, 스텝마다 원 밖으로 밀려 나간다. 여분한 계산(extragradient)이나 전진-후진-전진 같은 보정이 필요한 이유가 이 한 칸의 빈자리다.²

강단조가 있으면 리졸번트가 수축이 된다 — $\|J_{\lambda T}x-J_{\lambda T}y\|\le\frac{1}{1+\lambda\mu}\|x-y\|$. 선형 수렴은 전부 이 인수에서 나온다.

6. 알고리즘의 통일[편집]

이제 계보를 한눈에 정리할 수 있다. 문제는 항상 $0\in Tx$ 이고, $T$ 를 어떻게 쪼개느냐가 알고리즘을 정한다.

• 근접점법. $T$ 를 안 쪼갠다. $x^{k+1}=J_{\lambda_k T}x^k$. 견고 비확장 사상의 고정점 반복이므로 크라스노셀스키-만 정리로 약수렴이 나온다. 스텝 크기에 상한이 없다는 것이 특징이며, 대가는 부분문제 비용이다.
• 전진-후진 분할. $0\in Ax+Bx$ 에서 $A$ 는 극대단조, $B$ 는 $\beta$-코코어시브. $x^{k+1}=J_{\lambda A}(x^k-\lambda Bx^k)$ 가 $\lambda\in(0,2\beta)$ 에서 수렴한다. $A=\partial g$, $B=\nabla f$ 로 두면 그대로 ISTA이고, $A=N_C$ 로 두면 투영 경사법이다. 스텝 상한 $2\beta$ 가 왜 생기는지가 코코어시브 상수 하나로 설명된다.
• 더글러스-래치포드 분할. $A,B$ 둘 다 극대단조이기만 하면 된다(코코어시브 불필요).

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

두 반사 작용소의 합성이 비확장이므로 그 평균은 평균화 사상이고, 다시 크라스노셀스키-만이 적용된다. 비확장성의 대수만으로 증명이 끝난다 — 목적함수 값은 한 번도 등장하지 않는다.

• 교대방향 승수법. 쌍대 문제에 더글러스-래치포드를 돌린 것(Gabay 1983). ADMM 수렴 증명이 볼록성 말고 아무것도 요구하지 않는 이유가 이것이다.
• 여분 계산·원시-쌍대. $B$ 가 단조·립시츠일 뿐이면(안장점의 반대칭 항) 코르펠레비치의 extragradient나 셍의 전진-후진-전진을 쓴다. 샹볼-포크의 원시-쌍대 알고리즘은 KKT 작용소에 계량을 바꾼 근접점법을 돌린 것으로 재해석되며, 이 재해석이 나온 뒤에야 스텝 조건 $\tau\sigma\|K\|^2<1$ 의 정체가 분명해졌다.

공통 구조는 하나다. 알고리즘을 어떤 평균화 사상 $M$ 의 고정점 반복으로 쓰고, $\mathrm{Fix}\,M$ 이 해집합과 일치함을 보인 뒤, 크라스노셀스키-만 정리를 인용한다. 페예르 단조성(해집합의 임의의 점까지의 거리가 단조 감소)이 증명의 뼈대이며, 힐베르트 공간에서는 약수렴, 유한 차원에서는 그냥 수렴이다.

7. 변분부등식과 안장점[편집]

목적함수 없는 문제들이 이 언어의 진짜 무대다.

변분부등식. 볼록집합 $C$ 와 사상 $F$ 에 대해 $x\in C$, $\langle F(x),\,y-x\rangle\ge0\ (\forall y\in C)$ 을 찾는 문제는

$$0 \in F(x) + N_C(x)$$

와 정확히 동치다. $F=\nabla f$ 면 제약 최소화의 1차 조건이지만, $F$ 가 그래디언트가 아니어도 문제는 그대로 성립한다 — 교통망 균형, 시장 균형, 마찰 접촉 문제가 이 형태다. $C$ 가 원뿔이면 선형 상보성 문제로 특수화되고, 게임 이론의 내시 균형도 각 참가자의 최적성 조건을 쌓으면 이 꼴이 된다.

안장점. $L(x,y)$ 가 $x$ 에 볼록·$y$ 에 오목이면

$$T(x,y) = \bigl(\partial_x L(x,y),\ \partial_y(-L)(x,y)\bigr)$$

가 극대단조이고, 안장점이 곧 $T$ 의 영점이다. 라그랑주 함수 $L(x,y)=f(x)+\langle y, Ax-b\rangle$ 로 두면 $T$ 는 “부미분 + 반대칭 선형” 형태가 되어, 앞에서 본 회전 성분이 그대로 등장한다. 안장점 문제에서 단순 경사 상승-하강이 왜 궤도를 그리며 돌기만 하는지, 왜 근접항이나 여분 계산이 필요한지가 이 분해로 설명된다.

8. 한계[편집]

작용소 언어가 만능은 아니다.

• 속도 정보가 약하다. 목적함수를 버렸으므로 “함수값이 얼마나 줄었나”를 말할 수 없다. 대신 리졸번트 잔차 $\|x^{k+1}-x^k\|$ 같은 양으로 수렴을 재는데, 이것이 해까지의 거리와 어떻게 연결되는지는 별도의 오차 한계 조건이 필요하다.
• 무한 차원에서는 약수렴뿐. 크라스노셀스키-만이 주는 것은 약수렴이고, 강수렴을 얻으려면 추가 가정(강단조, 콤팩트성)이나 할펀 반복 같은 변형이 필요하다.
• 비볼록으로 나가면 무너진다. 단조성을 조금 완화한 저단조(hypomonotone)·약볼록 함수 정도까지는 리졸번트가 살아남지만($\lambda$ 에 상한이 붙는 대가로), 일반 비볼록에서는 리졸번트가 다가가 되어 이론이 끝난다.
• 합의 극대성이 자동이 아니다. $A,B$ 가 각각 극대단조여도 $A+B$ 가 극대단조라는 보장은 없고, 정의역 조건(로카펠라 조건 등)이 필요하다. 분할 알고리즘의 정리마다 붙어 있는 자잘한 가정들이 대개 이것이다.³

9. 관련 문서[편집]

• 근접점 알고리즘 · 근접 경사법 · 모로 포락
• 연산자 분리 · 교대방향 승수법 · 더글러스-래치포드 분할
• 볼록 최적화 · 르장드르-펜셸 변환 · 카루시-쿤-터커 조건
• 변분부등식 · 선형 상보성 문제 · 안장점
• 증강 라그랑주법 · 라그랑주 승수법 · 게임 이론
• 반복법 · 수렴성 · 전변분 잡음제거

10. Footnotes[편집]

1. 이 관점의 표준 참고서는 Bauschke & Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces다. 600쪽이 넘는데 알고리즘은 뒤쪽 몇 장에만 나오고 앞은 전부 사상의 성질이다. 처음 펴면 “이걸 왜 이렇게까지 하나” 싶지만, 새 분할 알고리즘의 수렴 증명을 세 줄로 끝내는 순간 앞의 500쪽 값을 한다. ↩

2. 이 현상은 GAN 학습이 진동하는 이유를 설명할 때도 그대로 인용된다. 최소최대 문제의 벡터장에 회전 성분이 있으면 단순 경사 갱신은 나선을 그리며 밖으로 밀려 나간다. 딥러닝 쪽에서 재발견된 “extragradient가 GAN을 안정화한다”는 이야기는 1976년 코르펠레비치의 결과를 다시 만난 것이다. ↩

3. 번역어가 통일돼 있지 않은 분야이기도 하다. subdifferential은 부미분·준미분·열미분이 섞여 쓰이고, resolvent는 리졸번트·레졸벤트·해석자가 다 보이며, firmly nonexpansive는 견고 비확장·강비확장이 갈린다. 논문을 한글로 쓸 때 원어를 괄호로 병기하는 관행이 여기서만큼은 정말 필요하다. ↩