BFGS算法分析与实现

《BFGS算法分析与实现》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、《最优化方法》课程设计题目：BFGS算法分析与实现院系：数学与计算科学学院专业：统计学姓名学号：左想1200720133指导教师：李丰兵日期：2014年01月22日摘要在求解无约束最优化问题的众多算法中,拟牛顿法是颇受欢迎的一类算法。尤其是用于求解中小规模问题时该类算法具有较好的数值效果。BFGS算法被认为是数值效果最好的拟牛顿法，其收敛理论的研究也取得了很好的成果.在一定的条件下，BFGS算法具有全局收敛性和超线性收敛速度。然而，对于大规模最优化问题来求解，包括BFGS算法在内拟牛顿法具有明显的缺陷。有许多的例子表明，一旦

2、处理问题很大时，一些对小规模问题非常成功的算法变得毫无吸引力。究其原因，主要是由于在中小型问题一些不太重要的因素在求解大规模问题时，变得代价很高。随着速度更快及更复杂的计算机的出现，增强了我们的计算处理能力。同时也为我们设计算法带来了新的课题。并行计算机的发展为求解大规模最优化问题提供了一条新途径。关键词：BFGS拟牛顿法；无约束最优化问题；大规模问题AbstractQuasi-Newtonmethodsarewelcomenumericalmethodsforsolvingoptimizationproblems.They

3、areparticularlyeffectivewhenappliedtosolvesmallormiddlesizeproblems.BFGSmethodisregardedasthemosteffectivequasi-Newtonmethodduetoitsgoodnumericalperformance.Italsopossessesverygoodglobalandsuperlinearconvergenceproperties.Ontheotherhand,however,whenappliedtosolvela

4、rgescaleproblems,quasi-NewtonmethodsincludingBFGSmethoddonotperformwell.Themajordrawbackforaquasi-Newtonmethod,whenusedtosolvelargescaleoptimizationproblem,isthatthematrixgeneratedbythemethoddoesnotretainthesparsityoftheHessianmatrixoftheobjectivefunction.Therearee

5、xamplesshowingthatmanysuccessmethodsforsolvingsmall-sizedoptimizationbecomeunattractiveoncetheproblemtobetackledislarge.Animportantreasonforthisfeatureisthatsomeprocessthatisimportantforsmallproblemsmaybecomeveryexpensiveforlargescaleproblems.Thefastdevelopmentofco

6、mputerhasenhancedourabilitytosolvelargescaleproblems.Inparticular,theparallelcomputerprovidesusanewwaytosolvelargescaleproblemsefficiently.Inrecentyears,therehasbeengrowinginterestinthestudyinparallelmethods.Ithasbeenfoundthatmanygoodmethodsthatareefficientforsolvi

7、ngsmallandmiddlesizeproblemscanbeparallized.KeyWords:BFGSquasi-Newtonmethod;unconstrainedoptimizationproblem,largescaleproblem目录1、引言12、BFGS算法及其修正形式32.1拟牛顿法32.2BFGS算法42.3修正形式的BFGS算法53、BFGS算法对大规模问题研究54、数值分析74.1代码实现74.3算法测试84.4结果分析85、总结95.1总结概括95.2个人感言96、参考文献：10最优化课程设

8、计1.引言最优化问题在经济计划，生产管理，交通，运输，物理和通信等居多领域有广泛而又深入的应用。本文主要考察无约束最优化问题。无约束最优化问题(UC)的数学模型如下:(1.1)其中是一个连续可微函数.我们用∇x和∇2(x)分别表示f在x处的梯度和Hessian阵。在求解上述无约束最优化问题