Optimization Algorithms - Newton's Methods

考虑无约束问题

使用梯度下降法(GD)求解这一问题的迭代格式为

由于梯度下降的基本策略是沿一阶最速下降方向迭代。当的条件数较大时，由于只使用到了一阶信息, 它的收敛速度比较缓慢。如果函数足够光滑，自然地会想到使用二阶梯度信息来加速收敛，这正是牛顿法的基本思想。

Newton’s Method

Newton法最初是为了求解非线性方程组而提出的，后来被推广到无约束最优化问题。注意到寻找足够光滑的向量值函数的零点等价于考虑以下方程

给定任意点，可以对在处进行泰勒展开

其中为在处的Jacobian矩阵，为高阶项。舍弃高阶项，令右端为零以求解，得到

这样就得到了以下迭代格式

现在我们将以上的思路应用到无约束最优化问题中。对于可微二次函数，寻找其最小值等价于求解

仿照上述思路考虑目标函数在处的二阶泰勒展开

舍弃高阶项，将等式右端视作关于的二次函数，关于求导并令其为零以极小化该函数，得到

这一方程称为Newton方程，其解向量称为Newton方向。当非奇异时，Newton方向是存在且唯一的，此时可以构造迭代格式

其中是步长参数，当时，上述迭代格式称为经典Newton法。

不难发现，对于二次函数，Newton法仅需一次迭代就可以收敛到最优解。对于非二次函数，牛顿法并不能保证经有限次迭代求得最优解。但由于目标函数在极小点附近可用二次函数较好地近似，故当初始点靠近极小点时，牛顿法的收敛速度一般会很快。

另外，Newton法具有仿射不变性。令是一个可逆矩阵，给定任意的函数，定义

于是等价于在一组新的基底下对进行变换。可以验证，Newton法的迭代格式在变换后的函数下仍然保持不变，即

具有与在原基底下的Newton法相同的迭代形式

并且若，则对任意的都有。

现在我们讨论Newton法的收敛性。首先，Newton法的快速收敛依赖于初始点的选择，特别当条件数较大时对初值的要求往往比较严苛，即Newton法的收敛性是局部的，基于这一原因，应用时常以梯度类算法先求得较低精度的解, 后用牛顿法加速收敛。下面给出Newton法的收敛性定理。

Newton's Method

设是一个二次可微函数。如果存在的一个邻域以及常数使得 且满足 选取为任意使得以下不等式成立的正数 则当满足 时，迭代序列以-二次收敛速度收敛到： 并且以-二次收敛速度收敛到：

修正Newton法

回忆经典Newton法的迭代格式

该格式具有以下缺陷：

• 需要计算Hessian矩阵并求逆，这在高维问题中计算量过大，同时内存消耗过大。
• Hessian矩阵可能是奇异的或近似奇异的，此时Newton方向不可用。
• 初始点距离极小点较远时迭代不稳定，此时算法可能不收敛。

为了弥补以上缺陷，可以尝试从以下两方面改进Newton法：

• 对进行修正以使其正定；
• 使用线搜索来选择步长以提高算法稳定性；

我们将使用以上两种策略改进Newton法得到的迭代算法称为修正Newton法(Modified Newton Method, MNM)。修正Newton法的迭代格式为：

1. 确定矩阵以使得正定且条件数较小；
2. 求解修正Newton方程获得Newton方向；
3. 使用线搜索确定步长；
4. 更新迭代点

修正Newton法迭代流程

为了保证修正Newton法的收敛和稳定性，算法的关键在于选择合适的修正矩阵。的选取应当使得之后得到具有较小的条件数，且为了保留二阶信息，对的改动不应过大，另外，自身的计算也应当尽可能简单。

最常使用的修正矩阵形式为

其中是一个正数，其选取可以通过对的特征值进行分析来确定。设有如下特征分解：

则

当足够大时可以保证的正定性，但计算得到的将接近负梯度方向，此时算法退化为一阶方法。一种简单有效的选择是令

其中是一个小的正数。这样可以保证的所有特征值都大于，从而使得正定且条件数有上界。不过这种选择的问题在于通常不易计算，可以采用Cholesky分解等方法试探性地选取来一定程度上避免这一问题。

最后，可以证明修正Newton法在满足一定条件下具有全局收敛性。

Modified Newton's Method

令在开集上二次连续可微，且初始点满足为紧集。如果修正牛顿法中每步得到的的条件数有上界，即 则 即算法具有全局收敛性。

非精确Newton法

如之前所述，当处理大规模问题时，Newton法的计算量和内存消耗都很大，特别是需要计算Hessian矩阵并求逆时。为了解决这一问题，可以使用非精确Newton法(Inexact Newton Method)，即使用迭代法近似求解Newton方程，在达到一定精度时提前停止迭代，以此来提高求解效率。具体地来讲，我们引入残差向量

设置迭代法求解Newton方程的终止条件为

其中是一个小的正数，不同的选取方式将导致不同的精度要求，相应地将使算法具有不同的收敛速度。一般地，如下收敛性定理成立。

Inexact Newton's Method

令二次连续可微，且正定，则在非精确Newton法中：

1. 如果存在使得满足，且初始点充分靠近，并且迭代序列最终收敛到，则梯度序列以-线性收敛速度收敛到0。
2. 如果当时有，则梯度序列以-超线性收敛速度收敛到0。
3. 如果1或2成立，且在的邻域内Lipschitz连续，参数，则梯度序列以-二次收敛速度收敛到0。

在非精确求解Newton方程时，最常用的方法是使用共轭梯度法(Conjugate Gradient Method, CG)来求解线性方程组，这种非精确Newton法通常简记为线搜索Newton-CG法。特别地，由于共轭梯度法要求系数矩阵是对称正定矩阵，而可能非正定，因此在使用Newton-CG法时通常需要对进行修正以保证其正定性。

使用CG法求解Newton方程的最大优势在于只需使用到Hessian矩阵与向量的乘积，不需要显式地计算出，通过避免计算，该方法可以显著降低计算量和内存消耗，特别适用于大规模问题。

线搜索Newton-CG法

Quasi-Newton method

除了之前介绍的修正Newton法与非精确Newton法之外，还有一种常用的Newton方法变体称为拟Newton法(Quasi-Newton Method)。拟Newton法的基本思想是通过构造一个近似Hessian矩阵来代替真实的Hessian矩阵，或构造近似Hessian矩阵的逆矩阵来代替真实的Hessian矩阵的逆，从而避免直接计算Hessian矩阵及其逆。

设是一个二阶连续可微函数，对在点处进行一阶Taylor展开得到

令，，，则上式等价于

现在舍弃高阶项，希望找到一个近似Hessian矩阵使得

或近似Hessian逆矩阵满足

称上述两个方程为拟Newton法的割线方程。

类似于Newton法需要Hessian矩阵正定以保证收敛性，拟Newton法也需要近似Hessian矩阵正定来确保收敛，即要求

称上述要求为曲率条件。

如果线搜索使用Wolfe准则，即

其中，不难发现上式等价于。在这一不等式两侧同时减去，注意到且是下降方向，因此

因此曲率条件在满足Wolfe准则的线搜索下是自动满足的。

拟Newton法迭代流程

拟Newton矩阵

拟Newton法的关键在于如何构造近似Hessian矩阵或其逆矩阵。结构最简单的拟牛顿矩阵更新方式是秩一更新(SR1)：对于拟牛顿矩阵，设为某一待定向量，为待定常数 (和在迭代过程中一直变化，此处为了简单起见省略了上标)，令为的秩一修正，即

现在我们来推导为使割线方程成立，与需要满足的条件。将上述更新形式代入割线方程，得到

注意到，因此上式说明与同向。为了简单起见，令

将这一关系重新代入上式，得到

再令，就可以得到

综上，的秩一更新格式为

类似地可以得到的秩一更新格式为

上述两个更新格式在形式上互为对偶。事实上有，使用秩一更新的SMW (Sherman-Morrison-Woodbury) 公式

可以从的更新格式得到的更新格式，反之亦然。

然而秩一更新方式存在严重的缺陷：与的正定性无法保证秩一更新之后的与的正定性，因此即使初始的或是正定的，经过多次更新后得到的或可能会变得非正定。实际上，为了确保的正定性，可以使用的一个充分条件为正定且。

基于上述原因，通常在实际应用中使用BFGS(Broyden-Fletcher-Goldfarb-Shanno)更新方式来构造近似Hessian矩阵，其核心思想是进行秩二更新：对于拟牛顿矩阵，设为待定向量，为待定常数 (与同样在迭代过程中不断改变，这里省略上标)，令为的秩二修正，即

现在我们来推导为使割线方程成立，需要满足的条件。将上述更新形式代入割线方程，得到

整理可得

我们令，，这等价于要求

以及

将以上关系代入割线方程就得到了

借助一般的SMW公式

其中可逆，为使得可逆的任意矩阵，可以得到的秩二更新格式为

由BFGS更新方式得到的正定性由以下定理保证。

Positive-Definition of BFGS

当以下条件成立时，BFGS更新得到的是正定的：

1. 正定；
2. 曲率条件对于任意都成立。

因为在确定步长时使用某一Wolfe准则线搜索即可满足曲率条件, 因此BFGS公式产生的拟牛顿矩阵有望保持正定, 从而使得拟牛顿法具有良好的收敛性。

另一种常用的拟牛顿矩阵更新方式是DFP(Davidon-Fletcher-Powell)更新方式，它采用与BFGS类似的秩二更新方式，但是使用的割线方程为：基于的DFP更新方式为

对应地使用SMW公式可以得到的DFP更新方式为

不过尽管DFP格式与BFGS对偶，但从实际效果而言，DFP格式的求解效率整体上不如BFGS格式，一个经典的例子是

设置初始值

其中。当选取误差阈值为时，分别取为不同的值，使用BFGS算法与DFP算法进行迭代，得到的迭代次数如下表所示：

从上表可以看出，BFGS格式的迭代次数远远少于DFP格式。

收敛性分析

根据对BFGS格式有效性的分析，我们先确保初始矩阵是对称正定的。

Global Convergence of BFGS

设初始矩阵是对称正定的，目标函数是二阶连续可微函数，下水平集 是凸集，且存在使得对任意与任意满足 则BFGS格式结合线搜索的拟牛顿法可以全局收敛到的极小值点。

上述全局定理说明在一定假设下，使用BFGS格式确定下降方向，搭配Wolfe线搜索确定步长后是全局收敛的。下面这个定理从局部收敛性给出了其收敛速度。

Local Convergence of BFGS

设是二阶连续可微函数，是使用BFGS格式得到的收敛到的拟牛顿法迭代序列，是对称正定矩阵。如果初始矩阵是任意对称正定矩阵，则存在和使得对任意都有

上述定理表明, 序列满足压缩条件，因此拟牛顿法具有-线性收敛速度。事实上，在上述局部收敛定理的条件的基础上，如果进一步要求的Hessian矩阵在的邻域内Lipschitz连续，则拟牛顿法具有-超线性收敛速度，即

综上，以BFGS格式为代表的拟牛顿类算法由于仅仅使用了海瑟矩阵的近似，因此很难达到二阶收敛速度，最多只能达到Q-超线性收敛速度。但是，由于拟牛顿方法对近似矩阵的更新代价可能远小于牛顿方法计算海瑟矩阵的代价，因此它在大规模问题中的开销可能远小于牛顿算法，较为实用。

References

1. 最优化讲义，陈士祥
   1. 牛顿法
   2. 拟牛顿法
2. 最优化与建模，文再文