마라토스 효과

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