7.95 준뉴턴 방법의 필요성과 원리

1. 뉴턴법과 경사 하강법 사이의 간극

경사 하강법은 그래디언트만을 사용하여 구현이 단순하고 메모리 효율적이지만, 선형 수렴에 그친다. 뉴턴법은 헤시안의 곡률 정보를 활용하여 이차 수렴을 달성하지만, 헤시안의 계산( $O(n^2)$ )과 선형 시스템 해법( $O(n^3)$ )의 높은 비용이 대규모 문제에서 병목이 된다. 준뉴턴법(quasi-Newton method)은 헤시안을 직접 계산하지 않고 그래디언트의 변화로부터 헤시안의 근사를 점진적으로 구축하여, 초선형 수렴(superlinear convergence)을 달성하면서도 반복당 비용을 $O(n^2)$ 로 유지하는 절충적 방법이다.

2. 시컨트 조건

준뉴턴법의 핵심 요구 사항은 헤시안 근사 행렬 $\mathbf{B}_{k+1}$ 이 최근의 그래디언트 변화를 정확히 반영하는 것이다. 이를 시컨트 조건(secant condition) 또는 준뉴턴 조건(quasi-Newton condition)이라 한다.

$\mathbf{B}_{k+1}\mathbf{s}_k = \mathbf{y}_k$

여기서 $\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k$ 는 변수 변화량, $\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)$ 는 그래디언트 변화량이다.

$n > 1$ 일 때 시컨트 조건은 $n$ 개의 등식 제약만을 부과하므로, $n \times n$ 대칭 행렬의 $n(n+1)/2$ 개 독립 원소를 유일하게 결정하기에 불충분하다. 따라서 추가적인 조건이 필요하며, 이전 근사 $\mathbf{B}_k$ 로부터의 최소 변화를 요구하는 것이 자연스러운 선택이다.

3. 역헤시안 근사

실용적으로는 헤시안 $\mathbf{B}_k$ 보다 역헤시안 $\mathbf{H}_k \approx [\nabla^2 f(\mathbf{x}_k)]^{-1}$ 을 직접 근사하는 것이 편리하다. 이 경우 뉴턴 방향은 행렬-벡터 곱으로 직접 계산된다.

$\mathbf{d}_k = -\mathbf{H}_k \nabla f(\mathbf{x}_k)$

시컨트 조건의 역형식은 다음과 같다.

$\mathbf{H}_{k+1}\mathbf{y}_k = \mathbf{s}_k$

4. 대칭 계수 1 갱신(SR1)

대칭 계수 1 갱신(Symmetric Rank-1 update)은 다음과 같다.

$\mathbf{B}_{k+1} = \mathbf{B}_k + \frac{(\mathbf{y}_k - \mathbf{B}_k\mathbf{s}_k)(\mathbf{y}_k - \mathbf{B}_k\mathbf{s}_k)^T}{(\mathbf{y}_k - \mathbf{B}_k\mathbf{s}_k)^T\mathbf{s}_k}$

SR1 갱신은 양정치성을 유지하지 않으므로, 비양정치 헤시안의 근사에도 사용될 수 있다. 그러나 분모가 영에 가까워질 수 있어 수치적 안정성에 주의가 필요하다.

5. 계수 2 갱신과 브로이든 계열

헤시안 근사를 계수 2(rank-2) 행렬의 가산으로 갱신하는 방법이 더 널리 사용된다. 시컨트 조건, 대칭성, 이전 근사로부터의 최소 변화를 동시에 만족하는 갱신은 브로이든(Broyden) 계열로 매개변수화된다.

$\mathbf{B}_{k+1} = (1-\phi)\mathbf{B}_{k+1}^{BFGS} + \phi \mathbf{B}_{k+1}^{DFP}, \quad \phi \in [0, 1]$

여기서 $\phi = 0$ 이 BFGS, $\phi = 1$ 이 DFP 갱신에 해당한다.

5.1 DFP 갱신

데이비돈-플레처-파웰(Davidon-Fletcher-Powell) 갱신은 역헤시안 근사에 대해 다음과 같다.

$\mathbf{H}_{k+1} = \left(\mathbf{I} - \frac{\mathbf{s}_k\mathbf{y}_k^T}{\mathbf{y}_k^T\mathbf{s}_k}\right)\mathbf{H}_k\left(\mathbf{I} - \frac{\mathbf{y}_k\mathbf{s}_k^T}{\mathbf{y}_k^T\mathbf{s}_k}\right) + \frac{\mathbf{s}_k\mathbf{s}_k^T}{\mathbf{y}_k^T\mathbf{s}_k}$

5.2 BFGS 갱신

브로이든-플레처-골드파브-샤노(Broyden-Fletcher-Goldfarb-Shanno) 갱신은 준뉴턴법 중 가장 성공적인 공식이다. 역헤시안 근사에 대한 갱신은 다음과 같다.

BFGS 갱신은 $\mathbf{s}_k^T\mathbf{y}_k > 0$ (곡률 조건)이 만족되면 양정치성을 유지한다. 울프 조건을 만족하는 직선 탐색은 이 곡률 조건을 보장한다.

6. 초선형 수렴

BFGS 방법은 울프 조건을 만족하는 직선 탐색과 결합하면, 강볼록 함수에서 초선형 수렴을 달성한다. 즉, 다음이 성립한다.

$\lim_{k \to \infty} \frac{\lVert \mathbf{x}_{k+1} - \mathbf{x}^* \rVert}{\lVert \mathbf{x}_k - \mathbf{x}^* \rVert} = 0$

이는 수렴률이 선형 수렴보다 빠르지만 이차 수렴보다는 느린 중간적 특성이다. 초선형 수렴이 달성되는 조건은 데니스-모레(Dennis-Moré) 조건으로 알려져 있으며, 헤시안 근사 $\mathbf{B}_k$ 가 실제 헤시안 $\nabla^2 f(\mathbf{x}^*)$ 에 점근적으로 수렴함을 요구한다.

7. 계산 비용 비교

방법	반복당 비용	저장량	수렴 차수
경사 하강법	$O(n)$	$O(n)$	선형
켤레 그래디언트법	$O(n)$	$O(n)$	초선형(이차 함수에서 유한 종료)
준뉴턴법(BFGS)	$O(n^2)$	$O(n^2)$	초선형
뉴턴법	$O(n^3)$	$O(n^2)$	이차

8. 로봇 공학에서의 위상

준뉴턴법은 변수의 수가 수십에서 수천 수준인 중규모 로봇 최적화 문제에 특히 적합하다. 역기구학, 궤적 매개변수 최적화, 센서 캘리브레이션 등에서 뉴턴법보다 낮은 비용으로 빠른 수렴을 달성하며, 경사 하강법보다 적은 반복 횟수로 고정밀 해를 산출한다.

9. 참고 문헌

Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Dennis, J. E., & Moré, J. J. (1977). “Quasi-Newton Methods, Motivation and Theory.” SIAM Review, 19(1), 46–89.
Broyden, C. G. (1970). “The Convergence of a Class of Double-Rank Minimization Algorithms.” Journal of the Institute of Mathematics and its Applications, 6, 76–90.
Fletcher, R. (1987). Practical Methods of Optimization (2nd ed.). Wiley.

version: 1.0