BFGS算法分析与实现

《《最最优优化化方方法法》》课课程程设设计计题目：BFGS算法分析与实现院系：数学与计算科学学院专业：统计学姓名学号：左想1200720133指导教师：李丰兵日期：2014年01月22日摘要在求解无约束最优化问题的众多算法中,拟牛顿法是颇受欢迎的一类算法。尤其是用于求解中小规模问题时该类算法具有较好的数值效果。BFGS算法被认为是数值效果最好的拟牛顿法，其收敛理论的研究也取得了很好的成果.在一定的条件下，BFGS算法具有全局收敛性和超线性收敛速度。然而，对于大规模最优化问题来求解，包括BFGS算法在内拟牛顿法具有明显的缺陷。有许多的例子表明，一旦处理问题很大时，一些对小规模问题非常成功的算法变得毫无吸引力。究其原因，主要是由于在中小型问题一些不太重要的因素在求解大规模问题时，变得代价很高。随着速度更快及更复杂的计算机的出现，增强了我们的计算处理能力。同时也为我们设计算法带来了新的课题。并行计算机的发展为求解大规模最优化问题提供了一条新途径。关键词：BFGS拟牛顿法；无约束最优化问题；大规模问题AbstractQuasi-Newtonmethodsarewelcomenumericalmethodsforsolvingoptimizationproblems.Theyareparticularlyeffectivewhenappliedtosolvesmallormiddlesizeproblems.BFGSmethodisregardedasthemosteffectivequasi-Newtonmethodduetoitsgoodnumericalperformance.Italsopossessesverygoodglobalandsuperlinearconvergenceproperties.Ontheotherhand,however,whenappliedtosolvelargescaleproblems,quasi-NewtonmethodsincludingBFGSmethoddonotperformwell.Themajordrawbackforaquasi-Newtonmethod,whenusedtosolvelargescaleoptimizationproblem,isthatthematrixgeneratedbythemethoddoesnotretainthesparsityoftheHessianmatrixoftheobjectivefunction.Thereareexamplesshowingthatmanysuccessmethodsforsolvingsmall-sizedoptimizationbecomeunattractiveoncetheproblemtobetackledislarge.Animportantreasonforthisfeatureisthatsomeprocessthatisimportantforsmallproblemsmaybecomeveryexpensiveforlargescaleproblems.Thefastdevelopmentofcomputerhasenhancedourabilitytosolvelargescaleproblems.Inparticular,theparallelcomputerprovidesusanewwaytosolvelargescaleproblemsefficiently.Inrecentyears,therehasbeengrowinginterestinthestudyinparallelmethods.Ithasbeenfoundthatmanygoodmethodsthatareefficientforsolvingsmallandmiddlesizeproblemscanbeparallized.KeyWords:BFGSquasi-Newtonmethod;unconstrainedoptimizationproblem,largescaleproblem目录1、引言........................................................................................错误!未定义书签。2、BFGS算法及其修正形式................................................................................32.1拟牛顿法...........................................................................................................32.2BFGS算法........................................................................................................42.3修正形式的BFGS算法...................................................................................53、BFGS算法对大规模问题研究.......................................................................54、数值分析...............................................................................................................74.1代码实现...........................................................................................................74.3算法测试...........................................................................................................84.4结果分析...........................................................................................................85、总结.......................................................................................................................95.1总结概括...........................................................................................................95.2个人感言...........................................................................................................96、参考文献：.......................................................................................................10最优化课程设计11.引言最优化问题在经济计划，生产管理，交通，运输，物理和通信等居多领域有广泛而又深入的应用。本文主要考察无约束最优化问题。无约束最优化问题的数学模型如下:min(),nfxxR　　　(1.1)其中:nfRR是一个连续可微函数.我们用f和f分别表示在处的梯度和Hessian阵。在求解上述无约束最优化问题时，通常采用算法是迭代算法，其迭代格式如下:1kkkkxxd，(1.2)其中为搜索方向，一般满足f，因而是f在处的一个下降方向。称为步长，由线性搜索得到，为简便起见，在整篇文章中，我们分别把f记为，f记为f，f记为f。上面的迭代法称为下降算法，自上世纪70年代以来，下降算法的研究得到了飞速发展。迄今为止，已提出了许多的下降算法，这些算法具有各自的优缺点。常用的算法有：最速下降法.即取。该算法的优点是计算简便且存储量小，可用于大规模最优化问题求解。但该算法仅有线性收敛速度，收敛速度太慢。牛顿法.即取=f。其中f表示f在处的Hessian阵。该算法的优点是收敛速度快，可达到二阶收敛速度，但每次迭代需计算目标函数Hessian矩阵，计算量大。拟牛顿法.即取。其中是的近似。拟牛顿法的优点是超线性收敛速度，而且，大多数拟牛顿法可产生下降方向，但拟牛顿法需贮存一个矩阵。共轭梯度法.即取{，，(1.3)最优化课程设计2其中参数的选取依赖于不同的共轭梯度法。优点在于克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需的二阶导数信息。所以对大规模问题来说，也是一种很不错的算法。超记忆梯度法.即取{，∑，(1.4)其中当时，||||||||||∑Miele和Cantrell研究了这种记忆梯度法(memorygradientmethod)。同时Cantrell发现，当用于二次函数极小值问题求解时,记忆梯度法与Fletcher--Reeves算法是一致的.Cragg和Levy进一步地研究了一种超记忆梯度法(super-memorygradientmethod),实际上是记忆梯度法的一般化.其他有关超记忆梯度法可参考文献[3,4]等。无论是记忆梯度法还是超记忆梯度法,都比共轭梯度法更为有效,因为它使用了更多的先前迭代信息,并且增加了参数的自由度,但在形式上与共轭梯度法很相似,并且避免了计算与Hessian阵有关的矩阵,尽管收敛速度不如拟牛顿法,但也适合于大规模稀疏问题的求解。在选取步长时，通常有如下几种方式：精确搜索:即满足f(1.5)此种搜索由于计算量大，所以在实际中很少采用。非精确搜索:(i)Armijo搜索:给定σ,步长满足下列不等式fff,(1.6)最优化课程设计2确定步长的一种方式是令其为集合满足条件(1.6)的最大者。最优化课程设计3(ii)Wolfe-Powell搜索:即步长同时满足下面的两个不等式:{fff；ff，(1.7)其中为常数,满足2.BFGS算法及其修正形式自上世纪七十年代以来，关于拟Newton法的收敛性研究取得了重大进展。假设目标函数f(x)是凸的，采用精确线性搜索时，Powell等证明了Broyden族算法具有全局收敛性和超线性收敛速率。当采用非精确线性搜索时，即Wolfe-Powell准则确定步长，Byrd等在1987年证明了Broyden族算法(除DFP算法外)具有全局收敛性。若假设目标函数是一致凸的，其二阶导数矩阵在极小点附近满足Lipschitz条件，且在正定的条件下，还证明了其收敛速度是Q-超线性的.Bryd和Nocedal证明了采用Armijo线性搜索时，BFGS方法的全局收敛性等在文献得出：当目标函数是伪凸函数时，Broyden算法依然具有全局收敛性.Li证明了：当目标函数是凸二次函数，DFP算法仍然具有全局收敛性。在2001年，Li和Fukushima在文献提出了一种求解非凸函数极小值问题的修正拟牛顿法，并证明了修正的拟牛顿法的全局收敛性，并在适当的假设条件下，证明了超线性收敛速率。本文将侧重于对拟牛顿法中BFGS算法的研究.在众多求解无约束最优化的拟牛顿法中,BFGS(Broyden,Fletcher,Goldfarb,Shanno)法被认为是