共轭梯度法（CG）是解决下式的多元线性系统的一个优化方法
A x = b , \mathbf{A} \boldsymbol{x} = \boldsymbol{b}, A x = b , 其中，矩阵 A \mathbf{A} A 对称正定 条件。
共轭向量
如果两个向量 u \boldsymbol{u} u v \boldsymbol{v} v
u T A v = 0 , \boldsymbol{u}^T \mathbf{A} \boldsymbol{v} = 0, u T A v = 0 , 那么我们说 u \boldsymbol{u} u v \boldsymbol{v} v A \mathbf{A} A
我们也可以基于此定义一个内积：
⟨ u , v ⟩ A = u T A v . \langle \boldsymbol{u}, \boldsymbol{v} \rangle_\mathbf{A} = \boldsymbol{u}^T \mathbf{A} \boldsymbol{v}. ⟨ u , v ⟩ A = u T A v . 可以验证，它满足内积的条件。
闭式解
假设我们有一个向量集合 { p 1 , p 2 , … , p n } \{ \boldsymbol{p}_1, \boldsymbol{p}_2, \dots, \boldsymbol{p}_n \} { p 1 , p 2 , … , p n } i ≠ j i \neq j i = j
⟨ p i , p j ⟩ A = 0 \langle \boldsymbol{p}_i, \boldsymbol{p}_j \rangle_\mathbf{A} = 0 ⟨ p i , p j ⟩ A = 0 因为 A \mathbf{A} A { p 1 , p 2 , … , p n } \{ \boldsymbol{p}_1, \boldsymbol{p}_2, \dots, \boldsymbol{p}_n \} { p 1 , p 2 , … , p n } R n \mathbb{R}^n R n x ∗ \boldsymbol{x}^* x ∗ x ∗ \boldsymbol{x}^* x ∗
x ∗ = α i p i . \boldsymbol{x}^* = \alpha_i \boldsymbol{p}^i. x ∗ = α i p i . 因此，我们有
A x ∗ = α i A p i . \mathbf{A} \boldsymbol{x}^* = \alpha_i \mathbf{A} \boldsymbol{p}^i. A x ∗ = α i A p i . 上式左乘 p k \boldsymbol{p}_k p k
α i ⟨ p k , p i ⟩ A = α k ⟨ p k , p k ⟩ A = p k b . \alpha_i \langle \boldsymbol{p}_k, \boldsymbol{p}^i \rangle_\mathbf{A} = \alpha_k \langle \boldsymbol{p}_k, \boldsymbol{p}_k \rangle_\mathbf{A} = \boldsymbol{p}_k \boldsymbol{b}. α i ⟨ p k , p i ⟩ A = α k ⟨ p k , p k ⟩ A = p k b . 因此，α i \alpha_i α i
α i = p i T b ⟨ p i , p i ⟩ A \alpha_i = \frac{\boldsymbol{p}_i^T \boldsymbol{b}}{\langle \boldsymbol{p}_i, \boldsymbol{p}_i \rangle_\mathbf{A}} α i = ⟨ p i , p i ⟩ A p i T b 迭带求解
实践中，基于闭式解求这个问题可能消耗过多的时间，我们往往希望能够避免这个问题。思路的关键是仅仅使用少数的 p k \boldsymbol{p}_k p k x ∗ \boldsymbol{x}^* x ∗ p k \boldsymbol{p}_k p k
下面是一个无约束的二次规划（QP）问题：
min f ( x ) = 1 2 x T A x − b T x . \min f(\boldsymbol{x}) = \frac{1}{2} \boldsymbol{x}^T \mathbf{A} \boldsymbol{x} - \boldsymbol{b}^T \boldsymbol{x}. min f ( x ) = 2 1 x T A x − b T x . 对变量求导，可以得到上面这个优化问题的解满足
A x = b . \mathbf{A} \boldsymbol{x} = \boldsymbol{b}. A x = b . 这个问题可以基于梯度下降法来求解，其中梯度为
Δ x = − ∇ f ( x ) = b − A x . \Delta \boldsymbol{x} = -\nabla f (\boldsymbol{x}) = \boldsymbol{b} - \mathbf{A} \boldsymbol{x}. Δ x = − ∇ f ( x ) = b − A x . 在第一次迭代时，第一个基 p 1 \boldsymbol{p}_1 p 1 p 1 = b − A x 0 \boldsymbol{p}_1 = \boldsymbol{b} - \mathbf{A} \boldsymbol{x}_0 p 1 = b − A x 0 闭式解 ，我们可以求得和第一个基关联的 α 1 \alpha_1 α 1
这个迭代和解决无约束优化问题的梯度下降法的第一次迭代完全相同。在梯度下降法中，我们首先基于梯度计算得到下降的方向，然后用先搜索（line search）来寻找最佳的步长。这说明了 p k \boldsymbol{p}_k p k x 1 = x 0 − α 1 ∇ f ( x 0 ) \boldsymbol{x}_1 = \boldsymbol{x}_0 - \alpha_1 \nabla f(\boldsymbol{x}_0) x 1 = x 0 − α 1 ∇ f ( x 0 )
在后面的迭代中，CG 和梯度下降法开始不同。在梯度下降中，每次迭代都是选择梯度为下降方向；相反，在 CG 的第 k k k p k = b − A x k − 1 \boldsymbol{p}_k = \boldsymbol{b} - \mathbf{A} \boldsymbol{x}_{k-1} p k = b − A x k − 1 A \mathbf{A} A
r k = b − A x k p k = r k − ∑ i < k ⟨ r k , p i ⟩ A ⟨ p i , p i ⟩ A p i . \begin{align*}
\boldsymbol{r}_k &= \boldsymbol{b} - \mathbf{A} \boldsymbol{x}_{k} \\
\boldsymbol{p}_k &= \boldsymbol{r}_k - \sum_{i < k} \frac{\langle \boldsymbol{r}_k, \boldsymbol{p}_i \rangle_\mathbf{A}}{\langle \boldsymbol{p}_i, \boldsymbol{p}_i \rangle_\mathbf{A}}\boldsymbol{p}_i.
\end{align*} r k p k = b − A x k = r k − i < k ∑ ⟨ p i , p i ⟩ A ⟨ r k , p i ⟩ A p i . CG 法的一个特别的性质是它必定在第 n n n x ∗ \boldsymbol{x}^* x ∗
Line search 法和和 CG 法计算 α k \alpha_k α k
在第 k k k α k \alpha_k α k 闭式解 中的公式计算 α k \alpha_k α k
arg min α k f ( x k + α k p k ) , \underset{\alpha_k}{\arg \min} ~ f(\boldsymbol{x}_k + \alpha_{k} \boldsymbol{p}_{k}), α k arg min f ( x k + α k p k ) , 对 f f f α k \alpha_k α k
∂ f ∂ α k = 0 ⇒ α k = p k T ( b − A x k ) ⟨ p k , p k ⟩ A \begin{align*}
\frac{\partial f}{\partial \alpha_k} = 0 && \Rightarrow && \alpha_k = \frac{\boldsymbol{p}_{k}^T(\boldsymbol{b} - \mathbf{A} \boldsymbol{x}_{k})}{\langle \boldsymbol{p}_{k}, \boldsymbol{p}_{k} \rangle_\mathbf{A}}
\end{align*} ∂ α k ∂ f = 0 ⇒ α k = ⟨ p k , p k ⟩ A p k T ( b − A x k ) 注意，因为 p i \boldsymbol{p}_i p i A \mathbf{A} A
p k T A x k = p k T A ∑ i = 0 k x i = p k T A x 0 . \boldsymbol{p}_k^T \mathbf{A} \boldsymbol{x}_{k} = \boldsymbol{p}_k^T \mathbf{A} \sum_{i=0}^{k} \boldsymbol{x}_i = \boldsymbol{p}_k^T \mathbf{A} \boldsymbol{x}_0. p k T A x k = p k T A i = 0 ∑ k x i = p k T A x 0 . 因此，
α k = p k T ( b − A x k ) ⟨ p k , p k ⟩ A = p k T ( b − A x 0 ) ⟨ p k , p k ⟩ A , \alpha_k = \frac{\boldsymbol{p}_{k}^T(\boldsymbol{b} - \mathbf{A} \boldsymbol{x}_{k})}{\langle \boldsymbol{p}_{k}, \boldsymbol{p}_{k} \rangle_\mathbf{A}} = \frac{\boldsymbol{p}_{k}^T(\boldsymbol{b} - \mathbf{A} \boldsymbol{x}_{0})}{\langle \boldsymbol{p}_{k}, \boldsymbol{p}_{k} \rangle_\mathbf{A}}, α k = ⟨ p k , p k ⟩ A p k T ( b − A x k ) = ⟨ p k , p k ⟩ A p k T ( b − A x 0 ) , 这和 闭式解 中的公式一致。
下面是基于 Python 的简单的 CG 法的实现。
def conjugate_gradient ( A , b ): # solving the problem of Ax = b # A should be *positive symmetric*. n = A.shape[ 0 ] x = np. zeros_like (b) xs = [] for i in range (n): r = b - A @ x p = r - sum ([(r @ A @ x) / (x @ A @ x) * x for x in xs]) alpha = (b @ p) / (p @ A @ p) xs. append (alpha * p) x = x + xs[ - 1 ] return x, xs 需要注意的是，上面的代码并不高效。利用其它的性质，我们可以写出 更高效的实现 ，其中使用了更高效的计算 p k \boldsymbol{p}_k p k
Newton-CG 法
在解决非线性优化问题的牛顿法中，CG 可以用来解决下面的线性系统的近似：
H k Δ x n t = − ∇ f ( x ) . \mathbf{H}_k \Delta \boldsymbol{x}_{\mathrm{nt}} = - \nabla f(\boldsymbol{x}). H k Δ x nt = − ∇ f ( x ) . 使用 CG 法的牛顿法称为 Newton-CG 法。
和 PLS 的关系
可以证明，PLS 各个主元的系数和 CG 中的一致。
