《最优化方法》课程设计题目:BFGS算法分析与实现院系:数学与计算科学学院专业:统计学姓名学号:吕效忠1200720225指导教师:李丰兵日期:2015年01月22日摘要在求解无约束最优化问题的众多算法中,拟牛顿法是颇受欢迎的一类算法,尤其是用于求解小规模问题时,该类算法具有良好的数值效果,BFGS算法被认为时数值效果最好的拟牛顿法,并且具有全局收敛性和超线性收敛速度。随着速度更快及更复杂的计算机的出现,增强了我们的计算处理能力,同时也为我们设计算法带来了新的课题,并行计算机的发展为求解大规模最优化问题提供了一条新途径,对求解中小规模问题中数值效果好的算法并行化以用于大规模问题的求解受到广泛欢迎。本文提出一种求解无约束最优化问题的并行BFGS算法。无约束优化问题的核心是选择搜索方向。而BFGS算法的基本思想是在牛顿法的第二步中用Hesse矩阵2=)kkGfx(的某个近似矩阵kB取代kG。从而找出搜索方向,沿着这组方向进行搜索,求出目标函数的极小点。这种算法具有N步终止性。再结合该算法编写MATLAB程序,求解相同的无约束优化问题。关键词:无约束优化;拟牛顿法;BFGS算法;超线性收敛;MATLABAbstractInmanyalgorithmsthatsolveunconstrainedoptimizationproblems,thequasi-Newtonmethodisapopularkindofalgorithms.Especiallyitisusedtosolvethesmallproblem.Thisalgorithmhasgoodnumericalresults.TheBFGSalgorithmisconsideredthebestnumericaleffectofquasi-newtonmethod,andithasglobalconvergenceandsuperlinearconvergencerate.Withtheemergenceoffasterandmoresophisticatedcomputers,ourcomputingabilityhasimproved.Butitalsoforourdesignalgorithmhasbroughtthenewtask.Thedevelopmentofparallelcomputerforsolvinglarge-scaleoptimizationproblemprovidesanewway.Tosolvetheproblemofsmallandmedium-sizednumericalalgorithmwithgoodeffectinparalleltothepopularityoflargescaleproblems.ThispaperproposesaparallelBFGSalgorithmforsolvingunconstrainedoptimizationproblems.Attheheartoftheunconstrainedoptimizationproblemsischoosesearchdirection.TheBFGSalgorithmisthebasicideaoftheNewtonmethodthatusedinthesecondstepinthereplacedoneofHessematrix.Tofindoutthesearchdirection,alongthisdirection,thissetofdirectiontheminimumpointoftheobjectivefunction.ThisalgorithmhasNstepstermination.CombiningwritetheMATLABprogram,thealgorithmisemployedtosolveunconstrainedoptimizationproblemsofthesame.Keywords:Unconstrainedoptimization;Quasi-Newtonmethod;BFGSalgorithm;Superlinearconvergence;MATLAB目录1、引言........................................................................................................................12、BFGS算法综述.................................................................................................12.1拟牛顿法及其性质...........................................................................................12.2BFGS算法.........................................................................................................33、数值实验..............................................................................................................63.1代码实现...........................................................................................................63.2算法测试...........................................................................................................73.3结果分析...........................................................................................................84、总结.......................................................................................................................84.1总结概括...........................................................................................................84.2个人感言...........................................................................................................95、参考文献:.........................................................................................................9最优化方法课程设计11、引言在最优化的问题中,线性最优化至少可以使用单纯形法求解,但对于非线性优化问题,牛顿法提供了一种求解的办法。牛顿法的优点是具有二次收敛速度,但是当Hesse矩阵2=)kkGfx(不正定时,不能保证所产生的方向是目标函数在kx处的下降方向。特别地,当kG奇异时,算法就无法继续进行下去,尽管修正的牛顿法可以克服这一缺点,但修正参数的选取很难把握,过大或过小都会影响到收敛速度,此外,牛顿法的每一迭代步都需要目标函数的二阶导数,即Hesse矩阵,对于大规模问题,其计算量是惊人的。由此引出了一种新的求解非线性优化问题的方法——拟牛顿法。拟牛顿法(Quasi-NewtonMethods)是求解非线性优化问题最有效的方法之一,于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.Fletcher和M.J.D.Powell证实了这种新的算法远比其他方法快速和可靠,使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里,拟牛顿方法得到了蓬勃发展,出现了大量的变形公式以及数以百计的相关论文。其中BFGS就是拟牛顿法中的一种方法。2、BFGS算法的综述2.1拟牛顿法及其性质拟牛顿法的基本思想是在牛顿法的第二步中用Hesse矩阵2=)kkGfx(的某个近似矩阵kB取代kG。通常,kB应具有以下三个特点:(1)在某种意义下有kkBG,使得相应的算法产生的方向近似于牛顿方向,以确保算法具有较快的收敛速度;(2)对所有的k,kB是对称正定的,从而使得算法所产生的方向是函数f在kx处下降方向;(3)矩阵kB更新规则相对比较简单,即通常采用秩1或秩2矩阵进行校正。下面介绍满足这三个特点的矩阵kB的构造,设:nf在开集nD上二次连续可微,那么f在1kx处二次近似模型为最优化方法课程设计21111111()()(()()()2kkTkkTkkfxfxgxxxxGxx)(2.1)对上式求导得111()()kkkgxgGxx(2.2)令kxx,位移1kkksxx,梯度差1kkkygg,则有1kkkGsy(2.3)注意到对于二次函数f,上式是精确成立的。现在,要求在拟牛顿法中构造Hesse矩阵的近似矩阵kB满足这种关系式,即1kkkBsy(2.4)式(2.4)通常称为拟牛顿方程或拟牛顿条件。令111kkHB,则得到拟牛顿方程的另一种形式:1kkkHys(2.5)其中1kH为Hesse矩阵逆的近似。搜索方向由kkkdHg或kkkBdg确定。根据kB(或kH)的第三个特点,可令1kkkBBE,1kkkHHD(2.6)其中kE,kD为秩1或秩2矩阵,通常将拟牛顿方程(2.4)(或(2.5))和校正规则(2.6)所确立的方法称为拟牛顿法。下面介绍一对称秩1校正公式。在(2.6)中取()kkTkEuu(秩1矩阵),其中,knu.由拟牛顿方程(2.4)得[()]kkTkkkBuusy(2.7)即有[()]kTkkkkkusuyBs(2.8)式(2.8)表明向量ku平行kkkyBs,即存在常数使得()kkkkuyBs.因此有2()()kkkkTkkkEyBsyBs(2.9)于是,由(2.8)得最优化方法课程设计32[()]()()kkTkkkkkkkkyBssyBsyBs(2.10)由此,若()0kkTkkyBss,则可取2[()]1kkTkkyBss,即2()()1,()()kkkkTkkkkkTkkkTkkkyBsyBsEyBssyBss(2.11)故得对称秩1的校正公式如下:1()()()kkkkTkkkkkkTkkyBsyBsBByBss(2.12)类似地,利用拟牛顿方程(2.1.5),对称秩1的修正可得1()()()kkkkTkkkkkkTkksHysHyHHsHyy(2.13)有了对称秩1校正公式后,利用它可以构造求解一个无约束优化问题的一个拟牛顿算法,步骤如下:算法2.1(对称秩1算法)步0给定初始点0nx,终止误差01,初始对称正定矩阵0H(通常取单位矩阵nI),令0k.步1若kg,停止运算,输出kx作为近似极小点。步2计算