无约束优化算法可以分为线搜索类算法与信赖域类算法两类，他们都是对\(f(\boldsymbol x)\)在局部进行近似，前者用得更加普遍。而线搜索类算法根据搜索方向选择的不同可以分为梯度算法、牛顿算法、拟牛顿算法、次梯度算法等
本文目的是介绍牛顿法。平常我们说牛顿法，一般指的是用牛顿法求方程根，因而先复习牛顿法求根的原理，然后扩展到用牛顿法求极值，再进一步扩展到多元函数牛顿法求极值
1. 一元函数牛顿法求根
复杂方程的根很难直接求得，最开始用牛顿法迭代来求方程的根。方法是给 一个初值 \(x_{1}\) ，在 \(x_{1}\) 处用一阶泰勒展式来近似表示函数 \(f(x)\) \[ 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=x_{1}-f\left(x_{1}\right) / f^{\prime}\left(x_{1}\right)\), 这个 \(x\) 点并不是函数 \(f(x)\) 的根, 但是距离真正的根更近了一点，不断迭代优化，有如下步骤
\[ x_{n+1}=x_{n}-f\left(x_{n}\right) / f^{\prime}\left(x_{n}\right) \] 最终求得的 \(x\) 值变化小于一个阈值就认为这个 \(x\) 值是函数 \(f(x)\) 的近似根, 这时牛顿法收敛
2. 一元函数牛顿法求极值
牛顿法用于求函数极值。对于 \(f(x)\) 的极值点也就是求 \(f^{\prime}(x)\) 的根, 那么也就是如上面介绍的 求 \(f^{\prime}(x)=0\) 的解。给定初值 \(x_{1} ，\) 在 \(x_{1}\) 处用二阶泰勒展式见公式 \((4)\) 。 \[ 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} \] 对 \(f(x)\) 求导, 令 \(f^{\prime}(x)=0\), 得 \(x=x_{1}-f^{\prime}\left(x_{1}\right) / f^{\prime \prime}\left(x_{1}\right)\), 依次迭代得到递推公式 \[ x_{n+1}=x_{n}-f^{\prime}\left(x_{n}\right) / f^{\prime \prime}\left(x_{n}\right) \] 当xn的值变化小于阈值时认为算法收敛
3. 多元函数牛顿法求极值
对定义在\(\mathbb{R}^{n}\)上的二次可微函数\(f(\boldsymbol x)\)，考虑其在\(x_k\)处二阶泰勒展开，在其定义域上取\(x_k,d_k \in \mathbb{R}^{n}\)，其中\(d_k\)靠近\(x_k\)，有如下式子
\[ 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) \]
忽略高阶无穷小，将上式看作\(d_k\)的函数，对其求导(求梯度？)后令\(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_{n+1}=x_{n}-f\left(x_{n}\right) / f^{\prime}\left(x_{n}\right) \] \[ x_{n+1}=x_{n}-f^{\prime}\left(x_{n}\right) / f^{\prime \prime}\left(x_{n}\right) \] \[ 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) \]
- 参考
- 《最优化计算方法》 文再文
- 牛顿法求极值
