机器学习： 共轭梯度算法（PCG）

今天介绍数值计算和优化方法中非常有效的一种数值解法，共轭梯度法。我们知道，在解大型线性方程组的时候，很少会有一步到位的精确解析解，一般都需要通过迭代来进行逼近，而 PCG 就是这样一种迭代逼近算法。

我们先从一种特殊的线性方程组的定义开始，比如我们需要解如下的线性方程组：

Ax=b$$\mathbf{A}\mathbf{x}=\mathbf{b}$$

这里的 A(n×n)$\mathbf{A}(n\times n)$ 是对称，正定矩阵， b(n×1)$\mathbf{b}(n\times 1)$ 同样也是已知的列向量，我们需要通过 A$\mathbf{A}$ 和 b$\mathbf{b}$ 来求解 x(n×1)$\mathbf{x}(n\times 1)$, 这其实是我们熟知的一些线性系统的表达式。

直接求解

首先，我们来看一种直观的解法，我们定义满足如下关系的向量为关于 矩阵 A$\mathbf{A}$ 的共轭向量，

uTAv=0$${\mathbf{u}}^{\mathsf{T}}\mathbf{A}\mathbf{v}=0$$

因为矩阵 A$\mathbf{A}$ 是对称正定矩阵，所以矩阵 A$\mathbf{A}$ 定义了一个内积空间：

⟨u,v⟩A:=⟨Au,v⟩=⟨u,ATv⟩=⟨u,Av⟩=uTAv$$⟨\mathbf{u},\mathbf{v}{⟩}_{\mathbf{A}}:=⟨\mathbf{A}\mathbf{u},\mathbf{v}⟩=⟨\mathbf{u},{\mathbf{A}}^{\mathsf{T}}\mathbf{v}⟩=⟨\mathbf{u},\mathbf{A}\mathbf{v}⟩={\mathbf{u}}^{\mathsf{T}}\mathbf{A}\mathbf{v}$$

基于此，我们可以定义一组向量 P$P$

P={p1,…,pn}$$P=\left\{{\mathbf{p}}_1,\dots ,{\mathbf{p}}_n\right\}$$

其中的向量 p1${\mathbf{p}}_1$ , p2${\mathbf{p}}_2$, … , pn${\mathbf{p}}_n$ 都是互为共轭的，那么 P$P$ 构成了 Rn${\mathbb{R}}^n$ 空间的一个基，上述方程的解 x∗${\mathbf{x}}_{\ast }$ 可以表示成 P$P$ 中向量的线性组合：

x∗=∑i=1nαipi$${\mathbf{x}}_{\ast }=\sum _{i=1}^n{\alpha }_i{\mathbf{p}}_i$$

根据上面的表达式，我们可以得到：

Ax∗=∑i=1nαiApipTkAx∗=∑i=1nαipTkApi(Multiply left by pTk)pTkb=∑i=1nαi⟨pk,pi⟩A(Ax∗=b and ⟨u,v⟩A=uTAv)⟨pk,b⟩=αk⟨pk,pk⟩A(uTv=⟨u,v⟩ and ∀i≠k:⟨pk,pi⟩A=0)$$\begin{gathered} \mathbf{A}{\mathbf{x}}_{\ast }=\sum _{i=1}^n{\alpha }_i\mathbf{A}{\mathbf{p}}_i \\ {\mathbf{p}}_k^{\mathsf{T}}\mathbf{A}{\mathbf{x}}_{\ast }=\sum _{i=1}^n{\alpha }_i{\mathbf{p}}_k^{\mathsf{T}}\mathbf{A}{\mathbf{p}}_i\text{(Multiply left by }{\mathbf{p}}_k^{\mathsf{T}}\text{)} \\ {\mathbf{p}}_k^{\mathsf{T}}\mathbf{b}=\sum _{i=1}^n{\alpha }_i{⟨{\mathbf{p}}_k,{\mathbf{p}}_i⟩}_{\mathbf{A}}(\mathbf{A}{\mathbf{x}}_{\mathbf{\ast }}=\mathbf{b}\text{ and }⟨\mathbf{u},\mathbf{v}{⟩}_{\mathbf{A}}={\mathbf{u}}^{\mathsf{T}}\mathbf{A}\mathbf{v}) \\ ⟨{\mathbf{p}}_k,\mathbf{b}⟩={\alpha }_k{⟨{\mathbf{p}}_k,{\mathbf{p}}_k⟩}_{\mathbf{A}}({\mathbf{u}}^{\mathsf{T}}\mathbf{v}=⟨\mathbf{u},\mathbf{v}⟩\text{ and }\mathrm{\forall }i\ne k:{⟨{\mathbf{p}}_k,{\mathbf{p}}_i⟩}_{\mathbf{A}}=0) \end{gathered}$$

这意味着：

αk=⟨pk,b⟩⟨pk,pk⟩A$${\alpha }_k=\frac{⟨{\mathbf{p}}_k,\mathbf{b}⟩}{{⟨{\mathbf{p}}_k,{\mathbf{p}}_k⟩}_{\mathbf{A}}}$$

所以，如果我们要直接求解的，可以先对矩阵 A$\mathbf{A}$ 进行特征值分解，求出一系列的共轭向量，然后求出系数，最后可以得到方程的解 x∗${\mathbf{x}}_{\mathbf{\ast }}$

迭代求解

上面的方法已经说明，x∗${\mathbf{x}}_{\ast }$ 是一系列共轭向量 p$\mathbf{p}$ 的线性组合，学过 PCA 的都知道，可以用前面占比高的向量组合进行逼近，而不需要把所有的向量都组合到一起，PCG 也是用到了这种思想，通过仔细的挑选共轭向量 p$\mathbf{p}$ 来重建方程的解 x∗${\mathbf{x}}_{\mathbf{\ast }}$。

我们先来看下面的一个方程：

f(x)=12xTAx−xTb,x∈Rn$$f(\mathbf{x})=\frac{1}{2}{\mathbf{x}}^{\mathsf{T}}\mathbf{A}\mathbf{x}-{\mathbf{x}}^{\mathsf{T}}\mathbf{b},\mathbf{x}\in {\mathbf{R}}^n$$

对上面的方程求导，我们可以得到：

D2f(x)=A$${\mathrm{D}}^{2}f(\mathbf{x})=\mathbf{A}$$

Df(x)=Ax−b$$\mathrm{D}f(\mathbf{x})=\mathbf{A}\mathbf{x}-\mathbf{b}$$

可以看到，方程的一阶导数就是我们需要解的线性方程组，令一阶导数为 0，那么我们需要解的就是这样一个线性方程组了。

假设我们随机定义 x$\mathbf{x}$ 的一个初始向量为 x0${\mathbf{x}}_{\mathbf{0}}$，那么我们可以定义第一个共轭向量为 p0=b−Ax0${\mathbf{p}}_0=\mathbf{b}-\mathbf{A}{\mathbf{x}}_0$, 后续的基向量都是和梯度共轭的，所以称为共轭梯度法。

下面给出详细的算法流程：

而 preconditioned conjugate gradient method 与共轭梯度法的不同之处在于预先定义了一个特殊矩阵 M$\mathbf{M}$：

参考来源：wiki 百科

https://en.wikipedia.org/wiki/Conjugate_gradient_method#The_preconditioned_conjugate_gradient_method