> For the complete documentation index, see [llms.txt](https://json007.gitbook.io/svm/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://json007.gitbook.io/svm/math-convex_optimization/niu_dun_fa.md).

# 牛顿法

## 牛顿法

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

### 参考佳文

[最优化问题中，牛顿法为什么比梯度下降法求解需要的迭代次数更少？](https://www.zhihu.com/question/19723347)