conjugate gradient method

发表于   |   分类于   |  

Conjugate gradient method， 类似于坐标梯度下降，2次下降的方向不会相互干扰。

线性函数

线性函数的 conjugate gradient method 很容易理解，所以我们从线性函数开始讲起。假设我们的优化目标是
$\min\phi(x) = \frac{1}{2}x^TAx-b^Tx$
那么我们必然需要求解 $\nabla\phi(x)=Ax-b$ 。令 $r_k = Ax_k-b$

先讲讲 conjugacy

要理解 conjugate gradient method，自然先得理解 conjugacy 是什么。对于一组向量来说，我们说其关于对称矩阵 $A$ conjugate 如果 $p_i^TAp_j=0\quad i\neq j$ 。很容易发现这些向量必然也是线性独立的。

对于这样一组n维向量 $\{p_1,p_2...p_n\}$ ，如果我们令 $x_{k+1}=x_k+\alpha_kp_k$，那么 $x_n$ 可以表征整个n维向量空间。

令 $\alpha_k=-\dfrac{r^T_kp_k}{p^T_kAp_k}$(就steepest descent中的步长) ，那么上面的方法在n步后必然可以收敛到最优解。

CG算法

那么现在的问题是，我们如何构建出这样一套向量？我们介绍CG算法用于产生向量。CG算法如下：

  1. given $x_0$, set $r_0=Ax_0,p_0=-r_0$
  2. while $r_k\neq0$
    • $\alpha_k=\dfrac{r_k^Tr_k}{p_k^TAp_k}$
    • $x_{k+1}=x_k+\alpha_kp_k$
    • $r_{k+1} = r_k+\alpha_kAp_k$
    • $\beta_{k+1}=\dfrac{r_{k+1}^Tr_{k+1}}{r_k^Tr_k}$
    • $p_{k+1}=-r_{k+1}+\beta_{k+1}p_k$

收敛速度

如果 $A$ 有r个独立的特征根，可以证明CG算法可以在r步内收敛。其收敛速度为 linear， 但是收敛速度仍然和 condition number 密切相关。

preconditioning

因为收敛速度和 condition number 密切相关，所以仍然可以通过 乘以 $C$ 去改变 condition number， numerical optimization中将这个过程称为 preconditioning

非线性函数

Fletcher-Reeve method

  1. given $x_0$, $f_0=f(x_0), \nabla f_0=\nabla f(x_0), p_0=-\nabla f_0$
  2. while $\nabla f_0\neq 0$
    • compute $\alpha_k$， $x_{k+1}=x_k+\alpha_kp_k$
    • $\beta^{FR}_{k+1} = \dfrac{\nabla^T f_{k+1}\nabla f_{k+1}}{\nabla^T f_{k}\nabla f_{k}}$
    • $p_{k+1}=-\nabla f_{k+1}+\beta^{FR}_{k+1}p_k$

在这里，为了保证会产生下降的方向，$\alpha$ 必须满足 strict Wolfe condition ，即
$$f(x_k+\alpha p_k)\le f(x_k)+c_1\alpha\nabla f_k^Tp_k\\ |\nabla f(x_k+\alpha_kp_k)^Tp_k|\le c_2|\nabla f_kp_k|$$
不过 $0<c_1<c_2<\frac{1}{2}$ 。

FR method 的一些变化版本

对于 FR 算法的修改大都集中于 $\beta$ 的计算上。需要注意的是，我们只要保证当 $k>2$ 时， $|\beta_k|<\beta^{FR}_{k}$ 就可以保证全局收敛

PR

$\beta_{k+1}^{PR} = \dfrac{\nabla f_{k+1}^T(\nabla f_{k+1}-\nabla f_{k})}{\|\nabla f_k\|^2}$

经验表示 PR 似乎比 FR 更高效、健壮。但是对于PR来说， Wolfe condition 并不能保证每次迭代都处于下降方向。如果我们将 $\beta$ 的更新修改为
$\beta_{k+1}^+ = \max\{\beta_{k+1}^{PR}, 0\}$
那么对 Wolfe condition 做些微小的修改就可以保证下降的方向。我们将该算法称为 PR+

HS

$\beta^{HS} = \dfrac{\nabla f_{k+1}^T(\nabla f_{k+1}-\nabla f_{k})}{(\nabla f_{k+1}-\nabla f_{k})^Tp_k}$

PR-FR

$$\beta_k=\begin{cases} -\beta_k^{FR} & \text{if } \beta_k^{PR}<-\beta_k^{FR}\\ \beta_k^{PR} & \text{if } |\beta_k^{PR}|\le\beta_k^{FR}\\ \beta_k^{FR} & \text{if } \beta_k^{PR}>\beta_k^{FR} \end{cases}$$

restart

在处理非线性问题时，我们可以每n步就将 $\beta$ 设置为0。这被称为 restart ，相当于我们在当前步进行 steepest descent。这样的话，历史信息被抹去，相当于我们从当前开始重新做 conjugate gradient 。

对于每个函数的极值点来说，必然存在一个小的邻域，函数在该邻域内类似于二次函数。如果我们踏入邻域之后抹去历史信息，那么必然可以获得更快的迭代速度。似乎可以证明restart的收敛速度为quadratic。

当时实际过程中，如果用 restart ，那么 n 都会被设为一个相当大的值，基本不可能迭代那么多次。所以一般情况下不会为了收敛速度而进行 restart。当然，连续两次迭代的向量基本不正交的情况下可以进行 restart。 这可以通过 $\dfrac{|\nabla f_k^T\nabla f_{k-1}|}{\|\nabla f_k\|^2} \ge v$ 进行测试。v一般取0.1

收敛速度

对于 PR 来说，有下面不等式成立：
$-\dfrac{1}{1-c_2}\le\dfrac{|\nabla f_k^Tp_{k}|}{\|\nabla f_k\|^2}\le \dfrac{2c_2-1}{1-c_2}$

所以
$\cos\theta_k = \dfrac{\nabla f_k^Tp_{k}}{\|\nabla f_k\|\|p_{k}\|} \in(\dfrac{1- 2c_2}{1-c_2}\dfrac{\|\nabla f_k\|}{\|p_k\|},\dfrac{1}{1-c_2}\dfrac{\|\nabla f_k\|}{\|p_k\|})$
如果 $p_k$ 和 $\nabla f_k$ 正交，那么我们必然无法获得好的下降方向。这种情况下， $\cos\theta_k$ 基本为0， 故 $\|\nabla f_k\| \ll \|p_k\|，x_{k+1}\approx x_k，\nabla f_{k+1}\approx\nabla f_{k}$，因此 $\beta_{k+1}^{FR} \approx 1, p_{k+1}\approx p_k$。这种情况下 FR 很难有改进；而PR，HS就要好得多。

最后，书中对一些实际问题跑了 PR， FR， PR+，有些问题上，三者的差距并不明显。这里就不贴出来了，有兴趣的可以自己去看下