拟牛顿法的研究现状文献综述

拟牛顿法的研究现状文献综述姓名:孟媛媛学号：112111215指导老师：肖伟前言求解非线性方程组的方法有很多，最速下降法具有结构简单，计算量小的优点，但是它的收敛速度较慢；牛顿法及其改良牛顿法，虽然收敛速度快，但在迭代过程中的每一步构造搜索方向时，首先要计算目标函数的Hessian矩阵，然后需要解一个线性方程组，计算工作量很大，这就抵消了牛顿法收敛速度快的优点。为了克服牛顿法的缺点，人们提出了拟牛顿法，拟牛顿法在构造搜索方向时，只需要利用目标函数及其一阶导数的信息，防止了Hessian矩阵的计算，减少了计算量，并且具有超线性收敛的优点，经理论证明和实践检验，拟牛顿法已经成为一类公认的比拟有效的算法.拟牛顿法求解非线性方程组的拟牛顿法设是连续可微映射．考虑下面的非线性方程组：牛顿法是求解方程组的经典的方法之一，其迭代格式为：，，其中是在处的Jacobian阵.牛顿法的一个显著优点就是具有局部的超线性甚至二阶收敛速度，由于牛顿法这一优点，使其成为颇受欢送的算法之一，然而，当Jacobian矩阵奇异时，牛顿方向可能不存在．克服牛顿法的这一缺陷的一个主要途径就是采用拟牛顿法，其根本思想是利用某个矩阵作为的近似取代.拟牛顿法的一般格式为：，，其中是步长，通常由某种线性搜索确定.是的近似，它满足下面的拟牛顿方程：，其中.注意到，因此，与沿方向很接近.拟牛顿矩阵的不同的校正公式导致不同的拟牛顿法.著名的拟牛顿校正公式有Broyden秩一校正公式，对称秩一校正公式，DFP校正公式，BFGS校正公式，PSB校正公式等，它们分别由下面这些公式定义：容易看到，DFP，PSB，BFGS，SR1校正公式都是对称的，他们适合求解对称问题，而BroydenR1校正公式是不对称的，因此它常被用来求非对称问题.如果，那么DFP和BFGS公式保持迭代矩阵的对称正定性，而其它几种方法不具有这种性质.PSB校正公式在非线性最小二乘问题中经常被采用.BFGS公式是颇受欢送的拟牛顿公式，它具有DFP校正所具有的各种性质.此外，当采用Wolfe线性搜索时，BFGS算法对凸极小化问题具有全局收敛性质，这个性质对于DFP方法是否成立尚不清楚.大量的数据结果说明，BFGS方法的数值效果优于其它的拟牛顿方法.拟牛顿法不需要明显计算Jacobian阵，同时保持牛顿法的快速收敛速度.自20世纪60年代Broyden第一次提出求解非线性方程组的拟牛顿法后，因其深邃丰富的理论知识和实际计算中的有效性，很快受到最优化工作者和计算数学家的特别青睐.特别是拟牛顿法的局部收敛性得到了广泛的研究.此外，人们对拟牛顿法求解无约束问题的全局收敛性分析进行了相当的努力并且取得了巨大进展．尽管拟牛顿法的局部收敛性结果十分丰富，但是其求解非线性方程组的全局收敛性结果却很少．全局化方法需要采用某种搜索计算步，但是此时拟牛顿方向一般不再是某个度量函数的下降方向，从而使得线性搜索难以实现或考说缺少一种有效的线性搜索.Griewank在1986年研究了解非线性方程组的Broyden秩一方法的全局收敛性，并在文献[2]中提出了一种无导数的线性搜索，同时证明了Broyden方法在该搜索下的全局收敛性．Li和Fukushima在文献[3]中构造了一个反例说明Griewank在文献[2]中的线性搜索在计算中可能会产生某些困难，即该搜索不是适定的.为克服此缺陷，Li和Fukushima提出了一种非单调搜索技术：求步长使得其中是常数，在适当条件下，文献[3]证明了求解非线性方程组的Broyden方法的全局收敛性.关于BFGS方法求解非线性方程组的第一个全局收敛性结果属于Li和Fukushima，1999年，他们在文献[4]中提出了一种新的近似范数下降的BFGS方法，称之为Gauss—Newton型BFGS方法，其拟牛顿方向由下面的方程决定：，其中由下面的BFGS公式校正：其中.这种Gauss-Newton型BFGS公式不同于标准的BFGS公式，尽管它仍满足拟牛顿方程.注意到，因此，相应的方法称之为Gauss-Newton型BFGS方法.2003年，GU等人引入了一种范数下降的线性搜索，并利用Li和Fukushima求解无约束优化问题的CBFGS和MBFGS方法的思想,提出了求解对称非线性方程组的范数下降的保守的和修正的Gauss—Newton型BFGS方法，并且证明了这两种方法全局收敛.尽管牛顿法和拟牛顿法都是非常有效的算法，但是它们都需要计算和存储矩阵，这难以用于求解大型问题．最近，Cruz和Raydan在文献[5]提出了一种求解一般的非线性方程组的非单调的谱梯度方法并证明了其全局收敛性．Zhang和Zhou在文献[6]提出了一种求解单调非线性方程组的谱梯度投影方浃法建立了全局收敛性结果.这两种谱梯度方法都适合求大规模问题，察实上，这两种谱梯度方法是求解无约束优化问题的谱梯度方法在非线性方程组中的推广．前面讨论的都是拟牛顿法求解光滑非线性方程组的已有结果。对拟牛顿法求解非光滑方程组的结果目前并不多见，而且大多数研究集中在局部收敛性分析上.通过光滑技术，Li和Fukushima将文献[3]Broyden方法求解光滑方程组的全局收敛性结果推广到了一般的半光滑方程组[8].二、求解无约束优化问题的拟牛顿法设：连续可微，为在点处的梯度，求解无约束优化问题min的拟牛顿法的迭代与其求解非线性方程的格式相同，只需要将中中的定义改为，其中是的简写.拟牛顿法求解无约束优化问题不仅局部收敛性分析取得丰硕的成果，而且全局收敛性分析也取得了巨大进展．Powell和Dixon证明了Broyden族方法在精确搜索下求解凸极小化问题时的全局收敛性．所谓的精确搜索，即求使得满足.Byrd等人在文献[8]中证明了除DFP方法外的Broyden族方法在Wolfe线性搜索下求解凸极小化问题的全局收敛性．这里的wolfe搜索，指的是求使得其满足，，其中．Byrd和Nocedal证明了BFGS方法在Armijo线性搜索下求解凸极小化问题的全局收敛性．所谓的Armijo搜索，即求满足，其中为常数．为了研究拟牛顿法求解非凸问题的全局收敛性，Li和Fukushima修正了标准的BFGS公式，提出了CBFGS方法和MBFGS方法并证明了这两种方法在Armijo和Wolfe线性搜索下对非凸极小化问题全局收敛.前面都是关于单调的拟牛顿法求解无约束问题的工作，所谓的单调方法就是算法产生的函数值序列单调递减，即使得成立.非单调方法那么不一定要求.最早提出非单调线性搜索技术的是Grippo，Lampariello和Lucidi．1986年，他们在文献[7]中考虑了如下一般格式的非单调线性搜索技术：给定常数及非负整数，寻找步长因子使得.当时，上面的非单调线性搜索变为标准的Armijo线性搜索.非单调技术的一个好处就是不要求函数值减少，从而使步长因子的选取更具有弹性，即使得步长尽可能的大．此外，Panier和Tits在文献[10]中证明了非单调搜索技术能防止Maratos效应．大量的数值结果说明，非单调搜索比单调搜索数值表现要好得多，特别是非单调方法能求一些比拟困难的问题，此外，其数值计算也比拟稳定.多步拟牛顿法一般的拟牛顿方法在每一步的迭代中，仅利用上一步产生的梯度信息，建立—个拟牛顿方程，进而求得目标函数Hesse阵的近似。如果将前步的梯度值都纳入到计算过程中，是否会取得更好的效果？基于这样的想法Ford和Moghrabi于1993年提出了多步拟牛顿法。多步拟牛顿法的根本思想如下：记为中的一条可微路径。对向量应用链式法那么，在曲线上对应点处，满足牛顿等式，利用上式来建立拟牛顿方程.记.视为一条通过和两迭代点的直线.即，那么由式有，，并且.由于很难精确求得Hesse阵，用向后差分来近似,由式可估算导数在处的值.将和代入中取可得.标准拟牛顿打用近似值来代替Hesse阵，由上试满足.这就是标准的拟牛顿方程.多步拟牛顿法是上述单步牛顿法的推广，其多步拟牛顿方程的推导过程与相类似.假设前个迭代点以及相应的梯度值信息。同样记为中的一条可微路径，但此时不是一条直线，可以定义为一个m次的插值多项式，其插值基点为的取值不同，将得到不同的插值函数.由前面讨论的拟牛顿方程,的一个很自然的取法是选择等距的值,即取当然除这种取法外,值还有很多其他的有效取法.标准的拟牛顿方程是取及，得到的.构造的Lagrange插值多项式,这里的是基于集合的标准的次拉格朗日多项式的第项，即将视为的函数，由标准拟牛顿方程的推导过程及式，可用Lagrange插值多项式来近似.由于对应于，在中令，接下来计算和的值.对式求导得，对式求导得,这里，.由此，可类似推出多步拟牛顿法的拟牛顿方程,其中是的近似.对式和式进行重新整理，和可以分别用和的线性组合来表示，即，在多步法中，使用〔例如〕“DFP型”等校正公式得到新Hesse阵逆近似，这里分别以和来代替和，.根据变量的取值不同，可得到不同的插值函数，由此可得不同的算法。如单空间法、累积法、不动点法等.下面给出多步拟牛顿算法的步骤.步0.选取为问题所能容忍的值.设,;计算和.步1.如果，那么停止.步2.计算搜索方向.如果(为的维数)并且那么.步3.利用从出发沿方向的线搜索，计算满足条件的.步4.如果仅迭代一步，那么设,;否那么按照和计算和.步5.如果并且，那么取.步6.校正迭代矩阵.根据计算..转步1.总结拟牛顿法是无约束最优化方法中最有效的一类算法,其理论分析与算法改良研究已有很多成果.它有许多的优点，比方，迭代中仅需一阶导数，不必计算Hessian矩阵，当使正定时，算法产生的方向均为下降方向，并且这类算法具有二次终止性，对于一般情形，具有超线性收敛速率，而且还具有步二阶收敛速率,可见，拟牛顿法集中了许多算法的长处.拟牛顿法的缺点是所需存储量较大，对于大型问题，可能遇到存储方面的困难。虽然拟牛顿法的收敛速度快且相应的全局收敛性研究也非常成熟，但对于求解非线性方程组问题的全局收敛性研究却很少.参考文献：[1]徐成贤，陈志平，李乃成.近代优化方法.北京：科学出版社，2002.[2]GriewankA，The'global’convergenceofBroyden-likemethodswithasuitablelinesearch．JournalAustralianMathematicalSociety,1986，28(1)：75-92[3]LiDH，FukushimaM．Aderivative-freelinesearchandglobalconvergenceofBroyden’S-likemethodfornonlinearequations．OptimizationMethodsandSoftware，2000，13(3)：181—201[4]LiDH，FukushimaM．AgloballyandsupertinearconvergentGanss-Newton-basedBFGSmethodsforsyalmetricnonlinearequations．SIAMJournalonNumericalAnalysis，1999，37(1)：152-172[5]CruzW，RaydanM．Nonmonotonespectralmethodsforlargescalenonlinearsysterms．OptimizationMethodsandSoftware，2003，18(5)：583-589[6]ZhangL，ZhouWJ．Spectralgradientprojectionmethodforsolvingnonlinearmo