반평활 뉴턴법

편집 역사 토론
수치해석 최적설계 마지막 수정: 2026-08-14 04:27:53

1. 개요[편집]

반평활 뉴턴법
Semismooth Newton Method
대상국소 립시츠지만 미분 불가능한 F(x) = 0
반복식xk+1 = xk − Vk−1F(xk), Vk ∈ ∂F(xk)
도함수 대용클라크 일반화 야코비안
수렴반평활 + CD-정칙 → 초선형 / 강반평활 → 이차
이론Mifflin (1977), Qi–Sun (1993)
주 무대상보성 문제, 변분부등식, 접촉·소성, 상자 제약 최적제어

미분이 안 되는 함수에 뉴턴법을 쓰겠다는 말은 처음 들으면 무모하게 들린다. 그런데 최적화가 만들어 내는 비평활함수는 대부분 “꺾여 있을 뿐 조각조각은 매끄러운” 얌전한 부류다.

반평활 뉴턴법(semismooth Newton method)은 미분 불가능하지만 반평활(semismooth)한 국소 립시츠 함수의 근을 구하기 위해, 야코비안 자리에 클라크 일반화 야코비안의 한 원소를 대입해 뉴턴 반복을 그대로 수행하는 방법이다.

Vk∈∂F(xk),Vkdk=−F(xk),xk+1=xk+dkV_k \in \partial F(x^k), \qquad V_k d^k = -F(x^k), \qquad x^{k+1} = x^k + d^k

보다시피 겉모습은 뉴턴-랩슨법과 글자 하나 다르지 않다. 놀라운 것은 결과다 — 적절한 조건에서 국소 초선형 수렴이 그대로 살아남고, 함수가 강반평활이면 이차 수렴까지 나온다. 매끄럽지 않은데도.

이 방법이 중요한 이유는 응용의 폭이다. 부등식 제약이 만드는 카루시-쿤-터커 조건의 상보성 부분, 변분부등식, 접촉과 소성의 활성/비활성 전환 — 이 바닥에서 “조건에 따라 갈라지는” 모든 것은 min⁡\min, max⁡\max, 절댓값, 사영 같은 조각별 매끄러운 함수로 쓸 수 있고, 이들이 전부 강반평활이다. 즉 부등식 제약을 등식 하나로 압축해 뉴턴으로 때리는 길이 열린다.

2. 클라크 일반화 야코비안[편집]

F:Rn→RnF : \mathbb{R}^n \to \mathbb{R}^n 이 국소 립시츠라 하자. 라데마허 정리에 의해 FF 는 거의 모든 점에서 미분 가능하다(미분 불가능한 점들의 르베그 측도가 0). 미분 가능한 점들의 집합을 DFD_F 라 할 때,

∂BF(x)={lim⁡j→∞∇F(xj) : xj→x, xj∈DF},∂F(x)=conv ∂BF(x)\partial_B F(x) = \Bigl\{ \lim_{j\to\infty} \nabla F(x^j) \ :\ x^j \to x,\ x^j \in D_F \Bigr\}, \qquad \partial F(x) = \mathrm{conv}\, \partial_B F(x)

∂BF\partial_B F 를 B-미분(Bouligand), 그 볼록껍질 ∂F\partial F 를 클라크 일반화 야코비안이라 한다. 매끄러운 점에서는 ∂F(x)={∇F(x)}\partial F(x) = \{\nabla F(x)\} 로 한 점이고, 꺾인 점에서만 집합으로 부푼다.

가장 짧은 예가 φ(t)=∣t∣\varphi(t)=|t| 다. ∂φ(0)=[−1,1]\partial\varphi(0) = [-1,1], 그 밖에서는 {sign(t)}\{\mathrm{sign}(t)\}. min⁡(a,b)\min(a,b) 라면 a<ba<b 에서 (1,0)(1,0), a>ba>b 에서 (0,1)(0,1), a=ba=b 에서 두 점을 잇는 선분 전체다.

여기서 실무적으로 중요한 사실 하나. 알고리즘은 ∂F\partial F 전체를 계산할 필요가 없다. 필요한 것은 그 안의 원소 하나뿐이고, 꺾인 점에 정확히 착지할 확률은 부동소수점 세계에서도 사실상 0이라, 구현은 “조건 분기로 어느 조각인지 판정해 그 조각의 야코비안을 쓴다”가 전부다. 코드 상으로는 그냥 if (a < b) ... else ...다.

3. 반평활성 — 뉴턴이 살아남는 조건[편집]

일반화 야코비안이 존재한다고 뉴턴이 되는 건 아니다. 뉴턴법의 국소 수렴 증명은 ”F(x+d)−F(x)−VdF(x+d) - F(x) - Vd 가 ∥d∥\|d\| 보다 빨리 작아진다”는 근사 성질에 전적으로 기댄다. 이 성질을 비평활 세계로 옮긴 것이 반평활성이다.

FF 가 xx 에서 반평활이라는 것은 국소 립시츠이고 방향미분이 존재하며

sup⁡V∈∂F(x+d)∥F(x+d)−F(x)−Vd∥=o(∥d∥)(d→0)\sup_{V \in \partial F(x+d)} \bigl\| F(x+d) - F(x) - V d \bigr\| = o(\|d\|) \quad (d \to 0)

가 성립한다는 뜻이다. 우변이 O(∥d∥1+p)O(\|d\|^{1+p}) (0<p≤10<p\le1)이면 pp차 반평활, 특히 p=1p=1 이면 강반평활이라 한다. 정의에서 VV 를 xx 가 아니라 x+dx+d 에서 뽑는다는 점이 핵심이다 — “지금 서 있는 곳의 기울기”가 아니라 “옮겨 갈 곳의 기울기”가 근사를 보장해야 한다.

다행히 실무에서 만나는 함수는 거의 다 여기 들어온다.

  • 조각별 매끄러운(PC¹) 함수는 전부 반평활. 조각이 아핀이면 강반평활.
  • min⁡\min, max⁡\max, ∣⋅∣|\cdot|, 양수부 (⋅)+(\cdot)^+, 다면체 위로의 사영 ΠK\Pi_K — 전부 강반평활.
  • 반평활 함수의 합·곱·합성은 반평활. 즉 조립해도 성질이 보존된다.
  • 매끄러운 함수는 당연히 반평활(정의가 테일러 전개로 환원된다).

밀플린(1977)이 범함수에 대해 반평활 개념을 도입했고, 치(Qi)와 순(Sun)이 1993년에 이것을 뉴턴법의 수렴 조건으로 정리하면서 알고리즘으로서의 반평활 뉴턴이 성립했다.1

4. 수렴 정리[편집]

F(x⋆)=0F(x^\star)=0 이고 FF 가 x⋆x^\star 에서 반평활이며, ∂F(x⋆)\partial F(x^\star) 의 모든 원소가 정칙(비특이)이라고 하자. 이 조건을 CD-정칙성이라 부른다. 그러면 x⋆x^\star 의 어떤 근방에서 시작한 반복이 x⋆x^\star 로 초선형 수렴한다. FF 가 강반평활이면 이차 수렴한다.

∥xk+1−x⋆∥=o(∥xk−x⋆∥)또는O(∥xk−x⋆∥2)\|x^{k+1}-x^\star\| = o(\|x^k - x^\star\|) \quad\text{또는}\quad O(\|x^k-x^\star\|^2)

증명의 구조는 매끄러운 뉴턴과 판박이다. xk+1−x⋆=Vk−1[F(x⋆)−F(xk)−Vk(x⋆−xk)]x^{k+1}-x^\star = V_k^{-1}\bigl[F(x^\star) - F(x^k) - V_k(x^\star - x^k)\bigr] 로 쓰고, 대괄호 안을 반평활성으로 o(∥xk−x⋆∥)o(\|x^k-x^\star\|) 로 누른 뒤, Vk−1V_k^{-1} 의 유계성을 CD-정칙성으로 확보하면 끝난다. 정리 하나 때문에 정의가 그렇게 생긴 것이라고 보면 정확하다.

주의할 것은 CD-정칙성이 “야코비안 하나가 정칙”이 아니라 “집합의 모든 원소가 정칙”이라는 점이다. 꺾인 점 위에서는 ∂F\partial F 가 통째로 부풀어 있으므로 이 조건이 매끄러운 경우보다 훨씬 강하고, 실제로 이것이 깨져 수렴이 죽는 사례가 퇴화된 상보성 문제(엄격 상보성이 성립하지 않는 지점)에서 나온다.

5. KKT·상보성의 재정식화[편집]

이 방법이 진짜 힘을 쓰는 자리다. NCP 조건

a≥0,b≥0,ab=0a \ge 0, \qquad b \ge 0, \qquad ab = 0

을 하나의 등식 φ(a,b)=0\varphi(a,b)=0 으로 바꿔 주는 함수를 NCP-함수라 한다. 대표가 둘이다.

φmin⁡(a,b)=min⁡(a,b),φFB(a,b)=a2+b2−a−b\varphi_{\min}(a,b) = \min(a,b), \qquad \varphi_{\mathrm{FB}}(a,b) = \sqrt{a^2+b^2} - a - b

둘 다 φ=0  ⟺  \varphi=0 \iff 위의 세 조건과 동치이고, 둘 다 강반평활이다. 뒤쪽이 피셔-부르마이스터 함수로, (0,0)(0,0) 한 점을 빼면 매끄럽다는 것이 장점이다. NCP x≥0, F(x)≥0, x⊤F(x)=0x\ge0,\ F(x)\ge0,\ x^\top F(x)=0 는 성분별로 Φi(x)=φ(xi,Fi(x))\Phi_i(x) = \varphi(x_i, F_i(x)) 를 쌓아 Φ(x)=0\Phi(x)=0 이 되고, 여기에 반평활 뉴턴을 돌리면 된다. 부등식이 사라지고 정사각 비선형계 하나만 남는다.

FB 함수의 일반화 야코비안은 손으로 쓸 수 있다. (xi,Fi)≠(0,0)(x_i,F_i)\ne(0,0) 인 지표에서

∂Φi∂x=(xixi2+Fi2−1)⏟aiei⊤+(Fixi2+Fi2−1)⏟bi∇Fi(x)⊤\frac{\partial \Phi_i}{\partial x} = \underbrace{\Bigl(\tfrac{x_i}{\sqrt{x_i^2+F_i^2}} - 1\Bigr)}_{a_i} e_i^\top + \underbrace{\Bigl(\tfrac{F_i}{\sqrt{x_i^2+F_i^2}} - 1\Bigr)}_{b_i} \nabla F_i(x)^\top

즉 V=Da+Db ∇F(x)V = D_a + D_b\,\nabla F(x) — 대각행렬 두 개와 원래 야코비안의 조합이다. 매끄러운 문제의 야코비안 코드를 그대로 재사용할 수 있다는 뜻이며, 이게 구현 난이도를 결정적으로 낮춘다.

min⁡\min-함수 쪽에는 더 예쁜 해석이 붙는다. 상자 제약 문제의 KKT 를 min⁡\min-함수로 쓰고 반평활 뉴턴을 돌리면, 매 반복의 선형계가 “이번 반복에서 활성이라 판정된 성분은 경계값으로 고정, 나머지는 자유”라는 구조를 갖는다. 힌터뮐러·이토·쿠니슈(2002)가 보인 대로 원시-쌍대 활성집합법이 곧 min⁡\min-함수에 대한 반평활 뉴턴법이다.2 활성집합법의 조합적 갱신 규칙이 사실은 뉴턴 반복이었다는 이야기다.

6. 비평활 선형계 풀기[편집]

매 반복 Vkd=−Φ(xk)V_k d = -\Phi(x^k) 를 푸는데, 이 VkV_k 는 성분마다 다른 조각의 야코비안이 섞여 있어 겉보기에는 이상해 보인다. 실제로는 구조가 좋다.

  • 활성/비활성 블록. 지표 집합을 활성 A\mathcal{A} 와 비활성 I\mathcal{I} 로 나누면 VkV_k 는 A\mathcal{A} 행에서는 거의 단위행렬, I\mathcal{I} 행에서는 원래 야코비안이다. A\mathcal{A} 를 소거하면 크기가 ∣I∣|\mathcal{I}| 인 축소계가 남고, 그 축소계는 원래 문제의 부분행렬이라 희소성과 대칭성이 그대로 유지된다.
  • 대칭성 회복. 그냥 쓰면 Da+Db∇FD_a + D_b \nabla F 가 비대칭이지만, DbD_b 가 가역인 행에서 Db−1D_b^{-1} 을 곱해 스케일링하면 대칭 부분이 되살아나 켤레기울기·직접 촐레스키를 쓸 수 있다. 대형 문제에서는 이 사소한 스케일링이 반복당 비용을 몇 배 가른다.
  • 크릴로프 + 야코비안 프리. 대규모에서는 VkV_k 를 조립하지 않고 VkvV_k v 곱만 제공해 GMRES로 부정확 뉴턴을 돌린다. 안쪽 허용오차를 ∥Φ(xk)∥\|\Phi(x^k)\| 에 비례해 줄이면 초선형 수렴이 보존된다.
  • 정칙화. CD-정칙성이 의심스러운 퇴화 문제에서는 Vk+ϵkIV_k + \epsilon_k I 로 살짝 밀어 준다. 레벤버그-마쿼트 방법의 비평활 판본에 해당하며, 국소 오차 한계 조건만 있으면 정칙성 없이도 초선형 수렴이 나온다.

7. 전역화 — 어디서 시작해도 되게 만들기[편집]

뉴턴법이 늘 그렇듯 국소 수렴만 보장되므로 전역화 장치가 필요하다. 여기서 FB 함수의 진짜 장점이 나온다. 병합함수

Ψ(x)=12∥ΦFB(x)∥2\Psi(x) = \tfrac12 \|\Phi_{\mathrm{FB}}(x)\|^2

는 ΦFB\Phi_{\mathrm{FB}} 자체가 비평활인데도 어디서나 연속 미분 가능하고, ∇Ψ(x)=V⊤Φ(x)\nabla\Psi(x) = V^\top \Phi(x) 가 임의의 V∈∂Φ(x)V\in\partial\Phi(x) 에 대해 성립한다. 제곱이 (0,0)(0,0) 의 뾰족함을 정확히 상쇄해 주기 때문이다. 그래서 매끄러운 라인서치를 그대로 얹을 수 있고, “뉴턴 방향이 Ψ\Psi 의 하강 방향이 아니면 −∇Ψ-\nabla\Psi 로 갈아탄다”는 표준 안전장치도 통한다.

한 가지 함정은 Ψ\Psi 의 정류점이 해가 아닐 수 있다는 것이다. ∇Ψ(x)=V⊤Φ(x)=0\nabla\Psi(x)=V^\top\Phi(x)=0 인데 Φ(x)≠0\Phi(x)\ne0 이면 VV 가 특이한 것이고, 라인서치는 거기 갇힌다. 이 경우를 배제하는 조건이 FF 의 야코비안에 대한 P₀-행렬성 같은 구조 가정이며, NCP 가 단조(FF 가 단조)이면 자동으로 만족된다. 뒤집어 말하면 비단조 NCP 에서 솔버가 “수렴했다”고 뱉은 점은 반드시 잔차를 다시 확인해야 한다.

8. 응용[편집]

  • 변분부등식 / 상보성. 사영 기반 1차법은 선형 수렴에 머물지만, 반평활 뉴턴은 초선형으로 마무리한다. 다면체 KK 위의 VI 는 정규 사상 F(ΠK(z))+z−ΠK(z)=0F(\Pi_K(z)) + z - \Pi_K(z) = 0 으로 쓰면 ΠK\Pi_K 가 조각별 아핀이라 강반평활이고, 그대로 뉴턴이 먹는다.
  • 접촉·마찰. 접촉 해석의 시뇨리니 조건을 FB 나 min⁡\min 으로 압축하면 증강 라그랑주법의 바깥 반복 없이 뉴턴 한 겹으로 끝난다. 상용 코드가 “접촉 반복”과 “평형 반복”을 분리하지 않고 한 번에 도는 구현이 이쪽 계열이다.
  • 탄소성. 탄소성 해석의 응력 갱신(리턴 매핑)은 항복면 안/밖으로 갈라지는 조각별 매끄러운 사상이다. 여기서 쓰는 일관 접선 강성(consistent tangent)은 사실 그 사상의 일반화 야코비안 원소이고, 그래서 일관 접선을 쓴 뉴턴 반복이 그렇게 잘 도는 것이다. 반평활 뉴턴을 몰랐던 시절부터 구조해석은 이 방법을 쓰고 있었던 셈이다.3
  • 상자 제약 최적제어와 영상복원. L2L^2 벌점 + 상자 제약 최적제어, 전변분 잡음제거의 쌍대 문제 등이 원시-쌍대 활성집합/반평활 뉴턴의 표준 벤치마크다. 함수공간에서 반복을 정의할 수 있으면 격자를 조밀하게 해도 반복 횟수가 늘지 않는 격자 독립성이 나오는데, 이것이 이 방법을 PDE 제약 최적화의 주류로 만든 이유다.

마지막 항목에는 무한차원 특유의 미묘함이 하나 붙는다. max⁡(0,⋅)\max(0,\cdot) 를 Lp→LqL^p \to L^q 사이의 사상으로 볼 때, p>qp>q 인 노름 격차(norm gap)가 있어야만 뉴턴 미분 가능하다. 같은 공간 안에서는 성립하지 않는다. 이론을 유한차원 감각으로 옮기다 이 조건을 빠뜨리면, 격자를 줄일수록 반복 횟수가 늘어나는 광경을 보게 된다.

9. 관련 문서[편집]

10. Footnotes[편집]

  1. Mifflin, R. (1977). “Semismooth and semiconvex functions in constrained optimization”, SIAM J. Control Optim. 15(6). / Qi, L. & Sun, J. (1993). “A nonsmooth version of Newton’s method”, Math. Programming 58. 제목이 “뉴턴법의 비평활 버전”이라니 요즘 기준으로는 너무 정직해서 인용이 안 될 것 같은 작명인데, 실제로는 이 분야에서 가장 많이 인용되는 논문 중 하나가 됐다. ↩

  2. Hintermüller, M., Ito, K., Kunisch, K. (2002). “The primal-dual active set strategy as a semismooth Newton method”, SIAM J. Optim. 13(3). 논문 제목이 곧 결론이라 초록을 안 읽어도 되는 드문 사례. 덕분에 “활성집합법은 조합적이라 수렴률을 말할 수 없다”는 오래된 통념이 깨졌다. ↩

  3. 시몬(Simo)과 테일러(Taylor)의 1985년 일관 접선 논문이 반평활 뉴턴 이론보다 8년 앞선다. 구조해석 쪽에서는 “이렇게 하면 수렴이 빨라지더라”로 먼저 정착했고, 최적화 쪽에서 나중에 “그게 왜 되는지”를 증명한 것이다. 공학이 수학을 앞지르는 일은 생각보다 자주 있다. ↩