7.130 레벤버그-마쿼트 알고리즘

1. 가우스-뉴턴법과 경사 하강법의 결합

레벤버그-마쿼트(Levenberg-Marquardt, LM) 알고리즘은 가우스-뉴턴법과 경사 하강법의 장점을 결합한 비선형 최소 제곱 문제의 해법이다. 레벤버그(Levenberg, 1944)가 최초로 제안하고, 마쿼트(Marquardt, 1963)가 개선하였다. 가우스-뉴턴법이 최적해 근방에서 빠른 수렴을 달성하지만 수렴 영역이 제한적인 반면, 경사 하강법은 수렴 영역이 넓지만 수렴이 느리다. LM 알고리즘은 댐핑 매개변수(damping parameter)에 의해 두 방법 사이를 연속적으로 전환한다.

2. 알고리즘

LM 방향은 다음의 정규화된 정규 방정식의 해이다.

$(\mathbf{J}_k^T\mathbf{J}_k + \lambda_k \mathbf{I})\mathbf{d}_k = -\mathbf{J}_k^T\mathbf{r}_k$

여기서 $\lambda_k > 0$ 은 댐핑 매개변수이다.

$\lambda_k \to 0$ : 가우스-뉴턴 방향에 접근한다. 이차 모델이 신뢰할 수 있는 경우에 해당하며, 빠른 수렴이 가능하다.

$\lambda_k \to \infty$ : $\mathbf{d}_k \approx -\frac{1}{\lambda_k}\mathbf{J}_k^T\mathbf{r}_k = -\frac{1}{\lambda_k}\nabla f(\mathbf{x}_k)$ 로, 작은 스텝의 경사 하강 방향에 접근한다. 이차 모델이 부정확한 경우의 안전한 선택이다.

2.1 전체 절차

초기점 $\mathbf{x}_0$ , 초기 댐핑 $\lambda_0 > 0$ 을 설정한다.
$k = 0, 1, 2, \ldots$ 에 대해:
$\quad$ $\mathbf{r}_k$ , $\mathbf{J}_k$ 를 계산한다.
$\quad$ $(\mathbf{J}_k^T\mathbf{J}_k + \lambda_k\mathbf{I})\mathbf{d}_k = -\mathbf{J}_k^T\mathbf{r}_k$ 를 풀어 $\mathbf{d}_k$ 를 구한다.
$\quad$ 이득 비율(gain ratio) $\rho_k$ 를 계산한다.

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

$\quad$ if $\rho_k > \epsilon$ (예: $\epsilon = 0.01$ ): 스텝 수용 $\mathbf{x}_{k+1} = \mathbf{x}_k + \mathbf{d}_k$
$\quad$ else: 스텝 기각 $\mathbf{x}_{k+1} = \mathbf{x}_k$
$\quad$ 댐핑 매개변수 갱신:

$\rho_k > 0.75$ : $\lambda_{k+1} = \lambda_k / 3$ (댐핑 감소, 가우스-뉴턴 쪽으로)
$\rho_k < 0.25$ : $\lambda_{k+1} = 2\lambda_k$ (댐핑 증가, 경사 하강 쪽으로)
그 외: $\lambda_{k+1} = \lambda_k$ (유지)

3. 마쿼트의 스케일링

마쿼트는 단위 행렬 $\mathbf{I}$ 대신 $\mathbf{J}_k^T\mathbf{J}_k$ 의 대각을 사용하는 스케일링 변형을 제안하였다.

$(\mathbf{J}_k^T\mathbf{J}_k + \lambda_k \text{diag}(\mathbf{J}_k^T\mathbf{J}_k))\mathbf{d}_k = -\mathbf{J}_k^T\mathbf{r}_k$

이 스케일링은 파라미터의 스케일 차이를 보상하여, 그래디언트가 큰 방향에서는 더 강한 댐핑을, 그래디언트가 작은 방향에서는 더 약한 댐핑을 적용한다.

4. 신뢰 영역 해석

LM 알고리즘은 신뢰 영역법의 특수한 경우로 해석된다. 댐핑 매개변수 $\lambda_k$ 와 신뢰 영역 반지름 $\Delta_k$ 사이에 일대일 대응이 존재한다.

$(\mathbf{J}_k^T\mathbf{J}_k + \lambda_k\mathbf{I})\mathbf{d}_k = -\mathbf{J}_k^T\mathbf{r}_k \quad \Leftrightarrow \quad \min_{\lVert \mathbf{d} \rVert \leq \Delta_k} \lVert \mathbf{r}_k + \mathbf{J}_k\mathbf{d} \rVert^2$

$\lambda_k$ 가 증가하면 $\Delta_k$ 가 감소하고, $\lambda_k$ 가 감소하면 $\Delta_k$ 가 증가한다.

5. 수렴 성질

LM 알고리즘은 다음의 수렴 성질을 갖는다.

전역 수렴: 적절한 댐핑 갱신 전략하에서 임의의 초기점에서 정류점으로의 수렴이 보장된다.
영잔차 문제에서의 이차 수렴: $\mathbf{r}(\mathbf{x}^*) = \mathbf{0}$ 이고 $\mathbf{J}(\mathbf{x}^*)$ 가 열 완전 계수이면, 최적해 근방에서 $\lambda_k \to 0$ 이 되어 가우스-뉴턴법으로 전환되고 이차 수렴을 달성한다.
소잔차 문제에서의 초선형 수렴: 잔차가 작지만 영이 아닌 경우에도 빠른 수렴이 기대된다.

6. 구현의 실용적 고려

초기 댐핑의 선택: $\lambda_0 = \tau \cdot \max_i(\mathbf{J}_0^T\mathbf{J}_0)_{ii}$ 로 설정하며, $\tau \in [10^{-3}, 1]$ 이 통상적이다.

종료 기준: 다음의 조건 중 하나가 만족되면 종료한다.

그래디언트 노름: $\lVert \mathbf{J}_k^T\mathbf{r}_k \rVert_\infty < \epsilon_1$
스텝 크기: $\lVert \mathbf{d}_k \rVert < \epsilon_2(\lVert \mathbf{x}_k \rVert + \epsilon_2)$
잔차 변화: $\lvert f(\mathbf{x}_k) - f(\mathbf{x}_{k+1}) \rvert < \epsilon_3 f(\mathbf{x}_k)$
최대 반복 횟수 초과

야코비안 계산: 해석적 야코비안이 제공되면 정확하고 효율적이다. 자동 미분 또는 유한 차분으로도 계산 가능하다. Ceres Solver는 자동 미분에 의한 야코비안 계산을 기본으로 지원한다.

7. 로봇 공학에서의 응용

LM 알고리즘은 로봇 공학에서 비선형 최소 제곱 문제의 표준 해법으로 사용된다.

로봇 캘리브레이션: DH 파라미터, 카메라-로봇 외부 파라미터 등의 추정에 LM이 적용된다.

SLAM 백엔드: g2o, GTSAM 등의 SLAM 해법기에서 LM이 기본 최적화기로 제공된다.

핸드-아이 캘리브레이션: 로봇 손과 카메라 사이의 상대 자세를 최적화하는 AX = XB 문제의 비선형 최소 제곱 해법에 LM이 사용된다.

역기구학: 최적화 기반 역기구학에서 댐핑된 최소 제곱법(DLS)은 LM 알고리즘의 단일 반복에 해당한다.

8. 참고 문헌

Levenberg, K. (1944). “A Method for the Solution of Certain Non-Linear Problems in Least Squares.” Quarterly of Applied Mathematics, 2(2), 164–168.
Marquardt, D. W. (1963). “An Algorithm for Least-Squares Estimation of Nonlinear Parameters.” Journal of the Society for Industrial and Applied Mathematics, 11(2), 431–441.
Moré, J. J. (1978). “The Levenberg-Marquardt Algorithm: Implementation and Theory.” Lecture Notes in Mathematics, 630, 105–116.
Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
Madsen, K., Nielsen, H. B., & Tingleff, O. (2004). Methods for Non-Linear Least Squares Problems (2nd ed.). Technical University of Denmark.

version: 1.0