6.134 경사 하강법과 뉴턴법의 선형대수학적 기반

1. 최적화와 선형대수학의 연결

로봇공학의 다양한 문제, 예를 들어 역기구학, 궤적 최적화, 파라미터 추정 등은 비선형 최적화 문제로 귀결된다. 이러한 문제를 풀기 위한 반복적(iterative) 알고리즘의 핵심에는 선형대수학적 연산이 자리하고 있다. 본 절에서는 경사 하강법(gradient descent)과 뉴턴법(Newton’s method)을 선형대수학의 관점에서 분석한다.

2. 경사 하강법의 구조

2.1 기본 알고리즘

스칼라 목적 함수 f: \mathbb{R}^n \to \mathbb{R}를 최소화하는 경사 하강법은 다음의 반복 규칙을 따른다.

\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \nabla f(\mathbf{x}_k)

여기서 \alpha_k > 0은 스텝 크기(step size 또는 학습률)이고, \nabla f(\mathbf{x}_k) \in \mathbb{R}^n은 그래디언트 벡터이다. 그래디언트는 f의 가장 가파른 증가 방향을 나타내므로, -\nabla f(\mathbf{x}_k)는 가장 가파른 감소 방향(steepest descent direction)이다.

2.2 그래디언트의 선형대수학적 해석

함수 f가 이차 함수인 경우를 고려한다.

f(\mathbf{x}) = \frac{1}{2} \mathbf{x}^T \mathbf{A} \mathbf{x} - \mathbf{b}^T \mathbf{x} + c

여기서 \mathbf{A} \in \mathbb{R}^{n \times n}은 양의 정치(positive definite) 대칭 행렬이다. 이 경우 그래디언트와 최적해는 다음과 같다.

\nabla f(\mathbf{x}) = \mathbf{A}\mathbf{x} - \mathbf{b}, \qquad \mathbf{x}^* = \mathbf{A}^{-1}\mathbf{b}

따라서 경사 하강법의 반복 규칙은 다음과 같이 변환된다.

\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k (\mathbf{A}\mathbf{x}_k - \mathbf{b}) = (\mathbf{I} - \alpha_k \mathbf{A})\mathbf{x}_k + \alpha_k \mathbf{b}

2.3 수렴 속도와 조건수

오차 벡터 \mathbf{e}_k = \mathbf{x}_k - \mathbf{x}^*에 대하여 다음이 성립한다.

\mathbf{e}_{k+1} = (\mathbf{I} - \alpha_k \mathbf{A})\mathbf{e}_k

최적의 고정 스텝 크기 \alpha^* = \frac{2}{\lambda_{\max} + \lambda_{\min}}을 사용하면, 에너지 노름 \lVert \mathbf{e}_k \rVert_{\mathbf{A}}^2 = \mathbf{e}_k^T \mathbf{A} \mathbf{e}_k에 대하여 수렴 비율은 다음과 같다.

\frac{\lVert \mathbf{e}_{k+1} \rVert_{\mathbf{A}}}{\lVert \mathbf{e}_k \rVert_{\mathbf{A}}} \leq \frac{\kappa(\mathbf{A}) - 1}{\kappa(\mathbf{A}) + 1}

여기서 \kappa(\mathbf{A}) = \frac{\lambda_{\max}(\mathbf{A})}{\lambda_{\min}(\mathbf{A})}는 행렬 \mathbf{A}의 조건수(condition number)이다. 조건수가 클수록 수렴이 느려지며, \kappa(\mathbf{A}) = 1일 때 한 번의 반복으로 수렴한다. 이는 등방성(isotropic) 문제에 해당한다.

2.4 전처리(Preconditioning)

조건수를 개선하기 위하여 전처리 행렬 \mathbf{M}을 도입한다. \mathbf{M} \approx \mathbf{A}인 양의 정치 행렬을 선택하여 변환된 시스템을 풀면 다음과 같다.

\mathbf{x}_{k+1} = \mathbf{x}_k - \alpha_k \mathbf{M}^{-1} \nabla f(\mathbf{x}_k)

이는 \mathbf{M}^{-1}\mathbf{A}의 조건수가 원래 \mathbf{A}의 조건수보다 작아지도록 설계된 것이다. 전처리된 경사 하강법의 수렴 비율은 \kappa(\mathbf{M}^{-1}\mathbf{A})에 의하여 결정된다.

3. 뉴턴법의 구조

3.1 기본 알고리즘

뉴턴법은 목적 함수를 현재 점에서 이차 테일러 근사하여 그 근사 함수의 최솟값을 다음 반복점으로 선택한다.

f(\mathbf{x}_k + \Delta \mathbf{x}) \approx f(\mathbf{x}_k) + \nabla f(\mathbf{x}_k)^T \Delta \mathbf{x} + \frac{1}{2} \Delta \mathbf{x}^T \nabla^2 f(\mathbf{x}_k) \Delta \mathbf{x}

이 이차 근사를 \Delta \mathbf{x}에 대하여 최소화하면 뉴턴 방정식(Newton equation)을 얻는다.

\nabla^2 f(\mathbf{x}_k) \Delta \mathbf{x}_k = -\nabla f(\mathbf{x}_k)

즉, 뉴턴 스텝 \Delta \mathbf{x}_k는 헤시안 행렬 \mathbf{H}_k = \nabla^2 f(\mathbf{x}_k)와 그래디언트 \mathbf{g}_k = \nabla f(\mathbf{x}_k)로부터 다음의 선형 시스템을 풀어야 한다.

\mathbf{H}_k \Delta \mathbf{x}_k = -\mathbf{g}_k

갱신 규칙은 다음과 같다.

\mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \Delta \mathbf{x}_k

여기서 \alpha_k는 직선 탐색(line search)으로 결정한다. \alpha_k = 1인 순수 뉴턴법은 이차 수렴(quadratic convergence)을 보인다.

3.2 뉴턴 방정식의 선형대수학

뉴턴 방정식 \mathbf{H}_k \Delta \mathbf{x}_k = -\mathbf{g}_k를 효율적으로 푸는 것이 뉴턴법의 핵심이다. 주요 방법은 다음과 같다.

촐레스키 분해: \mathbf{H}_k가 양의 정치이면 촐레스키 분해 \mathbf{H}_k = \mathbf{L}_k \mathbf{L}_k^T를 수행하고, 전방/후방 대입으로 \Delta \mathbf{x}_k를 구한다. 계산 복잡도는 O(n^3/3)이다.

LDL 분해: \mathbf{H}_k가 부정치(indefinite)일 수 있는 경우, \mathbf{H}_k = \mathbf{L}\mathbf{D}\mathbf{L}^T 분해를 사용한다. 여기서 \mathbf{L}은 단위 하삼각 행렬이고, \mathbf{D}는 블록 대각 행렬(1 \times 1 또는 2 \times 2 블록)이다.

켤레 기울기법(Conjugate Gradient): 대규모 문제에서 헤시안을 명시적으로 저장하지 않고 헤시안-벡터 곱 \mathbf{H}_k \mathbf{v}만 계산할 수 있을 때 적합하다. 이를 행렬 자유(matrix-free) 뉴턴법이라 한다.

3.3 이차 수렴성

뉴턴법의 가장 중요한 특성은 이차 수렴성(quadratic convergence)이다. 최적해 \mathbf{x}^* 근방에서 충분히 가까운 초기점 \mathbf{x}_0에 대하여 다음이 성립한다.

\lVert \mathbf{x}_{k+1} - \mathbf{x}^* \rVert \leq C \lVert \mathbf{x}_k - \mathbf{x}^* \rVert^2

이는 유효 자릿수가 매 반복마다 대략 두 배로 증가함을 의미한다.

4. 가우스-뉴턴법

비선형 최소 제곱 문제 \min_{\mathbf{x}} \frac{1}{2} \lVert \mathbf{r}(\mathbf{x}) \rVert^2에서, \mathbf{r}: \mathbb{R}^n \to \mathbb{R}^m이 잔차 벡터(residual vector)이면, 가우스-뉴턴법은 헤시안을 자코비안의 곱으로 근사한다.

\nabla^2 f(\mathbf{x}) \approx \mathbf{J}(\mathbf{x})^T \mathbf{J}(\mathbf{x})

여기서 \mathbf{J}(\mathbf{x}) = \frac{\partial \mathbf{r}}{\partial \mathbf{x}} \in \mathbb{R}^{m \times n}은 자코비안 행렬이다. 가우스-뉴턴 스텝은 정규 방정식(normal equation)을 풀어 얻는다.

\mathbf{J}_k^T \mathbf{J}_k \Delta \mathbf{x}_k = -\mathbf{J}_k^T \mathbf{r}_k

이는 로봇공학에서 관측 모델이 비선형인 경우의 상태 추정, 센서 캘리브레이션 등에 광범위하게 사용된다. \mathbf{J}_k^T \mathbf{J}_k는 항상 양의 반정치이므로, 이차 항의 무시가 정당화되는 한 안정적인 수렴을 보인다.

5. 레벤버그-마쿼트법

가우스-뉴턴법의 수렴 영역을 확장하기 위하여, 정규화 항을 추가한 레벤버그-마쿼트(Levenberg-Marquardt)법이 사용된다.

(\mathbf{J}_k^T \mathbf{J}_k + \mu_k \mathbf{I}) \Delta \mathbf{x}_k = -\mathbf{J}_k^T \mathbf{r}_k

여기서 \mu_k > 0은 감쇠 파라미터(damping parameter)이다. \mu_k가 크면 경사 하강법에 가까워지고, \mu_k가 작으면 가우스-뉴턴법에 가까워진다. 선형대수학적으로, \mu_k \mathbf{I}를 더하는 것은 \mathbf{J}_k^T \mathbf{J}_k의 모든 고유값을 \mu_k만큼 이동시켜 양의 정치성을 보장하는 효과가 있다.

\lambda_i(\mathbf{J}_k^T \mathbf{J}_k + \mu_k \mathbf{I}) = \lambda_i(\mathbf{J}_k^T \mathbf{J}_k) + \mu_k > 0

6. 로봇공학에서의 적용 사례

6.1 역기구학의 수치 해법

로봇 팔의 역기구학 문제에서, 원하는 말단 장치(end-effector) 위치 \mathbf{p}_d와 현재 위치 \mathbf{p}(\mathbf{q})의 오차를 최소화하는 관절 변수 \mathbf{q}를 구한다. 가우스-뉴턴 갱신은 다음과 같다.

\Delta \mathbf{q} = \mathbf{J}^{\dagger}(\mathbf{q}) (\mathbf{p}_d - \mathbf{p}(\mathbf{q}))

여기서 \mathbf{J}^{\dagger}는 자코비안의 유사 역행렬(pseudoinverse)이다. 특이 형상(singular configuration) 근방에서는 감쇠 최소 제곱(damped least squares)을 적용한다.

\Delta \mathbf{q} = \mathbf{J}^T (\mathbf{J}\mathbf{J}^T + \mu^2 \mathbf{I})^{-1} (\mathbf{p}_d - \mathbf{p}(\mathbf{q}))

6.2 SLAM 최적화

동시 위치 추정 및 지도 작성(SLAM)의 백엔드 최적화는 비선형 최소 제곱 문제로 정식화된다. 로봇 자세와 랜드마크 위치를 포함하는 상태 벡터 \mathbf{x}에 대하여 가우스-뉴턴법을 적용하면, 정보 행렬 \mathbf{H} = \mathbf{J}^T \mathbf{J}는 희소 행렬(sparse matrix)이 된다. 이 희소 구조를 활용하여 촐레스키 분해의 계산량을 크게 줄일 수 있으며, 변수 순서(variable ordering)가 희소성 보존에 중요한 역할을 한다.

7. 경사 하강법과 뉴턴법의 비교

뉴턴법은 아핀 불변(affine invariant)이라는 중요한 성질을 가진다. 즉, 변수를 아핀 변환 \mathbf{x} = \mathbf{T}\mathbf{y}로 바꾸어도 뉴턴 스텝의 기하학적 경로가 변하지 않는다. 반면 경사 하강법은 좌표계에 의존한다.

8. 참고 문헌

• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
• Boyd, S., & Vandenberghe, L. (2004). Convex Optimization. Cambridge University Press.
• Grisetti, G., Kümmerle, R., Stachniss, C., & Burgard, W. (2010). A tutorial on graph-based SLAM. IEEE Intelligent Transportation Systems Magazine, 2(4), 31–43.
• Siciliano, B., Sciavicco, L., Villani, L., & Oriolo, G. (2009). Robotics: Modelling, Planning and Control. Springer.
• Shewchuk, J. R. (1994). An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Carnegie Mellon University.

v 0.1