BFGS算法分析与实现(共14页)

《BFGS算法分析与实现(共14页)》由会员分享，可在线阅读，更多相关《BFGS算法分析与实现(共14页)（19页珍藏版）》请在装配图网上搜索。

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

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

3、ive when applied to solve small or middle size problems. BFGS method is regarded as the most effective quasi-Newton method due toits good numerical perfor mance. It also possesses very good global and superlinear con vergen ceproperties. On the other hand, however, when applied to solve larg escalep

4、roblems, quasi-Newton methods including BFGS method don ot perform well. Themajor drawback for a quasi-Newton method, when used to solve large scaleoptimization problem, is that the matrix gener ated by the method does not retain thesparsity of the Hessian matrix of the objective function. There are

5、 examples showing that many success methods for solving small-sized optimization become unattractive once the problem to be tackled is large. An important reason for thisfeature is that some process that is important for small problems may become veryexpensive for large scale problems.The fast devel

6、opment of computer has enhanced our ability to solve large scaleproblems. In particular, the parallel computer provides us a new way to solve largescale problems efficiently. In recent years, there has been growing interest in the studyin parallel methods. It has been found that many good methods th

7、at are efficient forsolving small and middle size problems can be parallized. Key Words: BFGS quasi-Newton method; unconstrained optimization problem, large scale problem目 录专心-专注-专业1 .引言最优化问题在经济计划，生产管理，交通，运输，物理和通信等居多领域有广泛而又深入的应用。本文主要考察无约束最优化问题。无约束最优化问题(UC)的数学模型如下: (1.1)其中是一个连续可微函数.我们用 x和 2 (x)分别表示f在

8、x 处的梯度和 Hessian 阵。在求解上述无约束最优化问题时，通常采用算法是迭代算法，其迭代格式如下: ， (1.2)其中dk为搜索方向，一般满足 (xk)Tdk0称为步长，由线性搜索得到，为简便起见，在整篇文章中，我们分别把(xk)记为gk， (xk)记为k ， (x*)记为* 。上面的迭代法称为下降算法，自上世纪 70 年代以来，下降算法的研究得到了飞速发展。迄今为止，已提出了许多的下降算法，这些算法具有各自的优缺点。 常用的算法有： 最速下降法. 即取dk=-gk。该算法的优点是计算简便且存储量小，可用于大规模最优化问题求解。但该算法仅有线性收敛速度，收敛速度太慢。 牛顿法.即取dk

9、=-2(xk)-1gk。其中2 (xk)表示在xk处的Hessian阵。该算法的优点是收敛速度快，可达到二阶收敛速度，但每次迭代需计算目标函数Hessian矩阵，计算量大。 拟牛顿法. 即取dk=-Hkgk。其中Hk 是2(xk)-1的近似。拟牛顿法的优点是超线性收敛速度，而且，大多数拟牛顿法可产生下降方向，但拟牛顿法需贮存一个矩阵。共轭梯度法.即取dk=-gk ，k=1-gk+k*dk-1，k2 (1.3)其中参数k的选取依赖于不同的共轭梯度法。优点在于克服了最速下降法收敛慢的缺点，又避免了存贮和计算牛顿法所需的二阶导数信息。所以对大规模问题来说，也是一种很不错的算法。超记忆梯度法. 即取d

10、k=-gk ，k=1-i=1mk-i+1*gk-i+1，k2 (1.4)其中当km时，k-i+1=m-1gk2gk2+gkTgk-i+1,i=1,2,3m;k=1-i=2mk-i+1Miele 和 Cantrell 研究了这种记忆梯度法(memory gradient method)。同时 Cantrell发现，当用于二次函数极小值问题求解时,记忆梯度法与 Fletcher- -Reeves 算法是一致的.Cragg 和 Levy 进一步地研究了一种超记忆梯度法(super-memory gradient method),实际上是记忆梯度法的一般化.其他有关超记忆梯度法可参考文献3,4等。无论

11、是记忆梯度法还是超记忆梯度法,都比共轭梯度法更为有效,因为它使用了更多的先前迭代信息,并且增加了参数的自由度,但在形式上与共轭梯度法很相似,并且避免了计算与Hessian阵有关的矩阵,尽管收敛速度不如拟牛顿法,但也适合于大规模稀疏问题的求解。在选取步长k时，通常有如下几种方式：精确搜索: 即k满足 k=argmin0(xk+dk) (1.5)此种搜索由于计算量大，所以在实际中很少采用。非精确搜索:(i) Armijo 搜索:给定 (0,1),步长k满足下列不等式 xk+dkxk+ xkTdk , (1.6)确定步长k的一种方式是令其为集合1,2,3, 满足条件(1.6)的最大者。(ii) Wo

12、lfe-Powell 搜索: 即步长同时满足下面的两个不等式: xk+kdkxk+1 xkTdk；xk+kdkTdk2 xkTdk， (1.7)其中1,2为常数,满足0112,1212. BFGS 算法及其修正形式自上世纪七十年代以来，关于拟 Newton 法的收敛性研究取得了重大进展。 假设目标函数 f(x)是凸的，采用精确线性搜索时，Powell 等证明了 Broyden 族算法具有全局收敛性和超线性收敛速率。 当采用非精确线性搜索时，即Wolfe-Powell准则确定步长，Byrd等在1987年证明了Broyden 族算法(除DFP 算法外)具有全局收敛性。 若假设目标函数是一致凸的，其

13、二阶导数矩阵在极小点附近满足 Lipschitz 条件，且在正定的条件下，还证明了其收敛速度是 Q-超线性的. Bryd 和 Nocedal 证明了采用 Armijo 线性搜索时，BFGS 方法的全局收敛性等在文献得出：当目标函数是伪凸函数时，Broyden 算法依然具有全局收敛性.Li 证明了：当目标函数是凸二次函数，DFP 算法仍然具有全局收敛性。在 2001 年，Li 和 Fukushima 在文献提出了一种求解非凸函数极小值问题的修正拟牛顿法，并证明了修正的拟牛顿法的全局收敛性，并在适当的假设条件下，证明了超线性收敛速率。本文将侧重于对拟牛顿法中 BFGS 算法的研究. 在众多求解无约

14、束最优化的拟牛顿法中, BFGS(Broyden,Fletcher, Goldfarb,Shanno)法被认为是数值效果最好的方法.该方法中Bk 的修正公式为 Bk+1=Bk+ykykTykTsk-BkskskTBkskTBksk， (2.1)其中sk=xk+1-xk,yk= f xk+1- xk.修正公式(2.1)具有如下重要性质:定理 2.1 设Bk+1是由 BFGS 修正公式产生,若矩阵Bk是对称正定的且ykTsk0，则矩阵Bk+1也是正定的。求解(1.1)的 BFGS 算法步骤如下：算法 2.1步 1 :取初始点, x0 Rn，初始对称正定矩阵B0Rn*n。精度 0。令 k = 0。步

15、 2 :若| f xk|，则算法终止。得问题的解xk，否则，转步 3。步 3 :解线性方程组 Bkd+ f xk=0 (2.2)得解dk .转步 4.步 4 :由线性搜索方法确定步长k.步 5 :令xk+1=xk+kdk.若| f xk|，则得解xk+1.否则，由拟牛顿修正公式(2.1)确定Bk+1.步 6 :令 k=k+1，转步 2.若将算法(2.1)中的Bk的修正公式换成其它公式，则得相应的拟牛顿法的计算步骤。对于非凸函数的最优化问题，即使采用精确搜索，标准的 BFGS 方法也不具有全局收敛性.为了克服 BFGS 算法的这种缺陷，下面简单扼要地介绍 BFGS 的修正形式MBFGS(Modi

16、fied BFGS)算法及保守 BFGS 修正CBFGS(caution BFGS)算法.详细内容可看参考文献.MBFGS 法的修正公式与标准的 BFGS 修正公式形式上是完全相同的，所不同的是其中yk的定义，LiFukushima的修正 BFGS 公式中的yk定义如下: yk=k+vk(xk+1-xk)，其中: k= f xk+1- f xk。为了保证Bk+1的对称正定性.可以通过对参数vk的调整，使得 ykTsk0， k 0, (2.3)满足上式的vk的取法有许多.例如vk可由下式确定vk=ctk| xk|n，其中，tk=1+max-kTsk|sk|2,0c-1| xk|-n，其中 u 0

17、, c 0是常数。MBFGS 算法的一个重要优点是:该算法用于求解非凸函数极小值问题时，也具有全局收敛性.而且Bk的对称正定性与算法的线性搜索以及目标函数的凸性无关.文献17提出了一种保守 BFGS 修正CBFGS 修正方式.具体如下: Bk+1=Bk-BkskskTBkBkskTBk+ykykTykTsk ，ykTsk|sk|2| f xk|uBk ，ykTsk|sk|2| f xk|u， (2,4)其中，0, u0是常数。容易看出，若Bk对称正定，则有 CBFGS 公式产生的矩阵序列Bk 满足ykTsk0。因此，对所有的 k 0，矩阵Bk对称正定.该性质与算法的线性搜索以及函数f(x)的凸

18、性无关.此外，若不等式 ykTsk|sk|2| xk|u， (2,5)成立，则算法还原为标准的 BFGS 算法.因而，算法的仿射不变性成立。3.BFGS算法对大规模问题研究所谓的大规模问题，就是所涉及的变量的维数很高，通常上千维，有的甚至达到了万维，百万维的. 一般来说，大规模问题 f(x)的二阶导Hessian阵f(x)2常常是对称的、正定的，尤其具有某种稀疏的结构.在求解大规模问题时，我们总是希望得到收敛速度快、计算量少和存贮量小的算法. 而用于求解中小型最优化问题的传统算法，来求解大规模问题时，许多的优点已经变得不太重要，(比如数值效果较好的 BFGS 算法，虽然校正矩阵Bk+1能够继承

19、正定性和对称性，却不能继承其稀疏性)，且在经过一定数量的迭代后，先前的信息有可能被舍弃，算法必须计算新的信息重新开始,例如共轭梯度法.下面简要地介绍几种大规模算法：Nocedal 研究了一种有限记忆拟牛顿法.动机是当存储成为关键因素,怎样利用BFGS拟牛顿法来求解大规模最优化问题.其基本思想是利用最新m步迭代信息去产生新的近似 Hessian 矩阵.在每次迭代时用最新的信息去取代旧的信息.同时数值结果也表明逐渐增加迭代信息时，数值效果也会逐渐改善. 在下一节将作详细的介绍。求解具有线性方程组 Hd = g的大规模问题最常用的方法是预处理共轭梯度法(PCG)，可见文献19。考虑求解线性方程组Ax

20、 =b其中 A是稀疏、对称和正定矩阵.共轭梯度法是有效的方法之一，但由于其收敛性受到依赖于系数矩阵 A的谱条件数，即最大特征值和最小特征值之比. 为了改善收敛速度，就要设法改善矩阵 A的条件数. 通常是用预处理技术来改进共轭梯度法，其做法是使用左或右预条件矩阵M 使得方程组变成易于求解的形式：AM-1y=b ，x=M-1y或者M-1Ax=M-1b然后使用共轭梯度法求之。构造预条件矩阵的方法很多，如不完全分解法，结合实际问题的区域分解做预条件矩阵，基于迭代法的多项式预条件技术，基于系数矩阵的近似逆的预条件技术等。4数值实验无约束优化问题在matlab中可由三个功能函数实现，即函数fminbnd(

21、单变量的最小函数值)、fminsearch (多变量的最小函数值)、fminune(多变量函数最小值时的变量值)其中fminbnd和fminsearch的优化算法简单，处理简单问题方便，但对复杂问题却力不从心；fminunc的算法复杂，可解决较为复杂的问题，且提供了几种可供选择的不同算法Fminunc算法为无约束优化提供了大型优化和中型优化算法引，由option -s中的参数控制；Fminunc算法同时也为中型优化算法的搜索方向提供了4种算法，由options中的参数hessupdate控制，当hessupdate=bfgs(默认值)，拟Newton的BFGS公式；当hessupdate=df

22、p，拟Newton的DFP公式。实例分析：分别用BFGS方法和DFP方法求解如下的Powell奇异函数的最小值点f=(x1+x2)2+5(x3-x4)2+(x2-2x3)4+10(x1-x4)4解：可以看出，最小值点即为(0 0 0 0)点此例只是为比较各方法的应用，并无大的实际意义。在matlab里编制的程序并运行结果如下：functionx,val,k=bfgs(fun,gfun,x0)maxk=500;%给出最大迭代次数rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=length(x0);Bk=eye(n);%Bk=feval(Hess,x0);while(k

23、maxk)gk=feval(gfun,x0);%计算梯度if(norm(gk)epsilon),break;end%检验终止准则dk=-Bkgk;%解方程组，计算搜索方向m=0;mk=0;while(m20)%用Armijo搜索求步长newf=feval(fun,x0+rhom*dk);oldf=feval(fun,x0);if(newf0)Bk=Bk-(Bk*sk*sk*Bk)/(sk*Bk*sk)+(yk*yk)/(yk*sk);endk=k+1;x0=x;endval=feval(fun,x0);function f=pfun(x)f=(x(1)+x(2)2+5*(x(3)-x(4)2+

24、(x(2)-2*x(3)4+10*(x(1)-x(4)4x0=3,-1,0,1%BFGS算法实现%采用混合插值法options(6)=0;Options(7)=0;fminunc(pfun,x0,Options)ans=0.0027 -0.0003 -0.0057 -0.0057%采用立方差值法options(6)=0;Options(7)=1;fminunc(pfun,x0,Options)ans=-0.0156 0.0015 -0.0146 -0.0146%DFP算法实现%采用混合插值法options(6)=1;Options(7)=0;fminunc(pfun,x0,Options)an

25、s=0.0214 -0.0021 0.0119 0.0120%采用立方差值法options(6)=1;Options(7)=1;fminunc(pfun,x0,Options)ans=-0.0139 0.0014 -0.0064 -0.0064其中对函数fminunc来说。Options(6)为控制搜索方向算法，取默认值O时，是BFGS方法；取1时为DFP方法。0ptionsw(7)为控制插值法，其中取默认值0时是混合插值；取1时为立方插值。5总结5.1总结概括在当今社会，优化问题已成为科学研究、工程设计和经济管理等许多领域中一类重要问题，而许多科技人员往往又只注重寻找新方法。求解最优问题是一

26、个艰难而具有挑战性的过程，最优化方法是近几十年形成的一门运用研究各种系统的优化途径及方案，为决策者提供科学决策的依据的学科，它涵盖了无约束最优化问题、凸集与凸函数、等式约束最优化问题和不等式约束最优化问题等知识点。本次课程设计，我们小组成员通过老师的点拨以及激烈的讨论，对该门课程中的无约束最优化问题进行了一定程度地了解和研究，无约束最优化方法的核心问题是选择搜索方向。本文主要针对非线性优化问题，采用拟Newton法中的DFP算法和BFGS算法进行一些探讨；并利用MATLAB语言通过几个算例对其进行了仿真分析，认为BFGS算法是拟Newton算法中的最有效的方法之一；同时认为用MATLAB编写程

27、序来研究优化问题，能大大减轻设计人。5.2个人心得通过本次试验，我学会了应该怎么从一个问题出发，对该问题进行研究：首先要对问题有一个大概的了解，通过查阅资料，对问题有了深入了解，然后确定问题的研究方向，以及要研究方向所需要进行的工作，然后一步步去完成，如：在优化问题中，我了解到，根据目标函数、约束函数和变量的不同，可以将其大致分为线性优化、非线性优化、二次优化、多任务目标优化等。而对于非线性优化问题，比较好的有BFGS算法和DFP算法。BFGS算法的适用范围很广，其算法也有很多研究方向。6参考文献1 张光澄.非线性最优化计算方法M.北京：高等教育出版社，2005.2 席少霖.非线性最优化计算方法M.北京：高等教育出版社，1992.3 薛嘉庆.最优化原理与方法M.北京：清华大学出版社，2003.4 袁亚湘，孙文瑜.最优化理论与方法M.北京:科学出版社，1993.