梯度下降法和共轭梯度法有何异同？

一道考研题

@姓颜色的小学生 的答案蛮有见解的，我稍微用数学细化一下看这个问题的角度。
------------------------------------------------------------------------------------
首先，我们的问题是解决二次函数极值问题，其中Q是positive definite

                             (1)
接着介绍Q-conjugate：给定一个positive definite2矩阵Q， 我们说非零向量x,y 关于是Q-conjugate，如果他们满足，

                                        (2)
如果我们能找到n个Q-conjugate的向量用
表示，一个重要结论是
如果向量是Q-conjugate, 他们线性无关       (3)
所以空间任意向量 x可以用这组向量基表示

                                 (4)
将（4）代入（1）可得, 变量从
变成了
,



因为
是Q-conjugate，所以由（2）得
, 所以上式可以继续简化为

            (5)
将求和符号提出来，可以得到

          (6)


其实，现在我们的变量
已经被分开了，我们分别优化他们即可，为了看的更清楚一些，我们稍微改写一下， 把求和分开来写


这样，我们分别求第一项
的最小值，然后第二项，即可。
第一项是一个二次函数，求最小值我们直接求导即可：

可得
, 同样可得

           (7)
所以最优解
, 将(7)代入可得

         (8)
现在我们重新温习一下，conjuage gradient method(用在quadratic function上) （来自wiki   Conjugate gradient method）:


是不是和我们求的（7）式一样，只不过我们的conjugate notation 是
他们是
.  
所以本质上，就是把目标函数分成许多方向，然后不同方向分别求出极值在综合起来。我稍微推导了一下公式，让他更一目了然。

RemarK: 真正用conjugate gradient method的时候，我们需要找到一组conjugate的Basis, 一般使用的方法就是用当下的gradient (d_k) ，使用 Gram-Schmidt procedure 变成conjugate来用，所以其实conjugate gradient method 的一个版本是：

最后附上参考文献，里面关于conjugate gradient method讲的蛮清楚的：1>  Bertsekas D

---------------------------------------------------------------------------------------
看我写的这么辛苦，从知识的喜悦中脱离一下，点个赞呗，想一起了解学习凸优化和非凸优化的可以关注我，我以后会多写一些自己的学习体会，大家可以一起交流。
我的专栏：非凸优化学习之路 - 知乎专栏
第一篇文章是： 从Nesterov的角度看：我们为什么要研究凸优化？ - 知乎专栏
第二篇文章是：非凸优化基石：Lipschitz Condition - 知乎专栏
第三篇文章是：当我们谈论收敛速度时，我们都在谈什么？ - 知乎专栏
或许你看了也会有启发，哈哈。

最速下降：实在没什么好说的，
,until
共轭梯度：区别在于方向限制在初始点的共轭方向空间内
p.s.
随机梯度：相对上面两者每次用所有样本计算下降方向，每次随机选1个或batch个样本
牛顿法：二阶Talor展开，方向
pseudo-Newton (BFGS为例)：
，
，

这些搜索方法都是确定一个搜索方向然后再用一个合适的步长来保证收敛性，不同的是梯度下降在寻找搜索方向的时候只利用了空间中当前点的信息，共轭梯度下降还利用了之前的搜索路径信息

梯度下降法就是常说的最速下降法，考虑一个n维空间，我任意选取一个初始点，然后每次迭代的时候都以该点的负梯度方向（如果目标函数求最小值）进行精确一维搜索，正因为是精确搜索，所以相邻的迭代方向正交的，所以会出现“锯齿”现象，可能刚开始下降很多，但到后面越来越慢，收敛速度很慢。

而共轭梯度法是共轭方向法的一种，它在最速下降法的基础上对它进行了改良，初始点的下降方向仍是负梯度方向，但后面的迭代方向不再是该点的负梯度方向了，后面的迭代方向是该点的负梯度方向和前一次迭代方向形成的凸锥中的一个方向，这样有效地避免了“锯齿”现象。