반평활 뉴턴법

오류 제보
수치해석 최적설계 마지막 수정: 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년 앞선다. 구조해석 쪽에서는 “이렇게 하면 수렴이 빨라지더라”로 먼저 정착했고, 최적화 쪽에서 나중에 “그게 왜 되는지”를 증명한 것이다. 공학이 수학을 앞지르는 일은 생각보다 자주 있다. ↩

이 문서가 문제를 푸는 데 도움이 됐나요? 한 번의 클릭이 다음 검수 순서를 정합니다.

의견을 반영할게요. 감사합니다.

다음으로 읽기 뉴턴-랩슨법 약 5분 더 탐색 →