最优化问题求解--优化方法 - Jun's personal knowledge wiki

Table of Contents

1. 优化方法

SGD最大的缺点是下降速度慢，而且可能会在沟壑的两边持续震荡，停留在一个局部最优点。

mini-batch Gradient Descent

二阶优化算法使用了二阶导数(也叫做Hessian方法)来最小化或最大化损失函数。由于二阶导数的计算成本很高，所以这种方法并没有广泛使用。

牛顿法的优点是收敛速度快，而缺点是牛顿法的计算中需要计算海森矩阵和该矩阵的逆。海森矩阵往往需要较大的计算量，而且一般矩阵的求逆运算时间复杂度是O(p3)。

牛顿法起始点不能离局部极小点太远，否则很可能不会收敛。(考虑到二阶拟合应该很容易想象)，所以实际操作中会先使用别的方法，比如梯度下降法，使更新的点离最优点比较近，再开始用牛顿法
牛顿法每次需要更新一个二阶矩阵，当维数增加的时候是非常耗内存的，所以实际使用是会用拟牛顿法。
梯度下降法在非常靠近最优点时会有震荡，就是说明明离的很近了，却很难到达，因为线性的逼近非常容易一个方向过去就过了最优点(因为只能是负梯度方向)。但牛顿法因为是二次收敛就很容易到达了。牛顿法最明显快的特点是对于二阶函数(考虑多元函数的话要在凸函数的情况下)，牛顿法能够一步到达，非常有效。

原因一：牛顿法需要用到梯度和Hessian矩阵，这两个都难以求解。因为很难写出深度神经网络拟合函数的表达式，遑论直接得到其梯度表达式，更不要说得到基于梯度的Hessian矩阵了。

原因二：即使可以得到梯度和Hessian矩阵，当输入向量的维度N较大时，Hessian矩阵的大小是N×N，所需要的内存非常大。比如你有1亿的数据，Hessian矩阵是1亿行和1亿列，然后进行逆运算，

原因三：在高维非凸优化问题中，鞍点相对于局部最小值的数量非常多，而且鞍点处的损失值相对于局部最小值处也比较大。而二阶优化算法是寻找梯度为0的点，所以很容易陷入鞍点。

为了保持收敛速度快的同时，减小每一步迭代的计算量，我们可以将海森矩阵的逆替换为一个近似的矩阵。而该矩阵的计算复杂度远小于原始的海森矩阵求逆。

比较著名的拟牛顿法有DFP和BFGS和L-BFGS。