牛顿法用于优化问题

Ilingis · 发表于 2021-12-11 21:37

无约束优化算法可以分为线搜索类算法与信赖域类算法两类，他们都是对 $f(\bold x)$ 在局部进行近似，前者用得更加普遍。而线搜索类算法根据搜索方向选择的不同可以分为梯度算法（例如深度学习中常用的梯度下降）、牛顿算法、拟牛顿算法、次梯度算法等
本文目的是介绍牛顿法。平常我们说牛顿法，一般指的是用牛顿法求方程根，因而先复习牛顿法求根的原理，然后扩展到用牛顿法求极值，再进一步扩展到多元函数牛顿法求极值
1. 一元函数牛顿法求根

复杂方程的根很难直接求得，最开始用牛顿法迭代来求方程的根。方法是给一个初值  ，在  处用一阶泰勒展式来近似表示函数

$f(x)=f\left(x_{1}\right)+f^{\prime}\left(x_{1}\right)\left(x-x_{1}\right) + \mathcal{O}(x-x_1)$
将 $f(x)=0$ 带入上式, 求得与  轴交点横坐标 $x=x_{1}-f\left(x_{1}\right) / f^{\prime}\left(x_{1}\right)$ , 这个  点并不是函数  的根, 但是距离真正的根更近了一点，不断迭代优化，有如下步骤

最终求得的  值变化小于一个阈值就认为这个  值是函数  的近似根, 称为牛顿法收敛
2. 一元函数牛顿法求极值

牛顿法用于求函数极值。对于  的极值点也就是求 $f^{\prime}(x)$ 的根, 那么也就是如上面介绍的求  的解。给定初值 $x_{1} ，$ 在  处用二阶泰勒展式展开

$f(x)=f\left(x_{1}\right)+f^{\prime}\left(x_{1}\right)\left(x-x_{1}\right)+\frac{1}{2} f^{\prime \prime}\left(x_{1}\right)\left(x-x_{1}\right)^{2}$
对  求导, 令 , 得 $x=x_{1}-f^{\prime}\left(x_{1}\right) / f^{\prime \prime}\left(x_{1}\right)$ , 依次迭代得到递推公式

当xn的值变化小于阈值时认为算法收敛
3. 多元函数牛顿法求极值

对定义在 $\mathbb{R}^{n}$ 上的二次可微函数 $f(\boldsymbol x)$ ，考虑其在 $x_k$ 处二阶泰勒展开，在其定义域上取 $x_k,d_k \in \mathbb{R}^{n}$ ，其中趋近于0向量，展开结果如下

$f(x_k+d_k)=f(x_k)+\nabla f(x_k)^\mathrm{T}d_k + \frac{1}{2}(d_k)^\mathrm{T}\nabla^2f(x_k)d_k+\mathcal{O}(||d_k||^2)$
忽略高阶无穷小，将上式看作的函数，对其求导(求梯度？)后令 $f'(x_k+d_k)=0$ ，化简可得牛顿方程

$\nabla^{2} f\left(x_{k}\right) d_{k}=-\nabla f\left(x_{k}\right)$
由上式，可由简单的矩阵运算规则得到优化方向 $d_k=-\nabla^{2} f\left(x_{k}\right)^{-1} \nabla f\left(x_{k}\right)$
因而可以得到迭代规则

$x_{x+1}=x_{k}-\nabla^{2} f\left(x_{k}\right)^{-1} \nabla f\left(x_{k}\right)$
当xn的值变化小于阈值时认为算法收敛
4. 对比

4.1 牛顿法对比

如果把矩阵求逆 $\nabla^{2} f\left(x_{k}\right)^{-1}$ ，在形式上写作分母。将上面三者罗列如下，可见形式完全一样(吐槽：这不废话)

$x_{x+1}=x_{k}-\nabla f\left(x_{k}\right)/\nabla^{2} f\left(x_{k}\right)$
4.2 牛顿法与梯度下降对比

梯度下降

$x_{k+1}=x_{k}-\alpha_{k}\nabla f(x_k)$
步长不等于1的牛顿法(也就是优化方向乘以alpha)

$x_{x+1}=x_{k}-\alpha_k \nabla^{2} f\left(x_{k}\right)^{-1} \nabla f\left(x_{k}\right)$

5. 参考

《最优化计算方法》文再文
[牛顿法求极值](answer：牛顿法求极值)

		自动登录	找回密码
密码			立即注册