最优化基础：牛顿法与拟牛顿法

对于无约束最优化问题

Copy LaTeX

以下假设 $f$ 足够光滑；当梯度为零时停止迭代。精确一维搜索还要求沿搜索方向的极小值能够取得。

通用的算法流程如下：

我们现在关注搜索方向的确定。

最速下降法

每一次的搜索相当于对 $f$ 进行了一阶的泰勒展开

Copy LaTeX

这里记 $g^k$ 为梯度方向，在下文中用于简写。

Copy LaTeX

当梯度非零时，取负梯度方向是下降方向，配合足够小的正步长可以保证函数值下降

Copy LaTeX

每一次的搜索相当于对 $f$ 进行二阶的泰勒展开

Copy LaTeX

这里的二阶导是 Hesse 矩阵

Copy LaTeX

针对二次函数取极小点 $x^*$ ，当前点向极小点的位移方向取为搜索方向

Copy LaTeX

经典的牛顿法不会进行一维搜索，总是取步长为 1，在经典的牛顿法基础上，可以使用一维搜索确定步长，这样就得到了阻尼牛顿法。

牛顿法存在的最大问题是：我们希望需要计算的 Hesse 矩阵是对称正定的，但是实际问题中 Hesse 矩阵可能不定，此时二次近似没有极小值点；甚至可能矩阵不可逆，计算无法继续。

为了克服牛顿法的困难，更好的做法是采用一族对称正定矩阵 $H_k$ 作为 $\nabla^2 f(x^k)$ 的近似逆，使得计算可以继续。

牛顿方向 $d^k$ 满足

Copy LaTeX

引入如下记号

Copy LaTeX

近似有下式成立

Copy LaTeX

我们希望构造 $H_{k+1} \approx G_{k+1}^{-1}$ ，满足下式（称为正割条件，拟牛顿条件）

Copy LaTeX

这里的构造并不唯一，对应是不同的拟牛顿法。

拟牛顿法的一般流程为：

其中 Hesse 矩阵的对称正定近似逆 $\{H_k\}$ 的构造是依次进行的，基于上一步添加一个低秩矩阵而来

Copy LaTeX

近似逆采用如下形式计算

Copy LaTeX

利用拟牛顿条件可得

Copy LaTeX

该公式要求分母非零。若 $s^k=H_k y^k$ ，已有矩阵满足拟牛顿条件，直接取 $H_{k+1}=H_k$ 。实际计算中，记 $r^k=s^k-H_k y^k$ ，仅在

Copy LaTeX

时进行更新，否则跳过本次校正，避免零分母或过小分母导致的不稳定。

对称秩一校正可以保证对称性，但不能保证正定，不能完全满足需求。

近似逆采用如下形式计算

Copy LaTeX

拟牛顿条件

Copy LaTeX

对称秩二校正的自由度过多，拟牛顿条件和对称正定性质不足以保证唯一解。

DFP 和 BFGS 在 $H_k$ 对称正定且满足曲率条件 $(s^k)^T y^k>0$ 时保持正定，分母也随之非零。对于非零下降方向，若精确一维搜索取得正步长的内点极小值，则可推出该曲率条件；满足 Wolfe 条件的正步长也可保证它成立。任意步长没有这一保证，条件不满足时需要跳过或修正更新。