最优化方法：共轭梯度法（Conjugate Gradient）

http://blog.csdn.net/pipisorry/article/details/39891197

共轭梯度法（Conjugate Gradient）

共轭梯度法（英语：Conjugate gradient method）。是求解数学特定线性方程组的数值解的方法。当中那些矩阵为对称和正定。共轭梯度法是一个迭代方法。它适用于稀疏矩阵线性方程组，由于这些系统对于像Cholesky分解这种直接方法太大了。这种方程组在数值求解偏微分方程时非经常见。

共轭梯度法也能够用于求解无约束的最优化问题。

在数值线性代数中，共轭梯度法是一种求解对称正定线性方程组的迭代方法。

共轭梯度法能够从不同的角度推导而得，包含作为求解最优化问题的共轭方向法的特例，以及作为求解特征值问题的Arnoldi/Lanczos迭代的变种。

提供了一种处理非对称矩阵情况的推广。

基础

共轭向量

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcGlwaXNvcnJ5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" width="607" height="154" alt="" />

显然,共轭向量是线性无关向量.

初等变分原理

最速下降算法的有关性质

范数的‖・‖A的定义为‖x‖A=(Ax,x)。

上面定理表明,最速下降法从不论什么一向量x(0)出发,迭代产生的数列总是收敛到原方程Ax=b的解.而收敛速度的快慢则由A的特征值分布所决定.当A的最小特征值和最大特征值相差非常大时λ1<<λn,最速下降法收敛速度非常慢,非常少用于实际计算.

分析最速下降法收敛较慢的原因,能够发现,负梯度方向从局部来看是二次函数的最快下降方向,可是从总体来看,却并不是最好.对于对称正定矩阵A,共轭梯度法考虑选择关于A共轭的向量p1,p2,...取代最速(0)下降法中的负梯度方向,使迭代法对随意给定的初始点x具有有限步收敛性,即经有限步就能够(在理论上)得到问题的准确解.

皮皮blog

共轭梯度算法

计算共轭梯度算法同一时候构造出关于A共轭的向量pi

求解Ax = b的算法。当中A是实对称正定矩阵。

x := 0

k := 0

r := b-Ax

repeat until r is "sufficiently small":

k := k + 1

if k = 1

p := r

else

pk:=rk− 1+rk− 1⊤ rk− 1rk− 2⊤ rk− 2 pk− 1{\displaystyle p_{k}:=r_{k-1}+{\frac {r_{k-1}^{\top }r_{k-1}}{r_{k-2}^{\top }r_{k-2}}}~p_{k-1}}

end if

α k:=rk− 1⊤ rk− 1pk⊤ Apk{\displaystyle \alpha _{k}:={\frac {r_{k-1}^{\top }r_{k-1}}{p_{k}^{\top }Ap_{k}}}}

x := x + α p

r := r - α A p

end repeat

结果为x

或者

watermark/2/text/aHR0cDovL2Jsb2cuY3Nkbi5uZXQvcGlwaXNvcnJ5/font/5a6L5L2T/fontsize/400/fill/I0JBQkFCMA==/dissolve/70/gravity/Center" alt="" />

共轭梯度法评价

　　共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法须要存储和计算Hesse矩阵并求逆的缺点。共轭梯度法不仅是解决大型线性方程组最实用的方法之中的一个，也是解大型非线性最优化最有效的算法之中的一个。 在各种优化算法中，共轭梯度法是非常重要的一种。
其长处是所需存储量小，具有步收敛性。稳定性高，并且不须要不论什么外来參数。

　　下图为共轭梯度法和梯度下降法搜索最优解的路径对照示意图：

 

注：绿色为梯度下降法。红色代表共轭梯度法

from:http://blog.csdn.net/pipisorry/article/details/39891197

ref: [wiki 共轭梯度法] [wiki 共轭梯度法的推导]

[数值分析 钟尔杰]