拟牛顿法

拟牛顿法(Quasi-艾萨克·牛顿 Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W. C. Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。

内容概述

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

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

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

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

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

DFP方法

记,,,DFP公式为

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

SR1方法

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

Broyden族

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

参考资料

Warning: Invalid argument supplied for foreach() in /www/wwwroot/newbaike.com/id.php on line 280