근접점 알고리즘

수치해석 최적설계 마지막 수정: 2026-08-08 04:09:52

1. 개요[편집]

근접점 알고리즘 Proximal Point Algorithm
약칭	PPA
제안	Martinet (1970), Rockafellar (1976)
반복식	x^k+1 = prox_λf(x^k) = (I + λ∂f)⁻¹x^k
정체	극대단조 작용소의 영점을 찾는 리졸번트 반복
수렴 조건	영점이 존재하고 λ_k가 0으로 너무 빨리 죽지 않을 것

근접점 알고리즘은 목적함수의 최소점을, 매 스텝 “현재 위치에서 너무 멀어지지 말라”는 이차 벌점을 얹은 부분문제를 풀어 가며 찾아가는 반복법이다. 볼록 함수 $f$ 와 스텝 파라미터 $\lambda_k > 0$ 에 대해

x^{k+1} = \mathrm{prox}_{\lambda_k f}(x^k) = \arg\min_{y}\ \Bigl\{ f(y) + \frac{1}{2\lambda_k}\|y - x^k\|^2 \Bigr\}

한 줄이 전부다. 마르티네(1970)가 변분부등식의 정칙화로 도입했고, 록카펠라(1976)가 이것을 극대단조 작용소의 영점 찾기로 일반화하면서 현대 1차 최적화의 뼈대가 됐다.¹

이 알고리즘을 처음 보면 반드시 같은 의문이 든다. “부분문제가 원래 문제만큼 어려운데 이게 무슨 알고리즘이냐.” 맞는 지적이고, 실제로 PPA는 그 자체로 돌리는 물건이 아니라 다른 알고리즘들의 정체를 밝히는 틀로 쓰인다. 증강 라그랑주법, 교대방향 승수법, 더글러스-래치포드 분할, 근접 경사법이 전부 “어떤 문제에 PPA를 돌린 것”으로 정리된다. 이 문서는 그 수렴 이론과 파생 계보에 무게를 둔다. $\mathrm{prox}$ 연산자 자체의 정의·성질은 모로 포락 문서에 있다.

2. 리졸번트 반복 — 왜 무조건 수렴하나[편집]

$f$ 가 닫힌 진 볼록이면 부분문제의 최적성 조건은 $0 \in \partial f(x^{k+1}) + \frac{1}{\lambda_k}(x^{k+1}-x^k)$ , 즉

x^{k+1} = (I + \lambda_k \partial f)^{-1} x^k

이다. 우변을 작용소 $T = \partial f$ 의 리졸번트(resolvent) $J_{\lambda T}$ 라 부른다. 여기서 $T$ 가 굳이 어떤 함수의 부미분일 필요가 없다는 것이 록카펠라의 관점이다 — $T$ 가 극대단조(maximal monotone)이기만 하면, 민티 정리에 의해 $J_{\lambda T}$ 는 전 공간에서 정의된 단일값 사상이고 견고 비확장(firmly nonexpansive)이다. 특히 1-립시츠다.

\|J_{\lambda T}x - J_{\lambda T}y\| \le \|x - y\|

이 한 줄이 알고리즘의 정체를 다 말해 준다. 반복 사상이 어떤 $\lambda$ 를 골라도 확대되지 않으므로, 스텝을 아무리 크게 잡아도 발산할 수 없다. 경사하강법이 $\lambda < 2/L$ 을 지켜야 하는 것과 대조적이다.

이게 왜 공짜가 아닌지는 미분가능한 경우를 보면 즉시 드러난다. $x^{k+1} = x^k - \lambda_k \nabla f(x^{k+1})$ — 그래디언트를 다음 점에서 평가한다. 즉 PPA는 경사 흐름 $\dot{x} = -\nabla f(x)$ 에 대한 후진 오일러(암시적) 적분기다. 수치적분에서 암시적 방법이 무조건 안정한 대신 매 스텝 비선형 방정식을 풀어야 하는 것과 정확히 같은 거래를 하고 있는 셈이다.² 모로 포락의 언어로 쓰면 PPA 스텝은 $M_{\lambda f}$ 위에서의 명시적 경사하강이기도 하다 — 함수를 매끄럽게 바꾼 뒤 대놓고 내려가는 것과, 원함수에 암시적으로 내려가는 것이 같은 계산이다.

3. 이차 문제로 손으로 확인하기[편집]

말로만 하면 안 믿기니 $f(x) = \frac12 x^\top A x - b^\top x$ ( $A \succeq 0$ )로 직접 해 보자. 부분문제의 최적성 조건은 $(A + \frac{1}{\lambda}I)y = b + \frac{1}{\lambda}x$ 이므로

x^{k+1} = \bigl(I + \lambda A\bigr)^{-1}\bigl(x^k + \lambda b\bigr)

이고, 해 $x^\star$ ( $Ax^\star = b$ )에 대해 오차 점화식이 $x^{k+1}-x^\star = (I+\lambda A)^{-1}(x^k - x^\star)$ 로 깔끔하게 떨어진다. 반복 행렬의 고윳값은 $1/(1+\lambda\mu_i)$ — $A$ 의 고윳값 $\mu_i \ge 0$ 이 무엇이든, $\lambda$ 가 얼마든 전부 $(0,1]$ 안에 있다. 반면 경사하강법의 반복 행렬 $I - \lambda A$ 는 $\lambda < 2/\mu_{\max}$ 를 어기는 순간 발산한다. 무조건 안정성이 그냥 수사가 아니라는 것이 두 줄로 확인된다.

수축률은 $1/(1+\lambda\mu_{\min})$ 이라 $\lambda \to \infty$ 면 0으로 간다. 대신 매 스텝 푸는 $(A + \frac{1}{\lambda}I)y = \cdots$ 는 $\lambda$ 가 커질수록 원래의 $Ax=b$ 에 가까워져 어려워진다. 이 선형계가 정확히 티호노프 정규화된 계이고 조건수가 $\frac{1+\lambda\mu_{\max}}{1+\lambda\mu_{\min}} < \mathrm{cond}(A)$ 라는 점도 눈여겨볼 만하다 — 근접항은 바깥 반복을 안정화하는 동시에 안쪽 선형계를 잘 조건화한다. 특이하거나 병적으로 조건이 나쁜 문제에 근접항을 한 겹 씌우는 관행의 근거가 이것이다.

4. 수렴 이론[편집]

$T$ 가 극대단조이고 영점 집합 $T^{-1}(0)$ 이 비어 있지 않다고 하자.

전역 수렴. $\lambda_k$ 를 0으로 너무 빨리 보내지만 않으면 된다. 록카펠라의 원 논문은 $\inf_k \lambda_k > 0$ 을 걸었고, 이후 브레지-리옹 계열의 개선은 스텝 합이 발산한다는 조건( $\sum_k \lambda_k = \infty$ , 표준 교재판은 조금 더 강한 $\sum_k \lambda_k^2 = \infty$ )만으로 힐베르트 공간에서 약수렴이 나온다는 것을 보였다. 유한 차원이면 그냥 수렴이다.
함수값 감소율. $T=\partial f$ 인 최소화 문제에서는 $f(x^k) - f^\star = O\bigl(1/\sum_{i<k}\lambda_i\bigr)$ 다. 스텝을 키우면 그만큼 빨리 줄어든다는 뜻이라, ” $\lambda$ 를 무한대로 보내면 한 번에 끝난다”가 성립한다 — 실제로 $\lambda = \infty$ 는 원래 문제를 그냥 푸는 것이다. 수렴 속도는 부분문제 난이도로 사는 것이고, PPA는 그 교환율을 정직하게 보여 주는 알고리즘이다.
선형·초선형 수렴. $T^{-1}$ 이 0 근방에서 계수 $a$ 의 립시츠 성질을 가지면(강볼록이면 자동으로 성립) 오차가 인수 $a/\sqrt{a^2+\lambda_k^2} < 1$ 로 줄어든다. 즉 항상 선형 수렴이고, $\lambda_k \to \infty$ 로 키우면 초선형이 된다.

5. 비정확 판정 기준[편집]

부분문제를 정확히 풀 수 없다는 것이 실용화의 유일한 장벽이므로, 록카펠라는 “얼마나 대충 풀어도 되는가”를 함께 제시했다. $\hat{x}^{k+1} = J_{\lambda_k T}(x^k)$ 를 이상적인 값이라 할 때

\text{(A)}\quad \|x^{k+1} - \hat{x}^{k+1}\| \le \varepsilon_k,\ \ \sum_k \varepsilon_k < \infty

\text{(B)}\quad \|x^{k+1} - \hat{x}^{k+1}\| \le \delta_k \|x^{k+1} - x^k\|,\ \ \sum_k \delta_k < \infty

기준 (A)면 수렴이 보존되고, (B)면 위의 선형 수렴률까지 보존된다. (B)가 실무적으로 중요한 이유는 허용 오차가 스텝 크기에 비례하기 때문이다 — 초반에 크게 움직일 때는 대충 풀어도 되고, 해 근처에서 스텝이 작아지면 자동으로 정밀해진다. 안쪽 반복(inner iteration)의 종료 조건을 바깥 진행 상황에 연동시키는 오늘날의 관행이 여기서 나왔다.

6. 파생 — 이 바닥 알고리즘의 절반[편집]

록카펠라의 두 번째 1976년 논문이 남긴 결과가 특히 유명하다. 증강 라그랑주법(승수법)은 쌍대 문제에 적용한 근접점 알고리즘과 정확히 같다. 등식제약 문제의 쌍대함수 $g(y)$ 에 대해 $y^{k+1} = \mathrm{prox}_{c_k(-g)}(y^k)$ 를 전개하면, 그것이 바로 벌점계수 $c_k$ 인 승수법의 갱신식이다. 그래서 증강 라그랑주법의 승수 갱신이 왜 그렇게 안정적인지, 왜 $c_k$ 를 키워도 안 터지는지가 리졸번트의 비확장성 한 줄로 설명된다.³

여기서 계보가 갈라진다.

교대방향 승수법 — 쌍대에 더글러스-래치포드 분할을 돌린 것이고, DR 자체가 두 리졸번트를 엮는 PPA류 반복이다. ADMM의 수렴 증명이 목적함수의 볼록성만으로 끝나는 근거가 여기 있다.
근접 경사법(ISTA/FISTA) — 전진-후진 분할. 매끄러운 항엔 전진(명시적) 스텝, 비매끄러운 항엔 후진(리졸번트) 스텝. PPA의 반쪽만 쓰는 셈이라 스텝 제한 $\lambda \le 1/L$ 이 다시 등장한다.
연산자 분리 일반론 — 여러 개의 극대단조 작용소 합의 영점을 각각의 리졸번트로 나눠 공략하는 모든 기법이 이 우산 아래에 있다.

가속도 가능하다. 귈러(1992)는 네스테로프식 외삽을 얹어 $O(1/(\sum_k \sqrt{\lambda_k})^2)$ 로 개선했고, 이 아이디어가 나중에 임의의 알고리즘을 감싸 가속하는 Catalyst 계열로 이어진다. 물론 “PPA 자체는 못 쓴다”는 통념에도 예외는 있다.⁴

7. 비볼록에서는[편집]

$f$ 가 볼록이 아니면 부분문제가 최소점을 여러 개 가질 수 있어 $\mathrm{prox}$ 가 집합값이 된다. 그러나 $f$ 가 $\rho$ -약볼록 함수( $f + \frac{\rho}{2}\|\cdot\|^2$ 이 볼록)이기만 하면 $\lambda < 1/\rho$ 인 범위에서 부분문제가 여전히 강볼록이라 최소점이 유일하다. 즉 비볼록성의 정도가 스텝 크기의 상한을 정한다 — 볼록일 때 $\lambda$ 가 무제한이었던 자유가 딱 그만큼 회수된다. 이 영역에서는 목적값 대신 $\|\nabla M_{\lambda f}(x)\|$ 를 정상성 측도로 쓰며, 근접점법의 변형(prox-linear, 근접 다발법)이 비매끄러운 비볼록 손실의 표준 해석 틀이 됐다.

8. 관련 문서[편집]

Martinet, B. (1970). Régularisation d’inéquations variationnelles par approximations successives. / Rockafellar, R. T. (1976). “Monotone operators and the proximal point algorithm”, SIAM J. Control Optim. 14(5). 후자는 인용수만 보면 볼록해석에서 손에 꼽히는 논문인데, 정작 그 안에 “돌릴 수 있는 코드”는 한 줄도 없다. 이론이 밥값을 하는 방식이 이렇다. ↩
이 대응은 말장난이 아니라 정확한 동치다. 경사 흐름에 전진 오일러를 먹이면 경사하강법, 후진 오일러를 먹이면 근접점법이다. CFD 하던 사람이 “암시적이라 CFL 안 걸리는데 매 스텝 뉴턴 돌려야 하잖아요”라고 말하는 그 감각 그대로 가져오면 된다. ↩
그래서 벌점법(penalty method)과 승수법의 결정적 차이도 이 틀에서 보인다. 순수 벌점법은 $c\to\infty$ 로 보내야 해가 맞고 그 과정에서 조건수가 폭발하지만, 승수법은 $c$ 를 유한하게 두고도 정확한 해에 도달한다. 근접항이 매 스텝 이동하는 중심 $x^k$ 를 갖고 있기 때문이며, 벌점을 “고정 좌표계”가 아니라 “따라오는 좌표계”로 거는 것의 차이다. ↩
그렇다고 PPA를 절대 직접 못 쓰는 건 아니다. 부분문제가 원문제보다 조건이 좋아지는 경우 — 예를 들어 반정부호 계획법의 근접 갱신처럼 이차항 덕에 강볼록성이 생겨 내부점 솔버가 훨씬 편해지는 경우 — 에는 바깥 PPA + 안쪽 정확한 솔버 조합이 실제 경쟁력을 갖는다. Sun 계열의 SDPNAL 이 그 예다. ↩