7.94 뉴턴 방법의 수정과 댐핑 뉴턴법

1. 순수 뉴턴법의 한계

순수 뉴턴법(pure Newton’s method)은 최적해 근방에서 이차 수렴을 달성하지만, 초기점이 수렴 영역 밖에 있을 때 발산할 수 있다. 또한 헤시안 $\nabla^2 f(\mathbf{x}_k)$ 가 양정치가 아닌 경우 뉴턴 방향이 하강 방향이 되지 않아 목적 함수가 증가할 수 있다. 이러한 한계를 극복하기 위해 다양한 수정(modification) 기법이 개발되었다.

2. 댐핑 뉴턴법(Damped Newton’s Method)

가장 직접적인 수정은 뉴턴 방향에 직선 탐색(line search)을 결합하는 것이다.

$\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k^N$

여기서 $\alpha_k > 0$ 은 아르미요 역추적 또는 울프 조건에 의해 결정되는 스텝 크기이다. 순수 뉴턴법은 항상 $\alpha_k = 1$ 을 사용하는 반면, 댐핑 뉴턴법은 $\alpha_k \leq 1$ 로 스텝을 축소하여 목적 함수의 충분한 감소를 보장한다.

$\nabla^2 f(\mathbf{x}_k) \succ 0$ 이면 뉴턴 방향이 하강 방향이므로, 아르미요 조건을 만족하는 $\alpha_k > 0$ 이 항상 존재한다. 최적해 근방에서는 단위 스텝 $\alpha_k = 1$ 이 아르미요 조건을 자동으로 만족하므로, 댐핑 뉴턴법은 최적해 근방에서 순수 뉴턴법으로 환원되어 이차 수렴을 유지한다.

3. 헤시안 수정법

3.1 대각 수정(Diagonal Modification)

헤시안이 양정치가 아닌 경우, 충분히 큰 양의 대각 행렬을 가산하여 양정치로 만든다.

$\mathbf{B}_k = \nabla^2 f(\mathbf{x}_k) + \mu_k \mathbf{I}$

여기서 $\mu_k \geq 0$ 은 다음을 만족하도록 선택된다.

$\mathbf{B}_k \succ 0 \quad \Leftrightarrow \quad \mu_k > \max(0, -\lambda_{\min}(\nabla^2 f(\mathbf{x}_k)))$

수정된 뉴턴 방향은 $\mathbf{d}_k = -\mathbf{B}_k^{-1}\nabla f(\mathbf{x}_k)$ 이다. $\mu_k$ 가 크면 $\mathbf{B}_k \approx \mu_k \mathbf{I}$ 이므로 방향이 최급경사 방향에 가까워지고, $\mu_k = 0$ 이면 순수 뉴턴 방향이 된다. 이 방법은 경사 하강법과 뉴턴법 사이의 연속적인 전이를 제공한다.

3.2 촐레스키 분해 기반 수정

실용적으로 헤시안의 양정치성을 검증하고 수정하는 가장 효율적인 방법은 수정된 촐레스키 분해(modified Cholesky factorization)이다. 이 방법은 촐레스키 분해 $\nabla^2 f = \mathbf{L}\mathbf{D}\mathbf{L}^T$ 과정에서 대각 원소 $D_{ii}$ 가 지나치게 작거나 음수가 되면 이를 양의 하한으로 대체한다.

$\tilde{D}_{ii} = \max(D_{ii}, \delta)$

여기서 $\delta > 0$ 은 사전 설정된 양의 임계값이다. Gill, Murray, Wright의 GMW81 알고리즘과 Schnabel, Eskow의 SE90 알고리즘이 대표적이다.

3.3 고유값 분해 기반 수정

헤시안의 고유값 분해 $\nabla^2 f = \mathbf{V}\boldsymbol{\Lambda}\mathbf{V}^T$ 를 수행하고, 음의 고유값을 절대값으로 대체하거나 양의 하한으로 치환한다.

$\tilde{\lambda}_i = \max(\lvert \lambda_i \rvert, \delta)$

이 방법은 개념적으로 명확하지만, 고유값 분해의 비용이 $O(n^3)$ 이므로 대규모 문제에는 비실용적이다.

4. 레벤버그-마쿼트 정규화

레벤버그-마쿼트(Levenberg-Marquardt) 방법은 본래 비선형 최소 제곱 문제를 위해 개발되었지만, 일반적인 비선형 최적화에서도 헤시안 정규화의 기법으로 사용된다.

$(\nabla^2 f(\mathbf{x}_k) + \mu_k \mathbf{I})\mathbf{d}_k = -\nabla f(\mathbf{x}_k)$

정규화 매개변수 $\mu_k$ 는 갱신의 성공 여부에 따라 적응적으로 조정된다. 갱신이 성공적이면(목적 함수가 충분히 감소하면) $\mu_k$ 를 감소시켜 뉴턴법에 가깝게 하고, 실패하면 $\mu_k$ 를 증가시켜 경사 하강법에 가깝게 한다.

5. 신뢰 영역 뉴턴법

신뢰 영역(trust region) 접근법은 이차 모델이 원래 함수를 잘 근사하는 영역을 명시적으로 제한한다.

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

$\text{subject to} \quad \lVert \mathbf{d} \rVert \leq \Delta_k$

신뢰 영역 반지름 $\Delta_k$ 는 실제 감소와 예측 감소의 비율에 따라 조정된다.

$\rho_k = \frac{f(\mathbf{x}_k) - f(\mathbf{x}_k + \mathbf{d}_k)}{m_k(\mathbf{0}) - m_k(\mathbf{d}_k)}$

$\rho_k$ 가 1에 가까우면 이차 모델이 정확하므로 $\Delta_k$ 를 증가시키고, $\rho_k$ 가 작거나 음수이면 $\Delta_k$ 를 축소한다. 이 하위 문제의 최적해는 KKT 조건에 의해 $(\nabla^2 f + \mu \mathbf{I})\mathbf{d} = -\nabla f$ 형태로 귀착되며, $\mu \geq 0$ 은 $\lVert \mathbf{d} \rVert = \Delta_k$ 를 만족시키는 값으로 결정된다.

6. 절단 뉴턴법(Truncated Newton Method)

대규모 문제에서 뉴턴 방정식 $\nabla^2 f \cdot \mathbf{d} = -\nabla f$ 를 직접 풀기 어려울 때, 켤레 그래디언트법(CG)으로 근사적으로 푸는 방법이다. CG 반복을 조기 종료(truncation)하여 근사 뉴턴 방향을 얻으며, 부정확한 해를 수용하더라도 충분한 하강을 보장하는 종료 기준이 설계된다.

CG 반복 중 음의 곡률 방향( $\mathbf{d}^T\nabla^2 f\mathbf{d} \leq 0$ )이 감지되면 즉시 반복을 종료하고, 해당 시점까지의 근사 해를 뉴턴 방향으로 사용한다. 이 처리는 헤시안이 비양정치인 경우의 안전 장치 역할을 한다.

절단 뉴턴법의 핵심 이점은 헤시안 행렬을 명시적으로 형성하거나 저장할 필요 없이, 헤시안-벡터 곱 $\nabla^2 f \cdot \mathbf{v}$ 만을 반복적으로 계산하면 된다는 점이다. 이 곱은 자동 미분으로 $O(n)$ 비용에 계산 가능하다.

7. 로봇 공학에서의 수정 뉴턴법

비선형 최소 제곱: 로봇 캘리브레이션, SLAM 백엔드 최적화에서 가우스-뉴턴법은 헤시안을 야코비안의 곱 $\mathbf{J}^T\mathbf{J}$ 로 근사하며, 이 근사 헤시안은 항상 양의 반정치이다. 레벤버그-마쿼트 정규화가 양정치성을 보장하고 수렴 영역을 확장한다.

궤적 최적화: iLQR과 DDP에서 뉴턴 방정식은 동적 계획법 구조를 활용하여 $O(nT)$ ( $T$ 는 시간 스텝 수)에 효율적으로 풀린다. 정규화 항의 추가가 비양정치 헤시안에 의한 수치적 불안정을 방지한다.

8. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Dennis, J. E., & Schnabel, R. B. (1996). Numerical Methods for Unconstrained Optimization and Nonlinear Equations. SIAM.
Conn, A. R., Gould, N. I. M., & Toint, P. L. (2000). Trust-Region Methods. SIAM.
Gill, P. E., Murray, W., & Wright, M. H. (1981). Practical Optimization. Academic Press.

version: 1.0