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

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

@姓颜色的小学生 的答案蛮有见解的,我稍微用数学细化一下看这个问题的角度。

------------------------------------------------------------------------------------

首先,我们的问题是解决二次函数极值问题,其中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 是 他们是 .

所以本质上,就是把目标函数分成许多方向,然后不同方向分别求出极值在综合起来。我稍微推导了一下公式,让他更一目了然。

---------------------------------------------------------------------------------------

看我写的这么辛苦,从知识的喜悦中脱离一下,点个赞呗,想一起了解学习凸优化和非凸优化的可以关注我,我以后会多写一些自己的学习体会,大家可以一起交流。

我的专栏:非凸优化学习之路 - 知乎专栏

第一篇文章是: 从Nesterov的角度看:我们为什么要研究凸优化? - 知乎专栏

第二篇文章是:非凸优化基石:Lipschitz Condition - 知乎专栏

第三篇文章是:当我们谈论收敛速度时,我们都在谈什么? - 知乎专栏

或许你看了也会有启发,哈哈。