优化算法

只用到了目标函数的一阶导数信息（迭代方向），而牛顿法则用到了二阶导数信息
牛顿法就是用一个二次曲面去拟合你当前所处位置的局部曲面，而梯度下降法是用一个平面去拟合当前的局部曲面，通常情况下，二次曲面的拟合会比平面更好，所以牛顿法选择的下降路径会更符合真实的最优下降路径。
数据量大的时候会很慢。

对函数f(x)进行泰勒展开到二阶，得到

求导，令为

：

得：

基本牛顿法的流程:

给定终止误差值 $0 \leq \varepsilon \ll 1,$ 初始点 $x_{0} \in \mathbb{R}^{n},$ 令 $k=0$
计算 $g_{k}=\nabla f\left(x_{k}\right),$ 若 $\left\|g_{k}\right\| \leq \varepsilon,$ 则停止, 输出 $x^{*} \approx x_{k}$
计算 $G_{k}=\nabla^{2} f\left(x_{k}\right),$ 并求解线性方程组得解 $d_{k}: G_{k} d=-g_{k}$
$\widehat{\mathbf{\gamma}}^{x_{k+1}}=x_{k}+d_{k,}, k=k+1,$ 并转2。

全局牛顿法的流程:

给定终止误差值 $0 \leq \varepsilon \ll 1, \delta \in(0,1), \sigma \in(0,0.5),$ 初始点 $x_{0} \in \mathbb{R}^{n},$ 令 $k=0$
计算 $g_{k}=\nabla f\left(x_{k}\right),$ 若| $\left|g_{k}\right| \mid \leq \varepsilon,$ 则停止, 输出 $x^{*} \approx x_{k}$
计算 $G_{k}=\nabla^{2} f\left(x_{k}\right),$ 并求解线性方程组得解 $d_{k}: G_{k} d=-g_{k}$
记 $m_{k}$ 是不满足下列不等式的最小非负整数 $m: \quad f\left(x_{k}+\delta^{m} d_{k}\right) \leq f\left(x_{k}\right)+\sigma \delta^{m} g_{k}^{T} d_{k}$
$\hat{>} \alpha_{k}=\delta^{m_{k}}, x_{k+1}=x_{k}+\alpha_{k} d_{k}, k=k+1,$ 并转2。