7.85 켤레 그래디언트법

1. 최급경사법의 한계와 켤레 방향의 동기

최급경사법(steepest descent)에서 정밀 직선 탐색을 수행하면, 연속된 그래디언트가 직교하는 성질 \nabla f(\mathbf{x}_{k+1})^T \nabla f(\mathbf{x}_k) = 0을 갖는다. 이로 인해 이차 목적 함수의 등고선이 타원형인 경우, 반복열이 지그재그 패턴을 보이며 수렴이 극도로 느려진다. 조건수(condition number) \kappa = \lambda_{\max}/\lambda_{\min}이 큰 문제에서 최급경사법의 수렴률은 (\kappa - 1)/(\kappa + 1)에 비례하여 저하된다. 켤레 그래디언트법(conjugate gradient method)은 이전 탐색 방향의 정보를 활용하여 이러한 지그재그 현상을 제거하고, 이차 함수에 대해 최대 n번의 반복으로 정확한 해를 산출한다.

2. 켤레 방향의 정의

대칭 양정치 행렬 \mathbf{A} \in \mathbb{R}^{n \times n}에 대해, 벡터 집합 \{\mathbf{d}_0, \mathbf{d}_1, \ldots, \mathbf{d}_{n-1}\}이 다음을 만족하면 \mathbf{A}-켤레(conjugate)라 한다.

\mathbf{d}_i^T \mathbf{A} \mathbf{d}_j = 0, \quad \forall i \neq j

직교 조건 \mathbf{d}_i^T \mathbf{d}_j = 0의 일반화로, \mathbf{A} = \mathbf{I}이면 통상의 직교 조건으로 환원된다. \mathbf{A}-켤레 벡터들은 \mathbf{A}에 의해 정의되는 내적 \langle \mathbf{u}, \mathbf{v} \rangle_{\mathbf{A}} = \mathbf{u}^T\mathbf{A}\mathbf{v}에 대해 직교하며, 선형 독립이므로 \mathbb{R}^n의 기저를 형성한다.

3. 선형 켤레 그래디언트법

3.1 이차 함수에 대한 알고리즘

n차원 이차 함수 f(\mathbf{x}) = \frac{1}{2}\mathbf{x}^T\mathbf{A}\mathbf{x} - \mathbf{b}^T\mathbf{x} (\mathbf{A} \succ 0)의 최소화는 선형 연립 방정식 \mathbf{A}\mathbf{x} = \mathbf{b}를 푸는 것과 동치이다. 잔차(residual)를 \mathbf{r}_k = \mathbf{b} - \mathbf{A}\mathbf{x}_k = -\nabla f(\mathbf{x}_k)로 정의한다.

선형 켤레 그래디언트(CG) 알고리즘:

1. 초기점 \mathbf{x}_0, \mathbf{r}_0 = \mathbf{b} - \mathbf{A}\mathbf{x}_0, \mathbf{d}_0 = \mathbf{r}_0
2. k = 0, 1, 2, \ldots에 대해:
3. \quad \alpha_k = \frac{\mathbf{r}_k^T\mathbf{r}_k}{\mathbf{d}_k^T\mathbf{A}\mathbf{d}_k}
4. \quad \mathbf{x}_{k+1} = \mathbf{x}_k + \alpha_k \mathbf{d}_k
5. \quad \mathbf{r}_{k+1} = \mathbf{r}_k - \alpha_k \mathbf{A}\mathbf{d}_k
6. \quad \beta_{k+1} = \frac{\mathbf{r}_{k+1}^T\mathbf{r}_{k+1}}{\mathbf{r}_k^T\mathbf{r}_k}
7. \quad \mathbf{d}_{k+1} = \mathbf{r}_{k+1} + \beta_{k+1}\mathbf{d}_k
8. \quad \mathbf{r}_{k+1} = \mathbf{0}이면 종료

3.2 핵심 성질

선형 CG 알고리즘은 다음의 성질을 갖는다.

유한 종료성: 정확한 산술에서 최대 n번의 반복으로 정확한 해 \mathbf{x}^* = \mathbf{A}^{-1}\mathbf{b}에 도달한다.

켤레성: 생성된 탐색 방향이 \mathbf{A}-켤레이다.

\mathbf{d}_i^T \mathbf{A} \mathbf{d}_j = 0, \quad \forall i \neq j

잔차 직교성: 잔차 벡터들이 상호 직교한다.

\mathbf{r}_i^T \mathbf{r}_j = 0, \quad \forall i \neq j

확장 부분 공간 최적성: k번째 반복에서의 해 \mathbf{x}_k는 아핀 부분 공간 \mathbf{x}_0 + \text{span}\{\mathbf{d}_0, \ldots, \mathbf{d}_{k-1}\}에서의 최적해이다. 이 부분 공간은 크릴로프 부분 공간(Krylov subspace) \mathcal{K}_k(\mathbf{A}, \mathbf{r}_0) = \text{span}\{\mathbf{r}_0, \mathbf{A}\mathbf{r}_0, \ldots, \mathbf{A}^{k-1}\mathbf{r}_0\}과 일치한다.

3.3 수렴률

선형 CG의 수렴률은 \mathbf{A}의 조건수에 의존하며, k번째 반복에서의 오차는 다음과 같이 제한된다.

\lVert \mathbf{x}_k - \mathbf{x}^* \rVert_{\mathbf{A}} \leq 2 \left( \frac{\sqrt{\kappa} - 1}{\sqrt{\kappa} + 1} \right)^k \lVert \mathbf{x}_0 - \mathbf{x}^* \rVert_{\mathbf{A}}

여기서 \lVert \cdot \rVert_{\mathbf{A}} = \sqrt{(\cdot)^T\mathbf{A}(\cdot)}은 에너지 노름이다. 수렴률이 \kappa가 아닌 \sqrt{\kappa}에 의존하므로, 최급경사법 대비 현저히 빠른 수렴을 보인다.

4. 사전 조건화(Preconditioning)

조건수 \kappa가 큰 경우, 사전 조건자(preconditioner) \mathbf{M} \approx \mathbf{A}를 도입하여 \mathbf{M}^{-1}\mathbf{A}\mathbf{x} = \mathbf{M}^{-1}\mathbf{b}로 변환된 시스템을 풀면 수렴이 가속된다. 이상적으로 \mathbf{M} = \mathbf{A}이면 1회 반복으로 수렴하지만, \mathbf{M}^{-1}의 적용이 용이해야 하므로 근사가 필요하다. 불완전 촐레스키 분해(incomplete Cholesky factorization), 대각 사전 조건자(Jacobi preconditioner) 등이 널리 사용된다.

사전 조건화 CG(Preconditioned CG, PCG)에서 \beta의 갱신식은 다음과 같이 수정된다.

\beta_{k+1} = \frac{\mathbf{r}_{k+1}^T\mathbf{M}^{-1}\mathbf{r}_{k+1}}{\mathbf{r}_k^T\mathbf{M}^{-1}\mathbf{r}_k}

5. 비선형 켤레 그래디언트법

5.1 일반 비선형 함수로의 확장

비선형 목적 함수에 대해 선형 CG 알고리즘을 직접 적용할 수 없으므로, 이를 일반화한 비선형 켤레 그래디언트법이 사용된다. 탐색 방향의 갱신 규칙은 다음과 같다.

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

여기서 \beta_k의 계산 공식에 따라 여러 변형이 존재한다. \mathbf{g}_k = \nabla f(\mathbf{x}_k)로 표기하면 주요 공식은 다음과 같다.

5.2 플레처-리브스(Fletcher-Reeves, FR) 공식

\beta_k^{FR} = \frac{\mathbf{g}_k^T\mathbf{g}_k}{\mathbf{g}_{k-1}^T\mathbf{g}_{k-1}}

5.3 폴락-리비에르(Polak-Ribière, PR) 공식

\beta_k^{PR} = \frac{\mathbf{g}_k^T(\mathbf{g}_k - \mathbf{g}_{k-1})}{\mathbf{g}_{k-1}^T\mathbf{g}_{k-1}}

5.4 헤스테네스-슈티펠(Hestenes-Stiefel, HS) 공식

\beta_k^{HS} = \frac{\mathbf{g}_k^T(\mathbf{g}_k - \mathbf{g}_{k-1})}{\mathbf{d}_{k-1}^T(\mathbf{g}_k - \mathbf{g}_{k-1})}

이차 함수에서 정밀 직선 탐색을 사용하면 세 공식 모두 동일한 값을 산출한다. 비선형 함수에서는 성능이 다르며, PR과 HS 공식이 실용적으로 우수한 것으로 알려져 있다.

5.5 재시작(Restart) 전략

비선형 문제에서 켤레 방향의 품질은 반복이 진행됨에 따라 저하될 수 있다. 이를 방지하기 위해 주기적으로 탐색 방향을 최급경사 방향으로 재설정하는 재시작 전략이 사용된다. n번 반복마다 재시작하는 것이 가장 단순한 방식이며, \beta_k가 음수가 되는 경우 \beta_k = \max(\beta_k^{PR}, 0)으로 설정하는 PR+ 변형이 실용적이다. 이 변형은 자동적으로 재시작이 이루어지는 효과를 갖는다.

6. 계산 효율성

켤레 그래디언트법은 다음과 같은 계산 효율성을 갖는다.

• 저장 요구량: O(n). 현재 그래디언트, 이전 그래디언트, 탐색 방향만을 저장하면 된다. 헤시안 행렬(O(n^2))이나 그 근사를 저장할 필요가 없으므로, 대규모 문제에 적합하다.
• 반복당 계산량: O(n). 그래디언트 계산과 벡터 연산만 수행한다(선형 CG에서는 행렬-벡터 곱 \mathbf{A}\mathbf{d}_k가 추가).
• 수렴 속도: 최급경사법보다 현저히 빠르고, 준뉴턴법과 유사한 수준의 성능을 보인다.

이러한 특성으로 인해 켤레 그래디언트법은 결정 변수의 수가 매우 큰 대규모 최적화 문제에서 특히 유용하다.

7. 로봇 공학에서의 응용

대규모 선형 시스템의 해법: 로봇 동역학 시뮬레이션에서 발생하는 대규모 희소 선형 시스템 \mathbf{A}\mathbf{x} = \mathbf{b}를 사전 조건화 CG로 효율적으로 풀 수 있다. 특히 유한 요소 해석이나 접촉 역학에서 양정치 시스템이 빈번하게 나타난다.

궤적 최적화의 내부 해법: 순차적 이차 계획법(SQP)이나 뉴턴형 방법에서 뉴턴 방정식 \nabla^2 f(\mathbf{x}_k) \mathbf{d} = -\nabla f(\mathbf{x}_k)를 반복적으로 풀 때, 절단 뉴턴법(truncated Newton method)의 내부 해법으로 CG가 사용된다. 정확한 해가 아닌 근사 해를 수용함으로써 전체 계산 효율을 향상시킨다.

비선형 최소 제곱: SLAM 백엔드 최적화와 같은 대규모 비선형 최소 제곱 문제에서, 정규 방정식의 해를 CG로 구하여 가우스-뉴턴 스텝을 근사한다.

8. 참고 문헌

• Hestenes, M. R., & Stiefel, E. (1952). “Methods of Conjugate Gradients for Solving Linear Systems.” Journal of Research of the National Bureau of Standards, 49(6), 409–436.
• Fletcher, R., & Reeves, C. M. (1964). “Function Minimization by Conjugate Gradients.” The Computer Journal, 7(2), 149–154.
• Nocedal, J., & Wright, S. J. (2006). Numerical Optimization (2nd ed.). Springer.
• Shewchuk, J. R. (1994). An Introduction to the Conjugate Gradient Method Without the Agonizing Pain. Technical Report, Carnegie Mellon University.
• Golub, G. H., & Van Loan, C. F. (2013). Matrix Computations (4th ed.). Johns Hopkins University Press.

version: 1.0