[科普中国]-拟牛顿法

基本概念

拟牛顿法和最速下降法(Steepest Descent Methods)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(Newton's Method)更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。

拟牛顿法是解非线性方程组及最优化计算中最有效的方法之一.它是一类使每步迭代计算量少而又保持超线性收敛的牛顿型迭代法。

拟牛顿法还有很多具体算法，这类算法最早是由戴维登(Davidon，W.D.)于1959年提出的，弗莱彻(Fletcher，R.)和鲍威尔(Powell，M.J.D.)于1963年给出了后来称为DFP的秩2拟牛顿法，布罗依丹(Broyden，C.G.)于1965年给出了秩1拟牛顿法.方法的收敛性是20世纪60年代末到20世纪70年代才逐渐被证明的.由于这类方法受到广泛注意，从20世纪60年代到20世纪70年代近20年中，前后发表了一千多篇文章，提出了很多不同的算法及收敛性证明。中国也有一些学者在这方面做出很好的结果。1

基本思想拟牛顿法的基本思想如下。首先构造目标函数在当前迭代 的二次模型：

这里 是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点 ，其中我们要求步长 满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵 代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵 的更新。现在假设得到一个新的迭代 ，并得到一个新的二次模型：

我们尽可能地利用上一步的信息来选取 。具体地，我们要求 ，从而得到

这个公式被称为割线方程。下面主要介绍这几种方法：DFP方法，BFGS方法，SR1方法，Broyden族方法。

DFP方法记 ， ， ，DFP公式为

该公式最初由Davidon于1959年提出，随后被Fletcher和Powell研究和推广。DFP方法是秩-2更新的一种，由它产生的矩阵 是正定的，而且满足这样的极小性：

BFGS方法DFP更新公式非常有效，但很快就被BFGS公式取代。BFGS与DFP十分类似，是另一种秩-2更新，以其发明者Broyden, Fletcher, Goldfarb和Shanno的姓氏首字母命名。BFGS公式为 由他产生的矩阵 同样保持正定性，而且也满足一个极小性：

BFGS和DFP公式在形式上是对称的： 与 对称， 与 对称。但是BFGS比DFP更加有效。

对称秩1（SR1）方法有别于DFP和BFG方法，SR1是一种秩-1更新。它的公式是： 。SR1公式不要求矩阵B_k保持正定性，从而更逼近真实的Hesse矩阵，所以适用于信赖域方法(Trust Region Methods)。

Broyden族Boyden族是更广泛的一类更新公式，其形式为： 。当 时，Broyden族公式就变成了BFGS公式；当 时，Broyden族公式就变成了DFP公式。因此BFGS和DFP均可看成Broyden族的特殊形式或者其中一员。