共轭梯度法（Conjugate Gradient）是介于最速下降法与牛顿法之间的一个方法
- 仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，
- 避免了牛顿法需要存储和计算Hessian矩阵（占用空间大）并求逆的缺点
- 求解大型线性方程组或非线性最优化问题时常用且高效的方法
1 共轭方向法
设$G$为对称正定矩阵，若$d^T_mGd_n=0,\ m\neq n$ ，则称$d_m$和$d_n$为“G共轭”，共轭方向是“互不相关”的方向
共轭是正交的推广，$n$个共轭向量可以作为$n$维空间的非正交基，共轭向量间是线性无关的
共轭方向法的核心思路就是沿着每一个基的方向做直线搜索，并寻找到最小极值点
对于二次型目标函数，共轭方向法最多经过N步（N为向量维数）迭代，就可以到达极小值点——这种特性叫作二次收敛性（Quadratic Convergence），或称二次终止定理
当G有$r$个非零奇异值时，算法最多进行$r$次迭代就能达到最优点
共轭方向法步骤：
- 给定一个初始解$x_1\in R_n$ 和一组共轭方向${p_1,p_2,...,p_{n}}$，令迭代次数$k=1$
- 确定一个满足共轭条件以及下降条件的搜索方向$d_{k}$
- 其中共轭条件是指当前搜索方向与之前的搜索方向都是”共轭的“： $$d_{k}^TGd_i=0,i=1,2,...,k$$
- 而下降条件是指当前搜索方向要确保目标值可以下降（用$g_{k}$表示当前解对应的梯度）： $$g_{k}^Td_{k}<0$$
- 当$||d_{k}||\leq \epsilon$或迭代次数达到上限时，算法结束；否则进入步骤6
- 从点$x_k$出发，沿着方向$d_k$展开一维搜索，找到最优的步长$\lambda_k$： $$argmin_{\lambda_k}f(x_k+\lambda_kd_K)$$
- 更新坐标与迭代次数：$x_{k+1}=x_k+\lambda_k d_k,\ \ k=k+1$，并进入步骤2
一般使用Powell方法（原理较复杂，暂未展开）来构建n个线性无关、两两共轭的方向
微分法计算步长$\lambda_k$：
- 假设目标函数为正定二次函数：$f(x)=\frac{1}{2}x^TGx+b^Tx+c$
- 记$\phi(\lambda_k)=f(x_{k+1})=\frac{1}{2}(x_k+\lambda_k d_k)^TG(x_k+\lambda_k d_k)+b^T(x_k+\lambda_k d_k)+c$
- 则$\phi'(\lambda_k)=d_k^T G(x_k+\lambda_k d_k)+b^Td_k$，正定二次函数最优解对应着$\phi'(\lambda_k)=0$
- 上式化简后，即可得到步长$\lambda_k$的解析解： $$\lambda_k=-\frac{d_k^T \nabla f(x_{k})}{d_k^TG d_k}$$
最终的解析解与最速下降法非常像，二者底层存在一致性（正交 VS 共轭）
共轭方向法分析：
- 只需要计算一阶导数（梯度），不需要计算二阶导（Hessian矩阵）
- 最速下降法的搜索方向是正交的，而共轭方向法的搜索方向是共轭的
2 共轭梯度法
共轭梯度法实际上是一种特殊的共轭方向法，在搜索方向的选择上融合了梯度信息
共轭梯度法不再需要一次性得出一组共轭方向，而是根据迭代式计算出下一次的方向： $$d_{k}=-\nabla f(x_k)+\beta_k d_{k-1}$$
- 其中$-\nabla f(x_k)$表示目标函数$f$在点$x$的负梯度，即最速下降方向
- 为确保$d_k$与$d_{k-1}$满足共轭条件，即 $(-\nabla f(x_k)+\beta_k d_{k-1})^T G d_{k-1}=0$，所以 $\beta$ 可定义如下： $$\beta_k=\frac{\nabla f(x_k)^T G d_{k-1}}{d_{k-1}^T G d_{k-1}}$$
共轭梯度法步骤：
- 初始化$x_1$，设定允许的最小误差$\epsilon$，迭代次数$k=1$，$d_0=0$
- 对于第$k$次迭代，计算得出新的搜索方向：$d_{k}=-\nabla f(x_k)+\beta_k d_{k-1}$
- 当$||\nabla f(x_k)||\leq \epsilon$或迭代次数达到上限时，算法结束；否则进入步骤4
- 从点$x_k$出发，沿着方向$d_k$展开一维搜索，找到最优的步长$\lambda_k$： $$argmin_{\lambda_k}f(x_k+\lambda_kd_K)$$
- 更新坐标与迭代次数：$x_{k+1}=x_k+\lambda_k d_k,\ \ k=k+1$，并进入步骤2
共轭梯度法从某种意义上来说是最速下降法和共轭方向法的融合
最速下降法和共轭方向法的步长$\lambda_k$的解析解依然适用于共轭梯度法
3 非线性共轭梯度
当目标函数是高于二次的连续函数（即目标函数的梯度存在）时，其对应的解方程是非线性方程
非线性问题的目标函数可能存在局部极值（不再满足二次终止定理），虽然共轭梯度法依然适用，但此时共轭梯度法不能保证在$n$维空间内依靠$n$步搜索到达极值点，也不能确保收敛到的是全局极值
共轭梯度法的重启：
- 在非线性共轭梯度法中，共轭梯度法经常需要重启以找到极值点
- 重启意味着重新设定$\beta_k=0$，并选择最速下降方向（负梯度）开启新一轮的共轭梯度法
- 常用的重启判定策略：当连续两次的梯度值离正交很远时（即夹角偏离90度很大），进行一次重启
当目标函数较为复杂时，可能需要借助Hessian矩阵（计算成本高）进行局部线性化
对于非线性共轭梯度，矩阵$G$还可能是病态的，因此需要在迭代公式中剔除掉
常见的两种$\beta_k$的迭代公式替代为Fletcher-Reeves（FR）公式和Polak-Ribiere（PR）公式 $$\beta_k^{FR}=\frac{\nabla f(x_k)^T \nabla f(x_k)}{\nabla f(x_{k-1})^T \nabla f(x_{k-1})},\ \ \ \beta_k^{PR}=\frac{\nabla f(x_k)^T (\nabla f(x_k)-\nabla f(x_{k-1}))}{\nabla f(x_{k-1})^T \nabla f(x_{k-1})}$$
当 f 是严格凸的二次函数，且使用精确线搜索时，两种算法是相同的
数值结果表明，PR-CG算法更加地高效，强健性也更好
更多细节可参阅：