牛顿法

牛顿下降方向： $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等

参考佳文

Previous随机梯度下降 NextL-BFGS

Last updated 5 years ago

Was this helpful?

牛顿法

牛顿下降方向：

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等

参考佳文