1. 共轭梯度法

http://www.cnblogs.com/maybe2030/p/4751804.html#_label1

* conjugate gradient method

* 目标：

• 加快最速下降法的收敛速度；同时避免牛顿法的大量计算

• 共轭梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hesse矩阵并求逆的缺点，共轭梯度法不仅是解决大型线性方程组最有用的方法之一，也是解大型非线性最优化最有效的算法之一

• 理论上只需要n次就得到精确解。
• 直接设置为共轭方向，减少了计算方向的开销
• 初次设置为最速下降方向
• 主要用于二次函数
• 存储量少
• 速度比牛顿法慢，比梯度下降快

* 应用背景

• 稳定性高
• 要求对称，正定
• 无约束凸二次规划
• 收敛速度优于梯度下降，差于Nesterov算法

* 算法

• 利用已知点的梯度构造一个共轭方向
• 沿着方向搜索，找出极小点

2. 算法

* 引理

$Q是n*n的对称实矩阵$，对于方向$d^0,..., d^m$如果对所有的$i\neq j$，有$d^{(i)}Qd^{(j)}=0$,则称是关于$Q共轭的$

• 可以借助施密特正交化的方法构建共轭向量

* 共轭方向法

• 针对n维二次型函数的最小化问题：

$f(x)=\frac{1}{2}x^TQx-x^Tb$

• 给定初始点$x^{(0)}$和关于Q的共轭方向$d^0,..,d^{(m-1)}$ 迭代公式：

$g^k=\bigtriangledown f(x^k)=Qx^k-b$

$\alpha^k=-\frac{(g^k)^T d^k}{d^{(k)^T}Qd^k}$

$x^{(k+1)}=x^k+\alpha_k d^{(k)}$

2.2 共轭梯度法

• 共轭梯度法不需要提取计算共轭方向，在迭代过程中不断的产生Q的共轭方向
• 每次迭代，利用上一次搜索方向和目标函数在当前迭代点的梯度向量之间的线性组合构造新的方向，使其与前面的搜索方向构成Q的共轭方向

* 步骤：

• 针对:

$f(x)=\frac{1}{2}x^TQx-x^Tb$

• 初始点是$x^0$, 搜索方向是最速下降法方向，即函数f在$x^0$处的梯度的负方向：

$d^0=-g^0$

• 下一个迭代点：

$x^1=x^0+\alpha_0 d^0$

• 步长$\alpha$是线性准则

• 再次搜索，搜索方向$d^1$和$d^0$是关于Q共轭的，$d^1$是$g^1$和$d^0$的线性组合。推广得：

$d^{(k+1)}=-g^{(k+1)}+\beta d^{(k)}$

• 如下方式选择$\beta_k$,可以使得$d^{(k+1)}和d^0,...,d^k$组成Q的共轭方向：

$\beta_k=\frac{g^{(k+1)T}Qd^k}{d^{(k)T}Qd^(k)}$

共轭梯度法的碎碎念

* 共轭梯度法的优缺点

* 共轭梯度法

*　依赖于初始值的猜测， 依然不可以保证收敛到全局最小值

• 理论上n次到达最小值

*算法比较

• 梯度下降法形式简单，一般情况下都能够保证收敛，但是收敛速度慢
• 牛顿法对于二次目标函数收敛速度快，但是不能够保证收敛，而且需要对赫森矩阵及其逆阵的计算和存储
• 共轭梯度法结合了前面两种方法的性质，收敛速度快，不需要对赫森矩阵及其逆阵的计算和存储，但是形式比前两者复杂

* 碎碎念

• 每次沿着一个方向优化到极小值
• 后面在沿着正交方向优化，不会对前面的方向产生影响
• 理论上N次可以得到最优值