拟牛顿算法.docx

拟牛顿算法拟牛顿法(QUaSi-NeWtOnMethodS)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.FletcherM.J.D.Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。基本概念拟牛顿法和最速下降法(SteePeStDescentMethOdS)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化,构造一个目标函数的模型使之足以产生超线性收敛性。这类方法大大优于最速下降法，尤其对于困难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(NeWtorYSMethOd)更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。拟牛顿法是解非线性方程组及最优化计算中最有效的方法之一.它是一类使每步迭代计算量少而又保持超线性收敛的牛顿型迭代法。拟牛顿法还有很多具体算法，这类算法最早是由戴维登(DaVidon,W.D.)于1959年提出的，弗莱彻(FIetCher,R.)和鲍威尔(POWeII,M.J.D.)于1963年给出了后来称为DFP的秩2拟牛顿法，布罗依丹(Broyden,C.G.)于1965年给出了秩1拟牛顿法.方法的收敛性是20世纪60年代末到20世纪70年代才逐渐被证明的.由于这类方法受到广泛注意，从20世纪60年代到20世纪70年代近20年中，前后发表了一千多篇文章，提出了很多不同的算法及收敛性证明。中国也有一些学者在这方面做出很好的结果。1基本思想拟牛顿法的基本思想如下。首先构造目标函数在当前迭代的二次模型：mA(P)=磔)+/(ZQTP÷P到P4W这里是一个对称正定矩阵，于是我们取这个二次模型的最优解作为搜索方向，并且得到新的迭代点,其中我们要求步长满足Wolfe条件。这样的迭代与牛顿法类似，区别就在于用近似的Hesse矩阵代替真实的Hesse矩阵。所以拟牛顿法最关键的地方就是每一步迭代中矩阵的更新。假设得到一个新的迭代,并得到一个新的二次模型：mt+1(P)=f(k+l)÷V(xt+1)p+pp我们尽可能地利用上息来选取具体地，我们要求Qu)-Vf(xk)=akBk.pk,从而得到1(®*+l-Xfc)=V(x*+)-/国)这个公式被称为割线方程.下面主要介绍这几种方法：DFP方法，BFGS方法，SRl方法，BrOyCen族方法.这个公式被称为割线方程。下面主要介绍这几种方法：DFP方法，BFGS方法，SR1方法，BrOyden族方法。DFP方法,DFP公式为该公式最初由Davidon于1959年提出，随后被Fletcher和Powell研究和推广。DFP方法是秩2更新的一种，由它产生的矩阵是正定的，而且满足这样的极小性：BFGS方法DFP更新公式非常有效，但很快就被BFGS公式取代。BFGS与DFP十分类似，是另一种秩-2更新，以其发明者Broyden1Fletcher,Goldfarb和Shanno的姓氏首字母命名。BFGS公式为由他产生的矩阵同样保持正定性，而且也满足一个极小性：BFGS和DFP公式在形式上是对称的：与对称，对称。但是BFGS比DFP更加有效。对称秩1(SRl)方法有别于DFP和BFG方法，SRl是一种秩1更新。它的公式是：OSRl公式不要求矩阵B_k保持正定性，从而更逼近真实的HeSSe矩阵，所以适用于信赖域方法(TrUStRegionMethods)oBroyden族Boyden族是更广泛的一类更新公式，其形式为：0当时，BrOyden族公式就变成了BFGS公式；当时，Broyden族公式就变成了DFP公式。因此BFGS和DFP均可看成Broyden族的特殊形式或者其中一员。