7.96 BFGS 알고리즘

1. BFGS 알고리즘의 전체 절차

BFGS(Broyden-Fletcher-Goldfarb-Shanno) 알고리즘은 준뉴턴법 중 가장 널리 사용되고 성공적인 방법이다. 전체 알고리즘은 다음과 같다.

입력: 초기점 $\mathbf{x}_0$ , 초기 역헤시안 근사 $\mathbf{H}_0$ (통상 $\mathbf{H}_0 = \mathbf{I}$ ), 수렴 허용 오차 $\epsilon$

$k = 0$ 으로 설정한다.
$\lVert \nabla f(\mathbf{x}_k) \rVert > \epsilon$ 인 동안 반복:
$\quad$ 탐색 방향 계산: $\mathbf{d}_k = -\mathbf{H}_k \nabla f(\mathbf{x}_k)$
$\quad$ 직선 탐색: 울프 조건을 만족하는 $\alpha_k$ 를 결정
$\quad$ 갱신: $\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k$
$\quad$ $\mathbf{s}_k = \mathbf{x}_{k+1} - \mathbf{x}_k$ , $\mathbf{y}_k = \nabla f(\mathbf{x}_{k+1}) - \nabla f(\mathbf{x}_k)$ 계산
$\quad$ 곡률 조건 확인: $\mathbf{s}_k^T \mathbf{y}_k > 0$
$\quad$ BFGS 역헤시안 갱신:

$\rho_k = \frac{1}{\mathbf{y}_k^T \mathbf{s}_k}$

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

$\quad$ $k \leftarrow k + 1$

2. BFGS 갱신의 성질

2.1 대칭성 보존

$\mathbf{H}_k$ 가 대칭이면 $\mathbf{H}_{k+1}$ 도 대칭이다. BFGS 갱신 공식의 구조가 이를 자동으로 보장한다.

2.2 양정치성 보존

$\mathbf{H}_k \succ 0$ 이고 $\mathbf{s}_k^T \mathbf{y}_k > 0$ 이면 $\mathbf{H}_{k+1} \succ 0$ 이다.

증명 개요: 임의의 $\mathbf{v} \neq \mathbf{0}$ 에 대해 $\mathbf{v}^T \mathbf{H}_{k+1} \mathbf{v}$ 를 전개하면 다음을 얻는다.

$\mathbf{v}^T \mathbf{H}_{k+1} \mathbf{v} = \mathbf{w}^T \mathbf{H}_k \mathbf{w} + \rho_k (\mathbf{s}_k^T \mathbf{v})^2$

여기서 $\mathbf{w} = (\mathbf{I} - \rho_k \mathbf{y}_k \mathbf{s}_k^T)\mathbf{v}$ 이다. $\mathbf{H}_k \succ 0$ 이므로 첫째 항은 비음수이고, $\rho_k > 0$ 이므로 둘째 항도 비음수이다. 양 항이 동시에 영이 되려면 $\mathbf{w} = \mathbf{0}$ 이고 $\mathbf{s}_k^T\mathbf{v} = 0$ 이어야 하나, $\mathbf{w} = \mathbf{v} - \rho_k(\mathbf{s}_k^T\mathbf{v})\mathbf{y}_k = \mathbf{v}$ 이므로 $\mathbf{v} = \mathbf{0}$ 이 되어 모순이다.

이 양정치성 보존은 BFGS의 핵심적 이점으로, 탐색 방향이 항상 하강 방향임을 보장한다. 울프 조건을 만족하는 직선 탐색은 $\mathbf{s}_k^T\mathbf{y}_k > 0$ 을 보장하므로, BFGS 갱신의 양정치성이 자동으로 유지된다.

2.3 시컨트 조건의 만족

$\mathbf{H}_{k+1}\mathbf{y}_k = \mathbf{s}_k$ 가 직접 계산으로 확인된다.

3. 헤시안 근사 형식의 BFGS

역헤시안 대신 헤시안 근사 $\mathbf{B}_k \approx \nabla^2 f(\mathbf{x}_k)$ 를 직접 갱신하는 형식도 존재한다.

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

이 경우 뉴턴 방향은 선형 시스템 $\mathbf{B}_k \mathbf{d}_k = -\nabla f(\mathbf{x}_k)$ 를 풀어 구해야 한다. 역헤시안 형식은 방향 계산이 행렬-벡터 곱 $O(n^2)$ 이므로 더 효율적이다.

4. 초기 헤시안 근사의 스케일링

$\mathbf{H}_0 = \mathbf{I}$ 로 시작하면 첫 번째 스텝이 최급경사 방향이 되어 비효율적일 수 있다. 실용적 개선으로, 첫 번째 갱신 후 다음의 스케일링을 적용한다.

$\mathbf{H}_0^{scaled} = \frac{\mathbf{y}_0^T \mathbf{s}_0}{\mathbf{y}_0^T \mathbf{y}_0} \mathbf{I}$

이 스케일링은 역헤시안의 대각 원소를 $\nabla^2 f$ 의 곡률에 맞추어 초기화하는 효과를 가지며, 초기 수렴을 상당히 가속한다.

5. 수렴 이론

5.1 전역 수렴

볼록이 아닌 일반적인 매끄러운 함수에서, 울프 조건을 만족하는 BFGS 방법은 다음을 보장한다.

$\liminf_{k \to \infty} \lVert \nabla f(\mathbf{x}_k) \rVert = 0$

이는 반복열의 어떤 부분열이 정류점에 수렴함을 의미한다. 볼록 함수에서는 더 강한 결과가 성립한다.

5.2 초선형 수렴

$f$ 가 두 번 연속 미분 가능하고, $\mathbf{x}^*$ 가 $\nabla^2 f(\mathbf{x}^*) \succ 0$ 인 국소 최소점이며, $\nabla^2 f$ 가 $\mathbf{x}^*$ 근방에서 리프시츠 연속이면, BFGS 반복열은 $\mathbf{x}^*$ 에 초선형으로 수렴한다. 이는 데니스-모레 조건을 통해 증명된다.

$\lim_{k \to \infty} \frac{\lVert (\mathbf{B}_k - \nabla^2 f(\mathbf{x}^*))\mathbf{d}_k \rVert}{\lVert \mathbf{d}_k \rVert} = 0$

이 조건은 BFGS 근사가 탐색 방향에서 실제 헤시안에 점근적으로 일치함을 의미한다.

6. 자기 보정 성질

BFGS 갱신은 자기 보정(self-correcting) 성질을 갖는다. 역헤시안 근사가 부정확하더라도, 후속 갱신을 통해 자동적으로 보정되는 경향이 있다. 이는 DFP 갱신에 비해 BFGS가 실용적으로 더 강건한 이유 중 하나이다.

7. 로봇 공학 응용에서의 BFGS

역기구학 해법: 로봇 매니퓰레이터의 역기구학을 비선형 방정식의 근 탐색 또는 비선형 최소화로 정식화할 때, BFGS가 효율적인 해법을 제공한다.

센서 캘리브레이션: 카메라-로봇 캘리브레이션에서 외부 파라미터의 최적화에 BFGS가 적용된다. 변수의 수가 수십 수준이므로 $O(n^2)$ 의 저장과 계산이 허용 가능하다.

소규모 궤적 최적화: 경유점의 수가 적은 궤적 최적화 문제에서 BFGS가 사용되며, 대규모 문제에서는 L-BFGS로 대체된다.

8. 참고 문헌

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. (1970). “A New Approach to Variable Metric Algorithms.” The Computer Journal, 13(3), 317–322.
Goldfarb, D. (1970). “A Family of Variable-Metric Methods Derived by Variational Means.” Mathematics of Computation, 24(109), 23–26.
Shanno, D. F. (1970). “Conditioning of Quasi-Newton Methods for Function Minimization.” Mathematics of Computation, 24(111), 647–656.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

version: 1.0