7.137 이차 수렴 조건과 뉴턴 방법의 수렴 정리
1. 뉴턴 방법의 국소 이차 수렴 정리
정리 (뉴턴-칸토로비치): f: \mathbb{R}^n \to \mathbb{R}이 두 번 연속 미분 가능하고, \mathbf{x}^*가 \nabla f(\mathbf{x}^*) = \mathbf{0}이며 \nabla^2 f(\mathbf{x}^*) \succ 0인 점이라 하자. \nabla^2 f가 \mathbf{x}^*의 근방에서 리프시츠 연속이면, 즉
\lVert \nabla^2 f(\mathbf{x}) - \nabla^2 f(\mathbf{y}) \rVert \leq L_H \lVert \mathbf{x} - \mathbf{y} \rVert
이면, \mathbf{x}_0가 \mathbf{x}^*에 충분히 가까울 때 뉴턴 반복
\mathbf{x}_{k+1} = \mathbf{x}_k - [\nabla^2 f(\mathbf{x}_k)]^{-1}\nabla f(\mathbf{x}_k)
은 \mathbf{x}^*에 이차 수렴한다.
\lVert \mathbf{x}_{k+1} - \mathbf{x}^* \rVert \leq C\lVert \mathbf{x}_k - \mathbf{x}^* \rVert^2
여기서 C = \frac{L_H}{2}\lVert [\nabla^2 f(\mathbf{x}^*)]^{-1} \rVert이다.
2. 이차 수렴의 조건 분석
이차 수렴을 위한 핵심 조건은 다음의 세 가지이다.
2.1 비특이 헤시안
\nabla^2 f(\mathbf{x}^*) \succ 0 \quad (\text{또는 비특이})
\nabla^2 f(\mathbf{x}^*)가 특이(singular)하면, 뉴턴 방정식의 해가 존재하지 않거나 크기가 무한대로 발산할 수 있다. 비특이 조건은 \mathbf{x}^*가 고립된(isolated) 정류점임을 보장한다.
2.2 헤시안의 리프시츠 연속성
\lVert \nabla^2 f(\mathbf{x}) - \nabla^2 f(\mathbf{x}^*) \rVert \leq L_H \lVert \mathbf{x} - \mathbf{x}^* \rVert
이 조건은 헤시안이 최적점 근방에서 급격하게 변하지 않음을 요구한다. 리프시츠 상수 L_H가 클수록 이차 수렴의 수렴 영역이 좁아진다.
2.3 충분히 가까운 초기점
\lVert \mathbf{x}_0 - \mathbf{x}^* \rVert < \frac{2}{C} = \frac{4}{L_H\lVert [\nabla^2 f(\mathbf{x}^*)]^{-1}\rVert}
이 조건은 뉴턴 방법의 국소적 성격을 반영한다. 초기점이 이 범위를 벗어나면 수렴이 보장되지 않는다.
3. 증명의 핵심 아이디어
뉴턴 갱신의 오차를 분석하기 위해 \nabla f(\mathbf{x}^*) = \mathbf{0}과 평균값 정리를 이용한다.
\nabla f(\mathbf{x}_k) = \nabla f(\mathbf{x}_k) - \nabla f(\mathbf{x}^*) = \bar{\mathbf{H}}_k(\mathbf{x}_k - \mathbf{x}^*)
여기서 \bar{\mathbf{H}}_k = \int_0^1 \nabla^2 f(\mathbf{x}^* + t(\mathbf{x}_k - \mathbf{x}^*)) dt는 경로를 따른 평균 헤시안이다.
뉴턴 갱신 후의 오차는 다음과 같다.
\mathbf{x}_{k+1} - \mathbf{x}^* = (\mathbf{x}_k - \mathbf{x}^*) - [\nabla^2 f(\mathbf{x}_k)]^{-1}\bar{\mathbf{H}}_k(\mathbf{x}_k - \mathbf{x}^*)
= [\nabla^2 f(\mathbf{x}_k)]^{-1}(\nabla^2 f(\mathbf{x}_k) - \bar{\mathbf{H}}_k)(\mathbf{x}_k - \mathbf{x}^*)
\nabla^2 f의 리프시츠 연속성에 의해 \lVert \nabla^2 f(\mathbf{x}_k) - \bar{\mathbf{H}}_k \rVert \leq \frac{1}{2}L_H\lVert \mathbf{x}_k - \mathbf{x}^* \rVert이므로
\lVert \mathbf{x}_{k+1} - \mathbf{x}^* \rVert \leq \frac{L_H}{2}\lVert [\nabla^2 f(\mathbf{x}_k)]^{-1}\rVert \lVert \mathbf{x}_k - \mathbf{x}^* \rVert^2
\mathbf{x}_k가 \mathbf{x}^*에 가까우면 \lVert [\nabla^2 f(\mathbf{x}_k)]^{-1}\rVert \approx \lVert [\nabla^2 f(\mathbf{x}^*)]^{-1}\rVert이므로, 이차 수렴이 확립된다.
4. 비선형 방정식에서의 뉴턴법 수렴 정리
비선형 방정식 \mathbf{F}(\mathbf{x}) = \mathbf{0}에 대한 뉴턴법 \mathbf{x}_{k+1} = \mathbf{x}_k - [\mathbf{F}'(\mathbf{x}_k)]^{-1}\mathbf{F}(\mathbf{x}_k)의 이차 수렴 조건도 유사하다. \mathbf{F}'(\mathbf{x}^*)가 비특이이고 \mathbf{F}'가 리프시츠 연속이면, 초기점이 충분히 가까울 때 이차 수렴한다. 로봇 역기구학의 뉴턴-라프슨 해법이 이에 직접 해당한다.
5. 비선형 최소 제곱에서의 수렴
가우스-뉴턴법의 수렴 차수는 잔차의 크기에 의존한다.
- 영잔차: \mathbf{r}(\mathbf{x}^*) = \mathbf{0}이면 이차 수렴
- 소잔차: \lVert \mathbf{r}(\mathbf{x}^*) \rVert 작으면 거의 이차에 가까운 수렴
- 대잔차: 선형 수렴 또는 수렴 실패
레벤버그-마쿼트 알고리즘은 영잔차 문제에서 가우스-뉴턴으로 전환되어 이차 수렴을 달성하고, 대잔차 문제에서는 정규화에 의해 안정적 수렴을 보장한다.
6. 수렴 영역의 확장
순수 뉴턴법의 좁은 수렴 영역은 실용적 한계이다. 수렴 영역을 확장하는 두 가지 표준 전략이 있다.
댐핑 뉴턴법: 직선 탐색에 의해 스텝 크기를 제한한다. 전역 수렴이 보장되며, 최적해 근방에서 단위 스텝이 수용되어 이차 수렴으로 복귀한다.
신뢰 영역 뉴턴법: 이차 모델의 신뢰할 수 있는 범위를 명시적으로 제한한다. 전역 수렴이 보장되며, 최적해 근방에서 신뢰 영역이 비활성이 되어 이차 수렴으로 복귀한다.
7. 참고 문헌
- 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.
- Ortega, J. M., & Rheinboldt, W. C. (1970). Iterative Solution of Nonlinear Equations in Several Variables. Academic Press.
- Kantorovich, L. V. (1948). “Functional Analysis and Applied Mathematics.” Uspekhi Matematicheskikh Nauk, 3(6), 89–185.
version: 1.0