最近看了CMU的凸优化，里面对梯度下降的原理讲的比较清楚，这里将自己对梯度下降的理解做一个总结，如果有不对的地方希望大家指正。
1.梯度下降法
考虑无约束的最小化问题：
minxf(x)(1)
优化目标
f(x)是可微的凸函数。
使用梯度下降法求解上述问题的最优解x∗，迭代过程为：
xk=xk−1−α⋅∇f(xk−1)(2)
为什么使用上述迭代可以从下面的角度考虑。
2.解释1
将f(x)在xk−1处进行一阶泰勒展开(第二步实际应该为≈)
f(x)=f(xk−1+Δx)=f(xk−1)+∇f(xk−1)T⋅Δx(3)
(3)式约等于号中的第二项是关于两个向量的内积，为了使
f(xk)<f(xk−1)，显然
Δx应该取为负梯度方向
−α∇f(xk−1)，此时两个向量夹角为180度，目标函数下降最快，其中
α用来控制目标函数下降的步长，此时(3)式变为
f(x)=f(xk−1)−α∇f(xk−1)T⋅∇f(xk−1)(4)
可以发现，减号右侧是大于0的，
f(x)较上一次更新有所下降，所以沿用负梯度方向不断更新变量，也就是公式(2)可以不断使
f(x)减小，因为
f(x)是凸函数，因此变量会更新到
f(x)全局最优的位置。
3.解释2
考虑f(x)的二阶泰勒展开
f(x)≈f(xk−1)+∇f(xk−1)T(x−xk−1)+12(x−xk−1)T∇2f(xk−1)(x−xk−1)(5)
不过不同的是我们使用
1tI替换Hessian矩阵
∇2f(x) f(x)≈f(xk−1)+∇f(xk−1)T(x−xk−1)+12t||x−xk−1||22(6)
我们使用(6)式最小化
f(x)，令(6)式梯度等于0得
xk=xk−1−t∇f(xk−1)(7)
对比下(7)式和(2)式，变量更新公式是一样的。
在我们的印象里梯度下降是一阶优化方法，为什么(6)式看起来像使用了二阶信息？实际上这里还是使用的是一阶信息，我们将包含二阶信息的Hessian矩阵替换为了1tI。可以这样理解，(6)式包含了两部分，第一部分是原目标函数的一阶近似，如果我们直接优化一阶近似的目标函数(实际是个线性函数，一维情况下就是用曲线的切线近似)，那么变量将更新到无穷远。第二部分可以看做是一个约束项，表示我们希望优化后变量的位置与变量之前的位置尽可能接近，t的大小决定了变量更新前后的接近程度，也就是我们上面提到的梯度下降的步长。
用下面的图直观地感受一下。
参考文献
- 《统计学习方法》
- http://www.stat.cmu.edu/~ryantibs/convexopt/lectures/grad-descent.pdf
