BFGS算法实现课程设计

1、最 优 化 方 法课 程 设 计题 目：BFGS算法分析与实现院 系： 数学与计算科学学院 专 业： 统计学 姓名学号： 吕效忠 指导教师： 李丰兵 日 期： 2015 年 01 月 22 日摘 要在求解无约束最优化问题的众多算法中，拟牛顿法是颇受欢迎的一类算法，尤其是用于求解小规模问题时，该类算法具有良好的数值效果，BFGS算法被认为时数值效果最好的拟牛顿法，并且具有全局收敛性和超线性收敛速度。随着速度更快及更复杂的计算机的出现，增强了我们的计算处理能力，同时也为我们设计算法带来了新的课题，并行计算机的发展为求解大规模最优化问题提供了一条新途径，对求解中小规模问题中数值效果好的算法并行化以用

2、于大规模问题的求解受到广泛欢迎。本文提出一种求解无约束最优化问题的并行BFGS算法。无约束优化问题的核心是选择搜索方向。而BFGS算法的基本思想是在牛顿法的第二步中用Hesse矩阵的某个近似矩阵取代。从而找出搜索方向，沿着这组方向进行搜索，求出目标函数的极小点。这种算法具有N步终止性。再结合该算法编写MATLAB程序，求解相同的无约束优化问题。关键词：无约束优化；拟牛顿法；BFGS算法；超线性收敛； MATLAB AbstractIn many algorithms that solve unconstrained optimization problems,the quasi-Newton

3、method is a popular kind of algorithms. Especially it is used to solve the small problem. This algorithm has good numerical results. The BFGS algorithm is considered the best numerical effect of quasi-newton method, and it has global convergence and superlinear convergence rate.With the emergence of

4、 faster and more sophisticated computers, our computing ability has improved. But it also for our design algorithm has brought the new task.The development of parallel computer for solving large-scale optimization problem provides a new way. To solve the problem of small and medium-sized numerical a

5、lgorithm with good effect in parallel to the popularity of large scale problems.This paper proposes a parallel BFGS algorithm for solving unconstrained optimization problems. At the heart of the unconstrained optimization problems is choose search direction. The BFGS algorithm is the basic idea of t

6、he Newton method that used in the second step in the replaced one of Hesse matrix. To find out the search direction, along this direction, this set of direction the minimum point of the objective function. This algorithm has N steps termination. Combining write the MATLAB program, the algorithm is e

7、mployed to solve unconstrained optimization problems of the same.Key words: Unconstrained optimization; Quasi-Newton method; BFGS algorithm; Superlinear convergence; MATLAB目 录1、引言12、BFGS算法综述12.1 拟牛顿法及其性质12.2 BFGS算法33、数值实验63.1 代码实现63.2 算法测试73.3 结果分析84、总结84.1 总结概括84.2 个人感言95、参考文献：91、引言在最优化的问题中，线性最优化至少

8、可以使用单纯形法求解，但对于非线性优化问题，牛顿法提供了一种求解的办法。牛顿法的优点是具有二次收敛速度，但是当Hesse矩阵不正定时，不能保证所产生的方向是目标函数在处的下降方向。特别地，当奇异时，算法就无法继续进行下去，尽管修正的牛顿法可以克服这一缺点，但修正参数的选取很难把握，过大或过小都会影响到收敛速度，此外，牛顿法的每一迭代步都需要目标函数的二阶导数，即Hesse矩阵，对于大规模问题，其计算量是惊人的。由此引出了一种新的求解非线性优化问题的方法拟牛顿法。拟牛顿法(Quasi-Newton Methods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实

9、验室的物理学家W. C. Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R. Fletcher和M. J. D. Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文。其中BFGS就是拟牛顿法中的一种方法。2、BFGS算法的综述 2.1拟牛顿法及其性质 拟牛顿法的基本思想是在牛顿法的第二步中用Hesse矩阵的某个近似矩阵取代。通常，应具有以下三个特点：（1）在某种意义下有，使得相应的算法产生的方向近似于牛顿方

10、向，以确保算法具有较快的收敛速度；（2）对所有的，是对称正定的，从而使得算法所产生的方向是函数在处下降方向；（3）矩阵更新规则相对比较简单，即通常采用秩1或秩2矩阵进行校正。下面介绍满足这三个特点的矩阵的构造，设在开集上二次连续可微，那么在处二次近似模型为 （2.1）对上式求导得 （2.2）令，位移，梯度差，则有 （2.3）注意到对于二次函数，上式是精确成立的。现在，要求在拟牛顿法中构造Hesse矩阵的近似矩阵满足这种关系式，即 （2.4）式（2.4）通常称为拟牛顿方程或拟牛顿条件。令，则得到拟牛顿方程的另一种形式： （2.5）其中为Hesse矩阵逆的近似。搜索方向由或确定。根据（或）的第三个

11、特点，可令， （2.6）其中，为秩1或秩2矩阵，通常将拟牛顿方程（2.4）（或（2.5）和校正规则（2.6）所确立的方法称为拟牛顿法。 下面介绍一对称秩1校正公式。在（2.6）中取（秩1矩阵），其中.由拟牛顿方程（2.4）得 （2.7）即有 （2.8）式（2.8）表明向量平行，即存在常数使得.因此有 （2.9）于是，由（2.8）得 （2.10）由此，若，则可取，即 （2.11）故得对称秩1的校正公式如下： （2.12）类似地，利用拟牛顿方程（2.1.5），对称秩1的修正可得 （2.13）有了对称秩1校正公式后，利用它可以构造求解一个无约束优化问题的一个拟牛顿算法，步骤如下：算法2.1（对称秩1

12、算法）步0 给定初始点，终止误差，初始对称正定矩阵（通常取单位矩阵），令.步1 若，停止运算，输出作为近似极小点。步2 计算搜索方向.步3 用线性搜索技术求步长.步4 令，由对称秩1校正公式（2.13）确定.步5 令，转步1.2.2 BFGS算法BFGS校正是目前最流行，也是最有效的牛顿校正，它是由Broyden，Fletcher，Goldfarb和Shanno在1970年各自独立提出的拟牛顿法，故称BFGS算法，其基本思想是：在（2.6）中去修正矩阵为秩2矩阵 （2.14）其中为待定向量为待定实数，于是拟牛顿方程（2.4）可得 （2.15）或者等价地 （2.16）不难发现，满足（2.16）的

13、向量和不唯一，可取和分别平行于和，即令，其中为待定的参数，于是有 （2.17）将的表达式代入（2.16）得 （2.18）整理得 （2.19）故可令及，即 （2.20）从而得到BFGS秩2修正公式如下： （2.21） 显然，由（2.21）可知，若对称，则校正后的也对称，并且可以证明BFGS校正公式的如下性质： 引理2.1 设对称正定，由BFGS校正公式（2.21）确定，那么的对称正定的充要条件是. 证 必要性是显然的。因，故若正定，则显然有. 下面证明充分性. 设，且正定，由校正公式（2.21），对任意的有 （2.22）因对称正定，故存在对称正定矩阵，使得，从而利用Cauchy-Schwarz不

14、等式得 （2.23）不难发现，式（2.23）中等号成立的充要条件是存在实数，使得，即故若不等式（2.23）严格成立，则由（2.22）得 （2.24）否则，若（2.23）中等号成立，即存在，使得，则由（2.22）（2.23）得 （2.25）故对任意的，总有.证毕。引理2.2 若在BFGS算法中采用精确线搜索或Wolfe搜索准则，则有. 证 注意到对于精确线搜索有.故 对于Wolfe搜索准则，利用该准则的第二个不等式（即）得 证毕.已有证明表示，Armijo搜索准则一般不能保证。但Armijo准则因其简单且易于程序实现而深得人们的喜爱，因此，为了保证采用Armijo准则时矩阵序列的对称正定性，可采

15、用如下的校正方式： （2.26）不难发现，只要对称正定，上述校正公式可以保证矩阵序列的对称正定性.下面给出基于Armijo搜索准则的BFGS算法的详细步骤.算法2.2 （BFGS算法）步0 给定参数，初始点，终止误差，初始对称正定矩阵（通常取或单位矩阵）。令.步1 计算.若，停止运算，输出作为近似极小点。步2 解线性方程组的解， . （2.26）步3 设是满足下列不等式的最小非负整数： （2.27）令.步4 由校正公式（2.26）确定.步5 令，转步1.3、数值实验3.1代码实现基于Armijo搜索的BFGS算法MATLAB程序：function x,val,k=bfgs(fun,gfun,x

16、0)%功能：用BFGS算法求解无约束问题：min f(x)%输入：x0是初始点，fun，gfun分别是目标函数及其梯度；%输出：x，val分别是近似最优点和最优值，k是迭代次数.maxk=500; %给出最大迭代次数rho=0.55;sigma=0.4;epsilon=1e-5;k=0;n=length(x0);Bk=eye(n);%Bk=feval(Hess,x0);while(kmaxk) gk=feval(gfun,x0); %计算梯度 if (norm(gk)epsilon),break;end %检验终止准则 dk=-Bkgk; %解方程组，计算搜索方向 m=0;mk=0; whil

17、e(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); end k=k+1;x0=x;endval=feval(fun,x0);3.2算法测试利用上述程序求解无约束优化问题 .该问题有精确解.解：取终止准则为，目标函数和梯度如下：fun.M文件function f=fun(x) %目标函数f=100*(x(1)2-x(2)2+(x(1)-1)2;gfun.M文件function gf=gfun(x

18、) %目标函数梯度函数gf=2*x(1) - 400*x(1)*(- x(1)2 + x(2) - 2,- 200*x(1)2 + 200*x(2);利用程序，取不同的初始点，数值结果如下表。表3.1 BFGS算法的数值结果初始点()迭代次数（）目标函数值（）最优解（）2015243136323.3 结果分析由表3.1可见BFGS修正拟牛顿算法在不同的初始点，求解最优解的迭代次数有所差异，分析可见，在接近精确解的输出点处的迭代次数会相对较少。并且计算结果比较稳定，误差在忽略范围内。4、总结4.1 总结概括求解最优问题是一个艰难而具有挑战性的过程，最优化方法是近几十年形成的一门运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据的学科，它涵盖了无约束最优化问题、凸集与凸函数、等式约束最优化问题和不等式约束最优化问题等知识点。本次课程设计，通过老师的点拨以及不断的查阅资料，对该门课程中的无约束最优化问题进行了一定程度地了解和研究，无约束最优化方法的核心问题是选择搜索方向。过程中,我们运用拟牛顿法的一种算法BFGS算法进行处理。我们从理论的来源、推导过程出发进行深入，拟牛顿法(Quasi-Newt