마라토스 효과

1. 개요

마라토스 효과 Maratos Effect
발견	N. Maratos (1978), 임페리얼 칼리지 런던 박사논문
증상	해 근처에서 이차 수렴을 주는 단위 스텝이 병합함수를 증가시켜 거부됨
원인	곡률 있는 제약을 선형화하면 위반이 ‖d‖² 만큼 생기는데 ℓ₁ 벌점이 이를 1차로 잰다
결과	초선형·이차 수렴 파괴, 스텝 길이가 계속 잘림
처방	2차 보정(SOC), 워치독/비단조, 필터법, 매끄러운 병합함수
등장 무대	순차 이차계획법, 라인서치 내점법

알고리즘이 정답 쪽으로 정확하게 한 걸음 내디뎠는데, 심판이 “그건 나빠진 거야”라며 물린다. 그것도 해에 가까워질수록 더 확실하게.

마라토스 효과는 제약 최적화의 전역화 장치가 쓰는 병합함수(merit function)가, 해 근방에서 이차 수렴을 만들어 내는 단위 스텝을 거부해 버리는 현상이다. 순차 이차계획법의 QP 가 내놓은 방향 $d_k$ 는 $\|x_k+d_k-x^\star\| = O(\|x_k-x^\star\|^2)$ 로 해에 제곱만큼 다가서는 훌륭한 스텝인데, $\ell_1$ 벌점 병합함수

$$\phi_1(x;\mu) = f(x) + \mu\bigl(\|h(x)\|_1 + \|[g(x)]^+\|_1\bigr)$$

로 재면 $\phi_1(x_k+d_k) > \phi_1(x_k)$ 가 되어 라인서치가 스텝을 잘라 버린다. 잘린 스텝은 더 이상 뉴턴 스텝이 아니므로 초선형 수렴이 통째로 죽고, 반복은 해 바로 앞에서 기어간다.

고약한 것은 이게 알고리즘의 버그도, 수치 오차도, 파라미터 튜닝의 문제도 아니라는 점이다. 정확 벌점 함수의 정의상 불가피한 구조적 결함이고, 그것도 해에 가까울수록 더 잘 나타난다. 벌점 계수 $\mu$ 를 어떻게 잡아도 못 피한다. 이 문서는 그 메커니즘과 표준 처방 셋을 정리한다. SQP 골격 전체는 순차 이차계획법, 정확 벌점 함수의 이론은 벌점법에 있다.

2. 표준 예제

마라토스가 제시한 예제는 2차원이고 손으로 끝까지 계산된다. 최적화 교과서에서 이 예제가 예외 없이 등장하는 이유다.

$$\min_{x\in\mathbb{R}^2}\ f(x) = 2\bigl(x_1^2 + x_2^2 - 1\bigr) - x_1 \qquad \text{s.t.}\qquad c(x) = x_1^2 + x_2^2 - 1 = 0$$

제약은 단위원이고, 원 위에서 $f = -x_1$ 이므로 해는 $x^\star=(1,0)$, 승수는 $\lambda^\star=-3/2$ 다. 반복점이 이미 원 위에 있다고 하자.

$$x_k = (\cos\theta,\ \sin\theta)$$

라그랑지안 헤세는 $\nabla^2 f + \lambda^\star\nabla^2 c = (4 - 3)I = I$ 이므로 QP 부분문제는

$$\min_d\ \tfrac12\|d\|^2 + \nabla f_k^\top d \quad\text{s.t.}\quad x_k^\top d = 0$$

이고, 풀면 깔끔하게 떨어진다.

$$d_k = \bigl(\sin^2\theta,\ -\sin\theta\cos\theta\bigr), \qquad \|d_k\| = |\sin\theta|$$

이제 이 스텝을 세 가지 잣대로 재 보자.

해까지의 거리 — $x_k + d_k - x^\star = (1-\cos\theta)(\cos\theta,\sin\theta)$ 이므로 노름이 $1-\cos\theta$ 다. 한편 $\|x_k - x^\star\| = 2|\sin(\theta/2)|$ 이고 $1-\cos\theta = 2\sin^2(\theta/2)$ 이므로

$$\|x_k + d_k - x^\star\| = \tfrac12\,\|x_k - x^\star\|^2$$

교과서적인 이차 수렴이다. 상수까지 정확히 $1/2$.

제약 위반 — $\|x_k+d_k\|^2 = \|x_k\|^2 + 2x_k^\top d_k + \|d_k\|^2 = 1 + 0 + \sin^2\theta$ 이므로

$$c(x_k) = 0 \ \longrightarrow\ c(x_k+d_k) = \sin^2\theta > 0$$

원 위에 있던 점이 원 밖으로 나갔다.

목적함수 — $f(x_k) = -\cos\theta$, $f(x_k+d_k) = \sin^2\theta - \cos\theta$ 이므로

$$f(x_k+d_k) - f(x_k) = \sin^2\theta > 0$$

목적함수도 늘었다. 따라서 어떤 $\mu \ge 0$ 을 잡아도

$$\phi_1(x_k+d_k;\mu) - \phi_1(x_k;\mu) = (1+\mu)\sin^2\theta \ >\ 0$$

모든 벌점 계수에서 거부된다. 해에 가까워질수록($\theta\to0$) 이 부등식은 여전히 성립하며, 상대적 크기도 줄지 않는다.¹

3. 왜 일어나는가

메커니즘은 결국 차수 계산이다. 해 근방에서 세 양의 크기를 비교해 보자.

• 선형화 오차. QP 는 제약을 1차로만 선형화한다. 제약면이 휘어 있으면 선형화된 제약을 정확히 만족하는 스텝이라도 실제 제약은 곡률만큼 위반한다: $c(x_k+d_k) = O(\|d_k\|^2)$. 예제에서 $\sin^2\theta$ 가 정확히 이것이다.
• 병합함수가 그 위반을 재는 방식. $\ell_1$ 은 위반을 절댓값으로, 즉 1차로 잰다. 그래서 벌점항의 증가는 $\mu\,O(\|d_k\|^2)$ 다.
• 목적함수의 감소량. 해 근방에서는 축소 그래디언트가 이미 작아서 1차 감소가 사라지고, 감소도 $O(\|d_k\|^2)$ 규모에 머문다.

즉 증가하는 벌점항과 감소해야 할 목적함수가 같은 차수다. 어느 쪽이 이길지는 상수가 정하고, 마라토스의 예제는 그 상수가 나쁜 쪽으로 몰릴 수 있음을 보인다. 이게 ”$\mu$ 를 잘 고르면 되는 문제”가 아닌 이유이기도 하다 — $\mu$ 를 키우면 벌점항이 더 커지고, 줄이면 정확 벌점의 조건 $\mu > \|\lambda^\star\|_\infty$ 가 깨져 애초에 해가 병합함수의 최소점이 아니게 된다.

한 가지 더. 이 현상은 비미분 정확 벌점 함수의 성질이다. $\ell_1$ 뿐 아니라 $\ell_\infty$ 정확 벌점에서도 똑같이 나타나고, 라인서치를 쓰는 내점법 구현에서도 나타난다. 반면 매끄러운 병합함수를 쓰면 사정이 달라지는데, 이 이야기는 아래에서 다시 한다.

4. 2차 보정 (SOC)

가장 직접적인 처방이다. 원인이 “선형화가 곡률을 못 따라가서 생긴 $O(\|d\|^2)$ 위반”이라면, 그 위반을 한 번 더 지워 주면 된다. $x_k+d_k$ 에서 제약을 실제로 다시 평가해, 그 잔차를 없애는 최소 노름 보정 $\hat{d}_k$ 를 구한다.

$$A_k \hat{d} + c(x_k + d_k) = 0, \qquad \min\ \|\hat{d}\|$$

($A_k = \nabla c(x_k)^\top$ 는 원래 반복점의 야코비안이다. 인수분해를 재사용할 수 있다는 뜻이며, 이게 SOC 를 싸게 만든다.) 그리고 $x_k + d_k + \hat{d}_k$ 를 시험한다.

앞의 예제로 확인해 보자. $A_k = 2x_k^\top$ 이므로 조건은 $2x_k^\top\hat{d} = -\sin^2\theta$, 최소 노름 해는 $\hat{d}_k = -\frac{\sin^2\theta}{2}x_k$ 다. 이때

$$\|x_k+d_k+\hat{d}_k\|^2 = 1 + \frac{\sin^4\theta}{4} \quad\Longrightarrow\quad c = \frac{\sin^4\theta}{4} = O(\|d_k\|^4)$$

위반이 두 차수 내려갔다. 목적함수도 다시 계산하면 $\theta$ 가 작을 때 대략 $-\frac12\sin^2\theta$ 만큼 감소하므로, 이번에는 병합함수가 줄어들어 단위 스텝이 수용된다. 그리고 $\|\hat{d}_k\| = O(\|d_k\|^2)$ 이므로 보정을 얹어도 원래 스텝의 이차 수렴성은 그대로 남는다. 처방이 병을 정확히 겨냥한 드문 사례다.²

실무 구현의 요령은 이렇다.

• 매번 하지 않는다. 단위 스텝이 거부될 때만 SOC 를 한 번 시도하고, 그래도 안 되면 평범한 백트래킹으로 내려간다. 잘 도는 구간에서 공짜 계산을 하지 않기 위해서다.
• 비용은 제약 평가 한 번 + 같은 행렬로 하는 역대입 한 번. 야코비안을 다시 만들지 않으므로 SQP 한 반복의 몇 퍼센트 수준이다.
• 부등식 제약이 있으면 현재 활성이라 판정된 것들만 보정 대상에 넣는다.

5. 워치독과 비단조 전략

다른 접근은 아예 심판을 잠시 눈감게 하는 것이다. 체임벌린, 파월, 르마레샬, 페데르센(1982)의 워치독(watchdog) 기법은 이렇게 돈다.

1. 현재 점을 기준점으로 기억하고 병합함수 값을 저장한다.
2. 이후 최대 $\bar{t}$ 회(보통 5회 정도) 동안은 단위 스텝을 무조건 받아들인다. 병합함수가 늘어도 상관하지 않는다.
3. $\bar{t}$ 회 안에 기준점 대비 충분한 감소가 확보되면 성공 — 새 기준점을 잡고 계속 간다.
4. 실패하면 기준점으로 되돌아가 정상적인 라인서치를 한 번 수행한다.

마라토스 효과가 “한두 반복만 참으면 지나가는 일시적 현상”이라는 관찰에 기댄 설계다. 되돌아가기가 있어서 전역 수렴도 유지된다. 같은 정신의 일반화가 그리포·람파리엘로·루치디의 비단조 라인서치로, 최근 $M$ 개 반복의 최댓값 대비 감소만 요구한다. 구현이 간단해 널리 쓰이지만, SOC 만큼 확실하지는 않고 $\bar{t}$ 나 $M$ 이라는 튜닝 손잡이가 하나 늘어난다.

6. 필터법

플레처와 레이퍼(2002)의 **필터법**은 문제의 뿌리를 다르게 짚는다. 목적함수와 제약 위반을 하나의 스칼라로 합치는 것 자체가 정보 손실이라는 것이다. 그래서 두 값을 그대로 두 축으로 놓고

$$\theta(x) = \|c(x)\|, \qquad f(x)$$

기존 반복점들 중 어느 것에게도 파레토 지배당하지 않으면 받아들인다. 다목적 최적화의 지배 관계를 수용 판정에 쓰는 셈이다. 장점이 뚜렷하다 — 벌점 계수 $\mu$ 를 튜닝할 필요가 사라지고, ”$f$ 는 나빠졌지만 위반은 크게 줄었다”는 스텝을 자연스럽게 수용한다.

다만 필터가 마라토스 효과를 자동으로 없애 주지는 않는다. 앞의 예제에서 SQP 스텝은 $f$ 와 $\theta$ 를 둘 다 나쁘게 만들므로, 필터도 그대로 거부한다. 그래서 filterSQP 와 라인서치 필터 내점법인 IPOPT 는 필터와 SOC 를 함께 쓴다. 필터는 벌점 계수 튜닝을 없애 주는 장치이지, 곡률 문제의 해답은 아니다. 이 구분을 놓치면 “필터 쓰는데 왜 아직도 스텝이 잘리냐”는 질문을 하게 된다.

7. 매끄러운 병합함수라는 우회로

마지막 갈래는 애초에 꺾이지 않는 병합함수를 쓰는 것이다. 증강 라그랑주형 병합함수

$$\mathcal{M}(x,\lambda;\mu) = f(x) + \lambda^\top c(x) + \frac{\mu}{2}\|c(x)\|_2^2$$

를 보면, 위반을 제곱으로 재기 때문에 $O(\|d\|^2)$ 짜리 위반이 벌점항에서는 $O(\|d\|^4)$ 로 나타난다. 곡률이 만든 위반이 목적함수 변화보다 두 차수 작아지므로 마라토스형 거부가 구조적으로 생기지 않는다. 증강 라그랑주법의 이차항이 여기서도 밥값을 하는 셈이다. SNOPT 가 이 계열의 병합함수를 쓴다.

대가는 승수 $\lambda$ 를 병합함수 안에서 함께 관리해야 한다는 것 — 수용 판정이 $x$ 만의 함수가 아니게 되고, 승수 갱신이 잘못되면 정확성이 깨진다. 플레처의 매끄러운 정확 벌점 함수는 승수를 $x$ 의 명시적 함수로 대입해 이 문제를 피하지만, 그 승수 공식이 매 평가마다 최소제곱 문제를 요구해서 비싸다. “매끄럽게 + 정확하게 + 싸게” 셋 중 둘만 고를 수 있다는 것이 이 절의 요약이다.

8. 진단과 현장 감각

• 증상. 반복 로그에서 KKT 잔차가 $10^{-4}$ 근처까지 잘 내려오다가 갑자기 스텝 길이 $\alpha$ 가 $10^{-1}, 10^{-2}, \dots$ 로 계속 잘리고, 반복 수만 늘면서 잔차는 선형으로 기어간다. 반복점 자체는 이미 해 근처에 있다.
• 구분해야 할 것. 같은 증상이 (1) 기울기가 틀린 경우, (2) 벌점 계수 $\mu$ 가 과하게 큰 경우, (3) 문제가 퇴화된 경우에도 나온다. 마라토스 효과라면 제약이 실제로 곡률을 가지고 있고, SOC 를 켜는 순간 증상이 사라진다. 진단이 곧 처방이라 확인이 쉽다.
• 선형 제약뿐이면 안 생긴다. 제약이 아핀이면 선형화가 정확해서 $c(x_k+d_k)=0$ 이므로 이 현상이 원천적으로 없다. 이차계획법이나 선형 제약 문제에서 마라토스를 걱정할 필요는 없다.
• 솔버 옵션 이름. 대부분의 구현이 second_order_correction, max_soc, watchdog 같은 이름의 옵션으로 노출하고 기본값은 켜져 있다. 튜닝한다고 끄면 정확히 이 현상을 되살리게 된다.

이름값 이야기 하나. 최적화 문헌에서 사람 이름이 붙은 “효과”는 드물고, 대부분은 정리나 알고리즘에 이름이 붙는다. 마라토스는 알고리즘이 아니라 반례로 이름을 남긴 사례다. 그것도 박사논문 한 편으로.³

9. 관련 문서

• 순차 이차계획법 · 벌점법 · 증강 라그랑주법
• 라인서치 · 울프 조건 · 신뢰 영역 방법
• 카루시-쿤-터커 조건 · 라그랑주 승수법 · 활성집합법
• 내점법 · 이차계획법 · 준-뉴턴법
• 수렴성 · 헤세 행렬 · 최적설계
• 필터법 · 비평활 최적화 · 약볼록 함수 · 반평활 뉴턴법

10. Footnotes

1. 자주 오해되는 지점이 있어 못 박아 둔다. “스텝이 목적함수와 제약을 둘 다 개선하는데도 병합함수가 늘어난다”는 설명은 틀렸다 — 그랬다면 $\phi_1$ 은 반드시 줄어든다. 실제로 벌어지는 일은 $f$ 도 늘고 위반도 늘지만 해까지의 거리는 제곱으로 줄어드는 것이다. 병합함수가 재는 것과 우리가 원하는 것이 다르다는 게 이 현상의 전부다. ↩

2. SOC 는 콜먼과 콘, 플레처, 메인과 폴락 등 여러 갈래에서 1980년대 초에 거의 동시에 등장했다. “곡선 제약을 따라 한 번 되돌려 놓는다”는 발상이 워낙 자연스러워서, 누구 것이라 하기 애매한 대표적 사례다. ↩

3. 심지어 “마라톤”과는 아무 관계가 없다. 그리스계 이름이라 철자가 겹칠 뿐인데, 처음 배울 때 “스텝이 짧아져서 마라톤처럼 오래 걸린다는 뜻인가” 하고 넘어간 사람이 이 바닥에 한둘이 아니다. 우연이 지나치게 잘 맞아떨어진 작명. ↩