7.93 뉴턴 방법의 원리와 이차 수렴성

1. 기본 원리

뉴턴 방법(Newton’s method)은 목적 함수의 2차 테일러 근사를 반복적으로 최소화하여 최적점을 찾는 2차 최적화 알고리즘이다. 현재 점 \mathbf{x}_k에서 f를 2차까지 전개하면 다음의 이차 모델을 얻는다.

m_k(\mathbf{d}) = f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T\mathbf{d} + \frac{1}{2}\mathbf{d}^T\nabla^2 f(\mathbf{x}_k)\mathbf{d}

이 이차 모델을 \mathbf{d}에 대해 최소화하면 뉴턴 방향(Newton direction) \mathbf{d}_k^N을 얻는다.

\nabla^2 f(\mathbf{x}_k) \mathbf{d}_k^N = -\nabla f(\mathbf{x}_k)

\mathbf{d}_k^N = -[\nabla^2 f(\mathbf{x}_k)]^{-1}\nabla f(\mathbf{x}_k)

뉴턴 갱신은 다음과 같다.

\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{d}_k^N = \mathbf{x}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1}\nabla f(\mathbf{x}_k)

2. 뉴턴 방향의 성질

\nabla^2 f(\mathbf{x}_k) \succ 0일 때, 뉴턴 방향은 하강 방향이다.

\nabla f(\mathbf{x}_k)^T \mathbf{d}_k^N = -\nabla f(\mathbf{x}_k)^T[\nabla^2 f(\mathbf{x}_k)]^{-1}\nabla f(\mathbf{x}_k) < 0

뉴턴 방향은 경사 하강 방향과 달리 헤시안에 의한 곡률 정보를 반영하여, 등고선의 형상에 맞추어 최적점을 향한 보다 직접적인 경로를 산출한다. 이차 함수에서는 단 한 번의 뉴턴 스텝으로 정확한 최적해에 도달한다.

3. 아핀 불변성

뉴턴 방법은 아핀 좌표 변환에 대해 불변(invariant)이다. \mathbf{x} = \mathbf{T}\mathbf{y}로 변수 치환하면, \mathbf{y} 공간에서의 뉴턴 스텝은 \mathbf{x} 공간에서의 뉴턴 스텝과 동일한 결과를 산출한다. 이는 경사 하강법이 좌표계에 의존하는 것과 대비되는 중요한 성질로, 파라미터 스케일링에 대한 강건성을 부여한다.

4. 이차 수렴 정리

뉴턴 방법의 가장 중요한 이론적 성질은 최적해 근방에서의 이차 수렴(quadratic convergence)이다.

정리: f가 두 번 연속 미분 가능하고, \nabla^2 f가 리프시츠 연속이며, \mathbf{x}^*가 \nabla f(\mathbf{x}^*) = \mathbf{0}이고 \nabla^2 f(\mathbf{x}^*) \succ 0인 점이면, \mathbf{x}_0가 \mathbf{x}^*에 충분히 가까울 때 뉴턴 반복열은 \mathbf{x}^*에 이차 수렴한다.

\lVert \mathbf{x}_{k+1} - \mathbf{x}^* \rVert \leq C \lVert \mathbf{x}_k - \mathbf{x}^* \rVert^2

여기서 C > 0은 상수이다. 이차 수렴은 유효 자릿수가 매 반복마다 두 배씩 증가함을 의미하며, 최적해 근방에서의 수렴이 극히 빠르다. 예를 들어, \lVert \mathbf{x}_k - \mathbf{x}^* \rVert = 10^{-3}이면 다음 반복에서 \lVert \mathbf{x}_{k+1} - \mathbf{x}^* \rVert \approx 10^{-6}, 그 다음에는 \approx 10^{-12}가 된다.

증명 개요: 뉴턴 갱신을 오차 \mathbf{e}_k = \mathbf{x}_k - \mathbf{x}^*로 표현하면 다음을 얻는다.

\mathbf{e}_{k+1} = \mathbf{e}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1}\nabla f(\mathbf{x}_k)

\nabla f(\mathbf{x}^*) = \mathbf{0}과 평균값 정리를 적용하면 \nabla f(\mathbf{x}_k) = \int_0^1 \nabla^2 f(\mathbf{x}^* + t\mathbf{e}_k) \, dt \cdot \mathbf{e}_k이다. \nabla^2 f의 리프시츠 연속성에 의해 \nabla^2 f(\mathbf{x}_k)와 적분의 차이가 O(\lVert \mathbf{e}_k \rVert)이므로, \lVert \mathbf{e}_{k+1} \rVert = O(\lVert \mathbf{e}_k \rVert^2)가 성립한다.

5. 수렴 영역의 제한

이차 수렴은 초기점이 최적해에 충분히 가까울 때만 보장되며, 이를 국소 수렴(local convergence)이라 한다. 초기점이 수렴 영역(convergence basin) 밖에 있으면 뉴턴 방법은 발산하거나 비최적점으로 수렴할 수 있다. 특히 다음의 상황에서 문제가 발생한다.

• 헤시안이 양정치가 아닌 경우: 뉴턴 방향이 하강 방향이 아니거나, 안장점이나 극대점 방향으로 이동할 수 있다.
• 헤시안이 특이(singular)한 경우: 뉴턴 방정식의 해가 존재하지 않거나 유일하지 않다.
• 이차 근사의 부정확성: 최적해에서 멀리 떨어진 경우 이차 모델이 원래 함수를 잘 근사하지 못한다.

이러한 한계를 극복하기 위해 직선 탐색이나 신뢰 영역(trust region)과 결합한 수정 뉴턴법이 사용된다.

6. 계산 비용

뉴턴 방법의 각 반복에서 다음의 계산이 필요하다.

1. 그래디언트 계산: O(n) 또는 목적 함수에 의존
2. 헤시안 계산: O(n^2) (대칭 행렬의 독립 원소 수 n(n+1)/2)
3. 선형 시스템 해법: \nabla^2 f \cdot \mathbf{d} = -\nabla f를 풀기 위한 O(n^3) (직접 분해) 또는 O(n^2) (반복적 해법)

n이 큰 경우 헤시안의 계산과 저장(O(n^2)), 선형 시스템 해법(O(n^3))이 병목이 된다. 이를 극복하기 위해 준뉴턴법(헤시안 근사), 절단 뉴턴법(반복적 해법으로 근사적 뉴턴 스텝 계산) 등의 변형이 개발되었다.

7. 뉴턴 감소량

뉴턴 감소량(Newton decrement) \lambda(\mathbf{x})는 다음과 같이 정의된다.

\lambda(\mathbf{x}) = \sqrt{\nabla f(\mathbf{x})^T [\nabla^2 f(\mathbf{x})]^{-1} \nabla f(\mathbf{x})}

이는 뉴턴 스텝에 의한 목적 함수 감소의 2차 근사값의 제곱근에 해당하며, 아핀 불변한 종료 기준으로 사용된다. \lambda(\mathbf{x}_k)^2 / 2 \leq \epsilon이면 이차 근사에 의한 잔여 감소가 \epsilon 이하임을 의미하므로, 수렴으로 판정한다.

8. 로봇 공학에서의 응용

뉴턴 방법은 정밀한 해가 요구되는 소규모 로봇 최적화 문제에 적합하다.

역기구학: 관절 공간에서 작업 공간으로의 비선형 사상의 역을 구하는 문제에서, 뉴턴 방법은 야코비안과 그 미분을 이용하여 빠른 수렴을 달성한다.

파라미터 추정: 로봇 동역학 파라미터(질량, 관성, 마찰 계수 등)를 실험 데이터로부터 추정하는 비선형 최소 제곱 문제에서, 가우스-뉴턴법과 레벤버그-마쿼트 알고리즘이 뉴턴 방법의 특수한 형태로 사용된다.

9. 참고 문헌

• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
• Dennis, J. E., & Schnabel, R. B. (1996). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM.
• Bertsekas, D. P. (2016). Nonlinear Programming (3rd ed.). Athena Scientific.

version: 1.0