Linearism › 최적화 › OP.4

4장. 뉴턴 방법과 준뉴턴 방법

최적화 · 2부. 반복 알고리즘

심화 · 약 15분 · 연습문제 5

요약

이차 근사와 뉴턴 단계, 이차 수렴, 감쇠 뉴턴 방법, 계산 비용, BFGS와 L-BFGS, 가우스–뉴턴 방법

경사하강법은 기울기만 보고 내려가므로, 길쭉한 골짜기에서는 지그재그로 느려집니다. 뉴턴 방법은 곡률(헤세 행렬)까지 보고 “이 그릇의 바닥은 저기”라고 한 번에 뛰어갑니다. 최솟값 근처에서는 맞는 자릿수가 매번 두 배가 될 만큼 빠르지만, 헤세 행렬을 계산하고 역행렬을 구하는 비용이 큽니다. 그 사이를 메우는 것이 BFGS 같은 준뉴턴 방법입니다.

4.1 뉴턴 단계

현재 점 xk\mathbf x_k에서 ff를 이차함수로 근사합니다(테일러 전개).

f(xk+d)≈f(xk)+∇f⊤d+12d⊤Hd,H=∇2f(xk).f(\mathbf x_k + \mathbf d) \approx f(\mathbf x_k) + \nabla f^\top\mathbf d + \frac12\mathbf d^\top H\mathbf d, \qquad H = \nabla^2f(\mathbf x_k).

HH가 양의 정부호이면 이 이차함수의 최솟값은 2장 정리 2.5에 따라 d=−H−1∇f\mathbf d = -H^{-1}\nabla f입니다.

정의 4.1 (뉴턴 방법). xk+1=xk−[∇2f(xk)]−1∇f(xk)\mathbf x_{k+1} = \mathbf x_k - [\nabla^2f(\mathbf x_k)]^{-1}\nabla f(\mathbf x_k).

실제로는 역행렬을 구하지 않고 연립방정식 Hd=−∇fH\mathbf d = -\nabla f를 풉니다.

예제 4.2. 이차함수 f=12x⊤Ax−b⊤xf = \frac12\mathbf x^\top A\mathbf x - \mathbf b^\top\mathbf x에서는 근사가 정확하므로, 어디서 시작하든 뉴턴 방법은 한 번에 A−1bA^{-1}\mathbf b에 도착합니다. 조건수가 아무리 커도 상관없습니다. 뉴턴 방법은 좌표를 바꿔 그릇을 동그랗게 만든 뒤 경사하강법을 하는 것과 같습니다.

예제 4.3 (일변수). x\mathbf x가 수 하나이면 xk+1=xk−f′(xk)/f′′(xk)x_{k+1} = x_k - f'(x_k)/f''(x_k). 이것은 방정식 f′(x)=0f'(x) = 0에 대한 뉴턴–랩슨 방법(미적분학)입니다.

4.2 이차 수렴

정리 4.4. ∇2f\nabla^2f가 최솟값 x∗\mathbf x^*에서 양의 정부호이고 립시츠 연속이면, x0\mathbf x_0가 충분히 가까울 때 상수 CC가 있어

∥xk+1−x∗∥≤C∥xk−x∗∥2.\|\mathbf x_{k+1} - \mathbf x^*\| \le C\|\mathbf x_k - \mathbf x^*\|^2.

이를 이차 수렴(quadratic convergence)이라 합니다. 오차가 10−210^{-2}이면 다음은 약 10−410^{-4}, 그다음은 10−810^{-8}입니다. 맞는 자릿수가 매번 두 배가 됩니다.

예제 4.5. f(x)=x−ln⁡xf(x) = x - \ln x(x>0x > 0, 최솟값 x∗=1x^* = 1). f′=1−1/xf' = 1 - 1/x, f′′=1/x2f'' = 1/x^2이므로 xk+1=xk−(1−1/xk)xk2=2xk−xk2x_{k+1} = x_k - (1 - 1/x_k)x_k^2 = 2x_k - x_k^2입니다. 오차 ek=xk−1e_k = x_k - 1로 쓰면 ek+1=−ek2e_{k+1} = -e_k^2. x0=0.5x_0 = 0.5이면 x1=0.75x_1 = 0.75, x2=0.9375x_2 = 0.9375, x3≈0.99609x_3 \approx 0.99609, x4≈0.99998x_4 \approx 0.99998입니다.

4.3 한계와 감쇠 뉴턴 방법

  • 멀리서는 발산할 수 있습니다. 예제 4.5에서 x0=3x_0 = 3이면 x1=−3x_1 = -3으로 정의역을 벗어납니다. 그래서 xk+1=xk+td\mathbf x_{k+1} = \mathbf x_k + t\mathbf d에서 tt를 3장의 직선 탐색으로 고르는 감쇠 뉴턴 방법(damped Newton)을 씁니다.
  • HH가 양의 정부호가 아니면 뉴턴 방향이 오르막이거나 안장점으로 끌려갑니다. 볼록이 아닌 문제에서는 H+μIH + \mu I처럼 고쳐 씁니다(레벤버그–마쿼트 방법의 생각).
  • 비용. 변수가 nn개이면 헤세 행렬은 n2n^2개 원소, 연립방정식 풀이는 약 n3n^3번의 연산입니다. 매개변수가 10910^9개인 신경망에서는 불가능합니다.

4.4 준뉴턴 방법

헤세 행렬을 직접 계산하지 않고, 그래디언트의 변화로부터 그 근사를 차츰 만들어 갑니다.

sk=xk+1−xk\mathbf s_k = \mathbf x_{k+1} - \mathbf x_k, yk=∇f(xk+1)−∇f(xk)\mathbf y_k = \nabla f(\mathbf x_{k+1}) - \nabla f(\mathbf x_k)라 하면, 이차함수에서는 yk=Hsk\mathbf y_k = H\mathbf s_k입니다. 그래서 근사 Bk+1B_{k+1}이 할선 조건(secant condition) Bk+1sk=ykB_{k+1}\mathbf s_k = \mathbf y_k를 만족하도록 고칩니다.

  • BFGS: 할선 조건을 만족하면서 BkB_k에서 가장 적게 바뀌는(순위 2 수정) 공식. 매 단계 비용 n2n^2.
  • L-BFGS: 최근 mm개(보통 5–20)의 (sk,yk)(\mathbf s_k, \mathbf y_k)만 저장해 행렬 없이 방향을 계산합니다. 비용 mnmn으로, 변수 수백만 개에서도 쓰입니다.

일변수에서 할선 조건은 f′′(xk+1)≈f′(xk+1)−f′(xk)xk+1−xkf''(x_{k+1}) \approx \frac{f'(x_{k+1}) - f'(x_k)}{x_{k+1} - x_k}, 곧 미분을 할선의 기울기로 바꾼 것입니다.

4.5 가우스–뉴턴 방법

최소제곱 f(θ)=12∑iri(θ)2f(\boldsymbol\theta) = \frac12\sum_ir_i(\boldsymbol\theta)^2에서 JJ를 잔차 rir_i의 야코비 행렬이라 하면 ∇f=J⊤r\nabla f = J^\top\mathbf r, ∇2f=J⊤J+∑iri∇2ri\nabla^2f = J^\top J + \sum_ir_i\nabla^2r_i입니다. 둘째 항(잔차가 작으면 작음)을 버리면

θk+1=θk−(J⊤J)−1J⊤r,\boldsymbol\theta_{k+1} = \boldsymbol\theta_k - (J^\top J)^{-1}J^\top\mathbf r,

이 가우스–뉴턴 방법(Gauss–Newton)입니다. 2계 도함수 없이 뉴턴 방법에 가까운 속도를 냅니다. 곡선 맞춤, GPS 위치 계산, 컴퓨터 비전의 번들 조정이 이 방법과 그 감쇠판인 레벤버그–마쿼트 방법(Levenberg-Marquardt algorithm)을 씁니다.

4.6 이 장의 요약

  • 뉴턴 단계 −H−1∇f-H^{-1}\nabla f: 이차 근사의 최솟값으로 뜁니다. 이차함수는 한 번에.
  • 최솟값 근처에서 이차 수렴(자릿수가 두 배씩). 멀리서는 감쇠가 필요합니다.
  • 비용 n3n^3이 문제 → BFGS, L-BFGS(할선 조건), 가우스–뉴턴(J⊤JJ^\top J).

쓰이는 곳. 과학 계산 라이브러리의 기본 최적화기(SciPy의 BFGS, L-BFGS-B), 통계 소프트웨어의 로지스틱 회귀 적합(뉴턴 방법 = IRLS), 딥러닝의 2차 방법 연구(K-FAC, Shampoo, 자연 경사법), 로봇공학·비전의 비선형 최소제곱, 회로 시뮬레이터의 비선형 방정식 풀이가 이 장의 방법입니다.

문제

4.1 [계산] · 확인 문제

f(x)=x4f(x) = x^4의 최솟값을 뉴턴 방법으로 찾습니다. x0=3x_0 = 3이면 x1x_1은?

정답
2
풀이

f′=4x3f' = 4x^3, f′′=12x2f'' = 12x^2이므로 x1=x0−4x0312x02=23x0=2x_1 = x_0 - \frac{4x_0^3}{12x_0^2} = \frac23x_0 = 2입니다. 최솟값에서 f′′=0f'' = 0이라 이차 수렴이 아니라 매번 23\frac23배로 줄어드는 선형 수렴입니다.

4.2 [계산] · 확인 문제

f(x,y)=x2+4y2−2x−8yf(x, y) = x^2 + 4y^2 - 2x - 8y에서 (0,0)(0, 0)을 출발해 뉴턴 단계를 한 번 하면 도착하는 점은?

좌표 값
xx [?]
yy [?]
정답
1
1
풀이

∇f(0,0)=(−2,−8)\nabla f(0, 0) = (-2, -8), H=diag(2,8)H = \mathrm{diag}(2, 8)이므로 d=−H−1∇f=(1,1)\mathbf d = -H^{-1}\nabla f = (1, 1)입니다. 이차함수라 이것이 바로 최솟값입니다.

4.3 [계산] · 확인 문제

예제 4.5의 반복 xk+1=2xk−xk2x_{k+1} = 2x_k - x_k^2을 x0=0.8x_0 = 0.8에서 시작할 때 x3x_3은? (소수 여덟째 자리까지)

정답
0.99999744
풀이

x1=0.96x_1 = 0.96, x2=0.9984x_2 = 0.9984, x3=0.99999744x_3 = 0.99999744. 오차는 0.2→0.04→0.0016→0.000002560.2 \to 0.04 \to 0.0016 \to 0.00000256으로 매번 제곱됩니다.

4.4 [계산] · 확인 문제

변수가 n=1000n = 1000개일 때, L-BFGS가 m=10m = 10쌍을 저장하는 데 필요한 수의 개수(2mn2mn)를 헤세 행렬 원소 수 n2n^2으로 나눈 값은?

정답
0.02
풀이

2⋅10⋅1000/106=0.022\cdot10\cdot1000/10^6 = 0.02, 곧 2%입니다.

4.5 [증명]

이차함수 f(x)=12x⊤Ax−b⊤xf(\mathbf x) = \frac12\mathbf x^\top A\mathbf x - \mathbf b^\top\mathbf x(AA 양의 정부호)에서 뉴턴 방법이 어느 점에서 시작하든 한 번에 최솟값에 도착함을 보입니다.

풀이

∇f(x0)=Ax0−b\nabla f(\mathbf x_0) = A\mathbf x_0 - \mathbf b, H=AH = A이므로 x1=x0−A−1(Ax0−b)=A−1b\mathbf x_1 = \mathbf x_0 - A^{-1}(A\mathbf x_0 - \mathbf b) = A^{-1}\mathbf b이고, 이것은 2장 정리 2.5의 최솟값입니다.