牛顿法

牛顿法

牛顿下降方向： $dir = (\nabla^2 L(w))^{-1}(-\nabla L(w))$

牛顿下降方向原因：

$$\nabla L(w+d) = 0 \\ \nabla L(w+d) \approx \nabla L(w) + d \nabla^2 L(w)= 0 \\ d = (\nabla^2 L(w))^{-1}(-\nabla L(w))$$

缺点：Hessian逆矩阵计算复杂，所以高维数据复杂度不可接受。 注意，Hessian逆矩阵不一定正定，所以不一定是下降方向。

一般步长为1，所以每步下降量：$\sigma(x) = (\nabla f(x)^T \nabla^2 f(x)^{-1} \nabla f(x) )^{\frac 12}$ 。所以停止条件可以为（注意与负梯度下降中的停止条件）：$\sigma(x) \le \epsilon$ 。

阻尼牛顿法

固定步长的牛顿法，目标函数不一定得到改善。所以使用直线搜索来修正。 $X^{(k+1)} = X^{(k)} + t_k d^{k}$

梯度法下降和牛顿法下降各有优点和缺点，有没有组合了有点避免了缺点方法？拟牛顿法!

拟牛顿法下降

寻找Hessian矩阵或逆矩阵的代替品，Hessian阵应该近似满足： $\nabla f(x_{k+1}) - \nabla f(x_k) = H_k(x_{k+1} - x_k)$

拟牛顿法的切线方程条件： 记$y_k = \nabla f(x_{k+1}) - \nabla f(x_k) , s_k = x_{k+1} - x_k$ ，择有： $H_k^{-1} y_k = s_k$

替代矩阵 为正定矩阵的充分条件： $s_k^{T} y_k \gt 0$ 1. 此条件，凸函数成立，非凸函数不一定成立。 2. 如果wolfe条件满足，则上式也成立。 证明：$\nabla f_{k+1}^{T} s_k \ge c_2 \nabla f_k^T s_k \ s_k^{T} y_k \gt (c_2-1) \nabla f_k^T s_k \gt 0$

替代矩阵产生的原则：

• 迭代产生

• 满足切线方程和对称条件

• 同时尽可能和上一步的替代矩阵相似

产生的解法有 DFP和BFGS等

参考佳文

最优化问题中，牛顿法为什么比梯度下降法求解需要的迭代次数更少？