牛顿法和拟牛顿法

约 557 个字预计阅读时间 2 分钟

简介

牛顿法和拟牛顿法也是求解无约束优化问题常用的方法，有收敛速度快的有点。牛顿法的基本思想是利用迭代点$x_k$处的一阶导数(梯度)和二阶导数(Hessen矩阵)对目标函数进行二次函数近似，然后把二次模型的极小点作为新的迭代点，并不断重复这一过程，直至求得满足精度的近似极小值。

牛顿法

NA 里面学过牛顿迭代法用来求方程近似解，这里其实也是求方程近似解，不过是导函数的。

将 $f\left( x\right)$ 在 ${x}^{\left( k\right) }$ 附近进行二阶泰勒展开:$f\left( x\right) = f\left( {x}^{\left( k\right) }\right) + {g}_{k}^{\mathrm{T}}\left( {x - {x}^{\left( k\right) }}\right) + \frac{1}{2}{\left( x - {x}^{\left( k\right) }\right) }^{\mathrm{T}}H\left( {x}^{\left( k\right) }\right) \left( {x - {x}^{\left( k\right) }}\right)$。

这里, ${g}_{k} = g\left( {x}^{\left( k\right) }\right) = \nabla f\left( {x}^{\left( k\right) }\right)$ 是 $f\left( x\right)$ 的梯度向量在点 ${x}^{\left( k\right) }$ 的值, $H\left( {x}^{\left( k\right) }\right)$ 是 $f\left( x\right)$的黑塞矩阵 (Hessian matrix)$H\left( x\right) = {\left\lbrack \frac{{\partial }^{2}f}{\partial {x}_{i}\partial {x}_{j}}\right\rbrack }_{n \times n}$ 在点 ${x}_{0}\left( k\right)$ 的值,函数 $f\left( x\right)$ 有极值的必要条件是在极值点处一阶导数为 0,即梯度向量为 0 。然后还是一样地操作可以得到迭代公式$$x^{(k+1)}=x^{(k)}+p_k\H_kp_k=-g_k $$

可以看到每次迭代都需对$H_k $求逆，矩阵求逆并不容易，所以这种算法时间复杂度其实很高。

这里补充一下黑塞矩阵的定义：

alt text

拟牛顿法

考虑用一个n阶矩阵$G_k=G(x^{(k)}) $来代替$H_k^{-1} $，不过需要满足拟牛顿条件$G_{k+1}y_k=\delta_k=(x^{(k+1)}-x^{(k)}) $

DFP算法

DFP算法选择$G_{k+1}$的方法是$G_{k+1}=G_k+P_k+Q_k \(，然后根据拟牛顿条件可以确定一组$P_k,Q_k\)

BFGS算法

这是当前最流行的拟牛顿算法，其实放在一维我们会把它叫做割线法，迭代公式与DFP类似