还剩18页未读，继续阅读
本资源只提供10页预览，全部文档请下载后查看！喜欢就下载吧，查找使用更方便
文本内容:
目录引言
12、BFGS算法综述11拟牛顿法及其性质
12.2BFGS算法
33、数值实验61代码实现62算法测试
73.3结果分析
84、总结81总结概括
85、参考文献9从而得到BFGS秩2修正公式如下:
2.21显然，由
2.21可知，若屏时称，则校正后的也对称，并且可以证明BFGS校正公式的如下性质引理
2.1设屏对称正定，由BFGS校正公式
2.21确定那么的对称正定的充要条件是炉浮＞0证必要性是显然的因，故若正定，则显然有炉浮＞0下面证明充分性.设/r^＞0且正定，由校正公式
2.21对任意的0“€口・（dTB^）2（dryyP）『（
772.22因耳对称正定，故存在对称正定矩阵瞰使得从而利用Cauchy-Schwarz不等式得■［（♦”（欧力『4wd忖寸=『（咪4⑶义堵力=（/4/）［（3］（
2.23）不难发现，式（
2.23）中等号成立的充要条件是存在实数rt*0使得碎％=—即d=r/故若不等式（
2.23）严格成立，则由（
2.22）得公…瞥鬻第1+的
2.24否则，若（
2.23）中等号成立，即存在d=TkSk，则由
2.
222.23得
2.25故对任意的，总有dTBk^d
0.证毕引理
2.2若在BFGS算法中采用精确线搜索或Wolfe搜索准则，则有（W证注意到对于精确线搜索有gw=o.故0对于Wolfe搜索准则，利用该准则的第二个不等式（即）得f（1-）（屋）rd0证毕.已有证明表示，Armijo搜索准则一般不能保证（炉浮0o但Armijo准则因其简单且易于程序实现而深得人们的喜爱，因此，为了保证采用Armijo准则时矩阵序列{BJ的对称正定性，可采用如下的校正方式j4r
02.26不难发现，只要风对称正定，上述校正公式可以保证矩阵序列{修的对称正定性.下面给出基于Armijo搜索准则的BFGS算法的详细步骤.算法
2.2（BFGS算法）步给定参数€
（01）（7€（
00.5）初始点终止误差01初始对称正定矩阵风（通常取馆）或单位矩阵）o令*=0步1计算.若停止运算，输出作为近似极小点步2解线性方程组的解.
2.26步3设叫是满足下列不等式的最小非负整数m*+犷/4/，+卡依A/小
2.27令步4由校正公式
2.26确定步5令*=*+1，转步
1.
3、数值实验代码实现基于Armijo搜索的BFGS算法MATLAB程序:function[xvalk]=bfgsfungfunxO%功能:用BFGS算法求解无约束问题minfx外输入xO是初始点，fungfun分别是目标函数及其梯度;%输出xval分别是近似最优点和最优值，k是迭代次数.maxk=500;%给出最大迭代次数rho=
0.55;sigma=
0.4;epsilon=le-5;k=O;n=lengthxO;Bk=eyen;%Bk=fevalHessxO;whilekmaxkgk=fevalgfunxO;%计算梯度ifnormgkepsilonbreak;end%检验终止准则dk=-Bk\gk;先解方程组，计算搜索方向m=0;mk=0;whilem20%用Armijo搜索求步长newf=fevalfunxO+rhom*dk;oldf=fevalfunxO;ifnewfo1df+sigma*rho*m*gk**dkmk=m;break;endm=m+l;end%BFGS校正x=xO+rh/mk*dk;sk=x-xO;yk=fevalgfunx-gk;ifyk*sk0Bk=Bk-Bk*sk*sk*Bk/sk*Bk*sk+yk*yk/yk，*sk;endk=k+1;xO=x;endval=fevalfunxO;
3.2算法测试利用上述程序求解无约束优化问题min〃x=iooM-马y+a-M“CwJw口该问题有精确解x=llr/x=O解取终止准则为%力忖0“目标函数和梯度如下fun.M文件functionf=funx%目标函数f=100*xl-2-x22+xl-1^2;gfun.M文件functiongf=gfunx用目标函数梯度函数gf=[2*xl-400*xl*-xl/2+x2-2-200*x⑴2+200*x2];利用程序，取不同的初始点，数值结果如下表表
3.1BFGS算法的数值结果3结果分析由表
3.1可见BFGS修正拟牛顿算法在不同的初始点，求解最优解的迭代次数有所差异，分析可见，在接近精确解的输出点处的迭代次数会相对较少并且计算结果比较稳定，误差在忽略范围内
4、总结1总结概括求解最优问题是一个艰难而具有挑战性的过程，最优化方法是近几十年形成的一门运用数学方法研究各种系统的优化途径及方案，为决策者提供科学决策的依据的学科，它涵盖了无约束最优化问题、凸集与凸函数、等式约束最优化问题和不等式约束最优化问题等知识点本次课程设计，通过老师的点拨以及不断的查阅资料，对该门课程中的无约束最优化问题进行了一定程度地了解和研究，无约束最优化方法的核心问题是选择搜索方向过程中，我们运用拟牛顿法的一种算法一一BFGS算法进行处理我们从理论的来源、推导过程出发进行深入，拟牛顿法Quasi-NewtonMethods是于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来BFGS算法是由BroydcnFletcherGoldfarb和Shanno提出的，故以其姓氏首字母命名后来，人们把这种方法用于求解无约束最优化问题BFGS算法的基本思想是用Hesse矩阵g4=v7/的某个近似矩阵取代从而避免当G*奇异或非正定时牛顿法的缺陷之后，还实现了MATLAB程序实现的效果对问题进行数值求解时，采用了大量的数据实例进行验证、对比，并且选择了较有代表性的例子编入我的课程设计论文当中
1、引言在最优化的问题中，线性最优化至少可以使用单纯形法求解，但对于非线性优化问题，牛顿法提供了一种求解的办法牛顿法的优点是具有二次收敛速度，但是当Hesse矩阵g4=v7（）不正定时，，不能保证所产生的方向是目标函数在X*处的下降方向特别地，当奇异时，算法就无法继续进行下去，尽管修正的牛顿法可以克服这一缺点，但修正参数的选取很难把握，过大或过小都会影响到收敛速度，此外，牛顿法的每一迭代步都需要目标函数的二阶导数，即Hesse矩阵，对于大规模问题，其计算量是惊人的由此引出了一种新的求解非线性优化问题的方法一一拟牛顿法拟牛顿法（Quasi-NewtonMethods）是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家MC.Davidon所提出来Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一不久R.Fletcher和M.J.D.Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进在之后的20年里，拟牛顿方法得到了蓬勃发展，出现了大量的变形公式以及数以百计的相关论文其中BFGS就是拟牛顿法中的一种方法
2、BFGS算法的综述
2.1拟牛顿法及其性质拟牛顿法的基本思想是在牛顿法的第二步中用Hesse矩阵g4=v7（）的某个近似矩阵取代通常应具有以下三个特点:1在某种意义下有4吗使得相应的算法产生的方向近似于牛顿方向，以确保算法具有较快的收敛速度;2对所有的屏是对称正定的，从而使得算法所产生的方向是函数/在处下降方向；3矩阵及更新规则相对比较简单，即通常采用秩1或秩2矩阵进行校正下面介绍满足这三个特点的矩阵屏的构造，设/口〜口在开集Den*上二次连续可微，那么/在处二次近似模型为对上式求导得双W-令x=X*位移梯度差八gZ-g，则有注意到对于二次函数/上式是精确成立的现在，要求在拟牛顿法中构造Hesse矩阵的近似矩阵屏满足这种关系式，即式
2.4通常称为拟牛顿方程或拟牛顿条件令儿.产吃I，则得到拟牛顿方程的另一种形式其中%为Hesse矩阵逆的近似搜索方向由Bd=-/确定根据%（或）的第三个特点，可令其中a为秩1或秩2矩阵，通常将拟牛顿方程（
2.4）（或（
2.5））和校正规则（
2.6）所确立的方法称为拟牛顿法下面介绍一对称秩1校正公式在（
2.6）中取（秩1矩阵），其中a€Otw*eO*.由拟牛顿方程（
2.4）得.♦ar1—=一即有式（
2.8）表明向量平行即存在常数使得.因此有于是，由（
2.8）得-S）=（y-BJ）（
2.10）由此，若则可取-y力=1即a炉-1E（/-―+八）『叩.（/小）――声新7（
2.11）故得对称秩1的校正公式如下:
2.12类似地，利用拟牛顿方程（
2.
1.5）对称秩1的修正可得有了对称秩1校正公式后，利用它可以构造求解一个无约束优化问题的一个拟牛顿算法，步骤如下算法
2.1（对称秩1算法）步0给定初始点终止误差01初始对称正定矩阵（通常取单位矩阵）令A=0步1若停止运算，输出作为近似极小点步2计算搜索方向步3用线性搜索技术求步长由对称秩1校正公式（
2.13）确定%*=*4-1，转步
1.
2.2BFGS算法BFGS校正是目前最流行，也是最有效的牛顿校正，它是由BroydenFletcherGoldfarb和Shanno在1970年各自独立提出的拟牛顿法，故称BFGS算法，其基本思想是在
2.6中去修正矩阵为秩2矩阵号川
2.14其中为待定向量aDw「为待定实数，于是拟牛顿方程
2.4可得[4+如/V+川///=/
2.15或者等价地一♦X=/-V
2.16不难发现，满足
2.16的向量uk和不唯一，可取和分别平行于和即令/=出，/=W其中为待定的参数，于是有用二”8/，「
4.微/力「
2.17将的表达式代入
2.16得――+4尔y/]8力=炉・
2.18整理得{研，『人力+1}4+喇产力-”=
02.19故可令a/[r^]+l=0及画[/『力-1=0即ay2=—TY——r，0仍=丁丁丁金/y初始点迭代次数k目标函数值/3最优解■X00r
202.2005xl0n
1.
00001.0000/
0.505r
151.9460x10*
1.
00001.0000/22r
242.1171x10书
1.
00001.0000/
311.3594xIO
121.
00001.0000/
1.1Of
361.3757xIO
151.
00001.0000/-
1.2Dr
326.7539x
10161.
00001.0000/。
个人认证
优秀文档
获得点赞 0
