7.97 L-BFGS 알고리즘과 대규모 최적화

1. BFGS의 저장 문제와 제한된 메모리 접근

표준 BFGS 알고리즘은 $n \times n$ 역헤시안 근사 행렬 $\mathbf{H}_k$ 를 명시적으로 저장하므로 $O(n^2)$ 의 메모리를 요구한다. 결정 변수의 수 $n$ 이 수만 이상인 대규모 문제에서는 이 저장 요구가 실질적인 제한이 된다. L-BFGS(Limited-memory BFGS)는 가장 최근의 $m$ 개 벡터 쌍 $\{(\mathbf{s}_j, \mathbf{y}_j)\}$ 만을 저장하여 역헤시안-그래디언트 곱 $\mathbf{H}_k \nabla f(\mathbf{x}_k)$ 를 암묵적으로 계산한다. 저장 요구량은 $O(mn)$ 이며, 통상 $m = 3 \sim 20$ 이다.

2. 이중 루프 재귀

L-BFGS의 핵심은 노세달(Nocedal)이 제안한 이중 루프 재귀(two-loop recursion)로, $\mathbf{H}_k \nabla f(\mathbf{x}_k)$ 를 $\mathbf{H}_k$ 를 명시적으로 형성하지 않고 $O(mn)$ 에 계산한다.

알고리즘: 입력 $\nabla f(\mathbf{x}_k)$ , 벡터 쌍 $\{(\mathbf{s}_j, \mathbf{y}_j)\}_{j=k-m}^{k-1}$

$\mathbf{q} \leftarrow \nabla f(\mathbf{x}_k)$
for $j = k-1, k-2, \ldots, k-m$ :
$\quad \alpha_j \leftarrow \rho_j \mathbf{s}_j^T \mathbf{q}$
$\quad \mathbf{q} \leftarrow \mathbf{q} - \alpha_j \mathbf{y}_j$
$\mathbf{r} \leftarrow \mathbf{H}_k^0 \mathbf{q}$ (초기 역헤시안 근사 적용)
for $j = k-m, k-m+1, \ldots, k-1$ :
$\quad \beta_j \leftarrow \rho_j \mathbf{y}_j^T \mathbf{r}$
$\quad \mathbf{r} \leftarrow \mathbf{r} + (\alpha_j - \beta_j)\mathbf{s}_j$
return $\mathbf{r} = \mathbf{H}_k \nabla f(\mathbf{x}_k)$

여기서 $\rho_j = 1/(\mathbf{y}_j^T\mathbf{s}_j)$ 이다.

3. 초기 역헤시안 스케일링

초기 역헤시안 $\mathbf{H}_k^0$ 는 통상 스칼라 배의 단위 행렬로 설정된다.

$\mathbf{H}_k^0 = \gamma_k \mathbf{I}, \quad \gamma_k = \frac{\mathbf{s}_{k-1}^T \mathbf{y}_{k-1}}{\mathbf{y}_{k-1}^T \mathbf{y}_{k-1}}$

이 스케일링은 가장 최근의 곡률 정보를 반영하여 탐색 방향의 크기를 적절히 조정하며, 직선 탐색에서 단위 스텝( $\alpha = 1$ )이 수용될 확률을 높인다.

4. L-BFGS 알고리즘의 전체 절차

초기점 $\mathbf{x}_0$ , 메모리 크기 $m$ 을 설정한다.
$k = 0, 1, 2, \ldots$ 에 대해:
$\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$ 저장된 쌍이 $m$ 개를 초과하면 가장 오래된 쌍을 삭제
$\quad$ 수렴 판정

5. 메모리 크기의 선택

메모리 크기 $m$ 은 곡률 근사의 정확도와 저장 비용 사이의 상충 관계를 결정한다.

$m$ 이 작으면( $m = 3 \sim 5$ ): 저장 비용이 최소화되지만 곡률 근사가 부정확하여 경사 하강법에 가까운 거동을 보일 수 있다.
$m$ 이 크면( $m = 15 \sim 20$ ): 곡률 근사가 개선되어 수렴이 가속되지만, 저장 비용이 증가한다.
실용적으로 $m = 5 \sim 10$ 이 대부분의 문제에서 좋은 성능을 제공한다.

$m = n$ 이면 L-BFGS는 표준 BFGS와 수학적으로 동치이다.

6. 계산 비용

연산	BFGS	L-BFGS
저장량	$O(n^2)$	$O(mn)$
방향 계산	$O(n^2)$	$O(mn)$
갱신	$O(n^2)$	$O(n)$

L-BFGS의 반복당 비용은 $O(mn)$ 이며, $m$ 이 상수이면 경사 하강법과 동일한 $O(n)$ 의 차수이다. 이는 L-BFGS가 대규모 문제에서 경사 하강법의 계산 효율성과 준뉴턴법의 수렴 속도를 동시에 제공함을 의미한다.

7. 수렴 성질

L-BFGS는 표준 BFGS와 달리 전체 곡률 이력을 보존하지 않으므로, 이론적 수렴 보장이 약간 약하다. 그러나 실용적으로는 표준 BFGS에 버금가는 성능을 보이며, 볼록 함수에서의 전역 수렴과 강볼록 함수에서의 R-선형 수렴(R-linear convergence)이 보장된다. $m$ 이 클수록 표준 BFGS의 초선형 수렴에 가까운 거동을 보인다.

8. L-BFGS-B: 구간 제약 확장

L-BFGS-B는 구간 제약(box constraint) $\mathbf{l} \leq \mathbf{x} \leq \mathbf{u}$ 를 처리할 수 있도록 L-BFGS를 확장한 것이다. 각 반복에서 활성 구간 제약의 집합을 식별하고, 자유 변수에 대해서만 L-BFGS 방향을 계산하며, 구간 경계를 위반하지 않도록 스텝 크기를 제한한다. 로봇 관절 각도 한계와 같은 물리적 구간 제약이 있는 최적화 문제에 직접 적용된다.

9. 대규모 로봇 최적화에서의 응용

궤적 최적화: 수백에서 수천 개의 결정 변수를 갖는 로봇 궤적 최적화에서 L-BFGS는 표준 해법으로 사용된다. 궤적의 시간 이산화 격자점에서의 상태와 제어 입력이 결정 변수를 구성하며, 직접 전사법(direct transcription)으로 이산화된 문제에 L-BFGS를 적용한다.

경로 최적화: CHOMP(Covariant Hamiltonian Optimization for Motion Planning)의 변형에서 L-BFGS가 사용되어, 대규모 경로 표현의 효율적 최적화를 가능하게 한다.

SLAM 백엔드: 그래프 기반 SLAM의 백엔드 최적화에서 포즈 변수의 수가 수만에 이를 수 있으며, 문제의 희소 구조를 활용한 L-BFGS 또는 가우스-뉴턴법이 적용된다.

기계 학습: 로봇 학습에서 신경망의 파라미터 수가 매우 큰 경우에도 L-BFGS가 전체 배치 학습에 사용될 수 있으며, 미니 배치 환경에서의 확률적 L-BFGS 변형도 연구되고 있다.

10. 참고 문헌

Nocedal, J. (1980). “Updating Quasi-Newton Matrices with Limited Storage.” Mathematics of Computation, 35(151), 773–782.
Liu, D. C., & Nocedal, J. (1989). “On the Limited Memory BFGS Method for Large Scale Optimization.” Mathematical Programming, 45(1-3), 503–528.
Byrd, R. H., Lu, P., Nocedal, J., & Zhu, C. (1995). “A Limited Memory Algorithm for Bound Constrained Optimization.” SIAM Journal on Scientific Computing, 16(5), 1190–1208.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.

version: 1.0