Solving Linear System Efficiently (1) - Conjugate Gradient Algorithm
본 글은 1차(선형) 행렬식 $Ax=b$ 문제(즉, 선형 시스템)를 매우 빠르고 효율적이게 풀기 위한 방법을 다룹니다. 본 선형 시스템은 거의 대부분의 수치 해석에서 사용되는 방법이며, 계산 측면에서 매우 중요한 기법입니다.
이번 글에서는 Conjugate Gradient Algorithm이 Unconstrained Quadratic Programming에서 변수의 개수 $n$번만큼의 iteration으로 수렴하는지를 증명합니다.
Conjugate Gradient
\[\begin{aligned} r_0 &= b - A x_0 \\ p_0 &= r_0 \\ \\ \text{for } k &= 0, 1, \dots, n-1: \\ \alpha_k &= \frac{r_k^T r_k}{p_k^T A p_k} \\ x_{k+1} &= x_k + \alpha_k p_k \\ r_{k+1} &= r_k - \alpha_k A p_k \\ \beta_k &= \frac{r_{k+1}^T r_{k+1}}{r_k^T r_k} \\ p_{k+1} &= r_{k+1} + \beta_k p_k \end{aligned}\]
Conjugate Gradient 알고리즘은 위처럼 구성되어 있습니다. 잔차 $r_k$를 줄이기 위한 방향 $p_k$과 step size $\alpha_k$를 구한 후 $x_{k+1}$를 업데이트하는 방식입니다. 이때, 모든 $k$에 대해 $p_k$끼리는 A-Conjugate 성질을 만족합니다.
A-conjugate
A-conjugate는 단순한 직교랑은 다릅니다. A행렬에 대한 직교성을 뜻합니다. 수식적으로는
\[p_i A p_j = 0\]을 만족할 때, $p_i$와 $p_j$는 A-conjugate 관계에 있다고 합니다. A-conjugate는 Quadratic Function $\frac{1}{2}xAx^T - bx$에서 $p_j$의 방향의 변화가 있을 때, 이 벡터의 크기가 어떤 값이던지 $p_i$ 방향의 변화는 동일하다. 라고 해석할 수 있습니다.
증명은 간단합니다. 방향에 대한 gradient 정의($\text{Grad}_v = v \cdot \nabla f(x)$)에 의해
\[v \cdot \nabla (\frac{1}{2}xAx^T - bx) = v(Ax-b) = vAx - vb\]가 됩니다. 이때, $-vb$는 상수이므로, $vAx$를 0으로 만드는 벡터는 크기가 어쨌건 변화량은 동일합니다. 이제 conjugate의 정의를 했으니, 증명 과정에 들어가겠습니다. 증명과정은 크게 세 단계로 나뉩니다.
- 해의 유일성 증명
- 업데이트 방향 $p_k$의 A-conjugate 증명
- Step Size 값이 해를 결정함을 증명
위 세 증명을 차례대로 다뤄보겠습니다.
Uniqueness of Solution
이 단계에서 보여야 할 증명은 다음과 같습니다.
가정 : 만약 A가 Positive Definite Matrix이면, A-conjugate인 $n$개의 벡터들은 모두 독립이다.
이를 보이기 위해
\[\sum_{i=0}^{N-1} c_i p_i = 0\]위 문제의 $c_i$의 유일해가 0임을 증명하면 됩니다. 이 역시 A-conjugate의 정의를 통해 증명 가능합니다. 양변에 $p_k A$를 곱하면,
\[\sum_{i=0}^{N-1} c_i p_k A p_i = 0\]이 되고, 이때, A-conjugate 정의에 의해 식은 $c_k p_k A p_k = 0$ 만 남겨지게 되죠. $A$ 행렬이 Positive Semidefinite Matrix이기 때문에 $c_k=0$이 유일한 값으로 결정됩니다. 이렇게 증명을 보일 수 있습니다.
이 증명이 필요한 이유는 $Ax=b$의 해가 $x^* = \sum_{i=0}^{N-1} c_i p_k A p_i$ 꼴로 유일하게 나타내짐을 보이기 위함입니다.
A-conjugate of Update Vectors
본 성질을 증명하기 위한 귀납 과정은 아래와 같습니다.
\[\forall i < k: \quad r_k^T r_i = 0, \quad p_k^T A p_i = 0\]잔차의 직교성($r_k^T r_i = 0$) 성질 또한 증명 과정에 필수적입니다. 먼저 이부터 보이겠습니다. 잔차의 업데이트 규칙은 다음과 같습니다.
\[r_{k+1} = r_k - \alpha_k A p_k\]이때, 양변에 $r_i$를 내적하여 전개합니다 ($i \le k$).
\[r_{k+1}^T r_i = r_k^T r_i - \alpha_k p_k^T A r_i\]이때, i=k 인 경우,
\[p_k^T A r_k = p_k^T A (p_k - \beta_k p_{k-1}) = p_k^T A p_k\] \[\therefore r_{k+1}^T r_k = r_k^T r_k - \frac{r_k^T r_k}{p_k^T A p_k} (p_k^T A p_k) = 0\]이 성립하며, $i < k$ 인 경우
\[r_k^T r_i = 0 \quad (\text{Hyp})\] \[p_k^T A r_i = p_k^T A (p_i - \beta_i p_{i-1}) = 0 \quad (\text{Hyp})\] \[\therefore r_{k+1}^T r_i = 0 - 0 = 0\]가 성립하여 모든 $i \le k$에 대해 $r_{k+1}^T r_i = 0$ 입니다.
이제 이 잔차의 직교성을 통해 A-conjugate($p_{k+1} \perp_A p_i$)를 증명하겠습니다. 업데이트 방향 $p_k$의 규칙은 다음과 같습니다.
\[p_{k+1} = r_{k+1} + \beta_{k+1} p_k\]양변에 $A p_i$를 내적하여 전개합니다 ($i \le k$).
\[p_{k+1}^T A p_i = r_{k+1}^T A p_i + \beta_{k+1} p_k^T A p_i\]이때, i=k 인 경우, $\beta_{k+1}$의 정의에 의해 직접적으로 성립합니다. $\beta_{k+1}$는 $(r_{k+1} + \beta_{k+1} p_k)^T A p_k = 0$을 직접 전개하여 얻어집니다. i < k 인 경우, 위 식에 의해 두 번째 항은 소거됩니다.
\[p_k^T A p_i = 0 \implies p_{k+1}^T A p_i = r_{k+1}^T A p_i\]이때, 잔차 업데이트 식($A p_i = \frac{1}{\alpha_i}(r_i - r_{i+1})$)을 대입합니다.
\[r_{k+1}^T A p_i = \frac{1}{\alpha_i} (r_{k+1}^T r_i - r_{k+1}^T r_{i+1})\]위에서 증명한 잔차 직교성($r_{k+1} \perp r_{\text{all } \le k}$)에 의해 모두 0이 됩니다.
\[\therefore p_{k+1}^T A p_i = 0\]Step Size Determination and Optimality
Conjugate Gradient에서 Line Search를 시행했을때의 Step size는 아래와 같습니다.
\[\alpha_k = \frac{r_k^T r_k}{p_k^T A p_k}\]이는 단순히 $\frac{d}{d\alpha_k}f(x_k + \alpha_k p_k) = 0$ 조건으로부터 얻어집니다.
\[\frac{d}{d\alpha_k}f(x_k + \alpha_k p_k) = 0\] \[(Ax_{k+1} - b)^T p_k = -r_{k+1}^T p_k = 0\]잔차의 정의에 의해,
\[(r_k - \alpha_k A p_k)^T p_k = 0\] \[\alpha_k = \frac{p_k^T r_k}{p_k^T A p_k}\]를 얻을 수 있습니다.
이때, 잔차 식($r_{k+1} = r_k - \alpha_k A p_{k}$)으로 되돌아가서 양변에 $p_{k}^T$를 내적합니다.
\[p_{k}^T r_{k+1} = p_{k}^T r_k - \alpha_k p_{k}^T A p_{k}\]다시 구한 $\alpha_k$를 대입하면, $p_{k}^T r_{k+1} = 0$이 성립합니다. 이제, $p_k$에 대한 식 $p_k = r_k + \beta_{k-1}p_{k-1}$로 돌아온 후, 양변에 $r_k^T$를 내적하면
\[r_k^T p_k = r_k^T r_k + \beta_{k-1}r_k^T p_{k-1}\] \[r_k^T p_k = r_k^T r_k\]이 성립해
\[\alpha_k = \frac{p_k^T r_k}{p_k^T A p_k} = \frac{r_k^T r_k}{p_k^T A p_k}\]를 만족시킵니다.
그런데, $Ax = b$를 만족하는 $x^\ast$는 $n$개의 기저벡터의 합으로 표현할 수 있습니다. 위에서 얻은 $p_k$가 기저벡터이므로, $ x^\ast = x_k + \sum_{i=0}^{N-1} c_k p_k$ 으로 표현 가능합니다. 이때 $x_k$를 넘긴 후 양변에 $p_k^T A$를 곱해주면,
\[x^\ast - x_k = \sum_{i=0}^{N-1} c_k p_k\] \[p_k^T A (x^\ast - x_k) = c_k p_k^T A p_k\]A-conjugate 성질에 의해 위 식으로 정리 가능합니다. 이때의 계수 $c_k$를 다시 정리하면
\[c_k = \frac{p_k^T A (x^\ast - x_k)}{p_k^T A p_k} = \frac{p_k^T (b - Ax_k)}{p_k^T A p_k} = \frac{p_k^T r_k}{p_k^T A p_k}\]가 나오므로, 이전에 구한 Line search 결과와 동일합니다.
Conclusion
이 글에서 우리는 Conjugate Gradient Algorithm의 수렴성을 보이기 위해 세 가지 성질을 증명했습니다.
-
$Ax = b$ 문제 해의 유일성, 즉 기저벡터의 계수로 결정 가능하다는 점,
-
Update vector $p_k$의 독립성, 그리고 A-conjugate를 띄는 점,
-
그리고 이렇게 얻은 $p_k$ 벡터의 Line Search 값이 $x^\ast$를 만드는 $p_k$ 벡터의 계수인 점,
위 과정을 거쳐 Quadratic Programming에서 Conjugate Gradient Algorithm이 변수의 개수인 $n$번만에 최적해를 찾을 수 있다는 점을 증명했습니다.