Wolfe非精确搜索+BFGS

数学与计算科学学院实验报告实验项目名称Wolfe非精确搜索+BFGS所属课程名称最优化方法实验类型算法编程实验日期2015.11.13班级信计1201班学号姓名成绩1一、实验概述：【实验目的】(1)通过上机实验掌握最优化的实用算法的结构及性能，并用这些算法解决实际的最优化问题，掌握一些实用的编程技巧。(2)了解Wolfe非精确搜索+BFGS的原理及时间效率等优点。【实验原理】1.拟牛顿法（BFGS）BFGS(Broyden–Fletcher–Goldfarb–Shanno)的算法流程如下：(1)初始化：初始点x0以及近似逆Hessian矩阵B−10。通常，B0=I,既为单位矩阵。(2)计算线搜索方向：pk=−B−1k∇f(xk)(3)用”Backtrackinglinesearch“算法沿搜索方向找到下一个迭代点：xk+1=xk+αkpk(4)根据Armijo–Goldstein准则，判断是否停止。(5)计算xk+1=xk+αkpk;以及yk=∇f(xk+1)−∇f(xk)(6)迭代近似逆Hessian矩阵：B−1k+1=(I−skyTkyTksk)B−1k(I−yksTkyTksk)+sksTkyTksk上式5中的推到方法比较复杂，有兴趣的可以搜一下相关文献。2.非精确线搜索wolfe算法2.2.1:.1.3,1,0),(:3.3.1.3:2.0:.1.3,2,1,0|).1,0(,0:1.;11.31:0)()(1)()1()(1)()()()0(1转步令的最大值）中第一个不等式成立中使得（是集合令步转步长令；否则，则终止计算，并得步长）中的第二个不等式，满足（若步令最大值的第一个不等式成立的）中中使得（是集合令，给定常数步否则转下一步），则取满足（若步iijiiikikjikikikikikkikikkk【实验环境】Winows7.0，matalb二、实验内容：【实验方案】fori=1:nn%%%1-nn函数依次进入运算(1)初值准备nprob=numer(i);[n,m,xk,filename]=initf(nprob);%%%%%%%%读初始数据xk=factor*xk;bk=eye(n);k=0;tic;%计时开始fk=objfcn(n,m,xk,nprob);3fnum=1;gk=grdfcn(n,m,xk,nprob);gnum=1;delta=norm(gk,2);(2)迭代开始whilek1000%%%%%%%%%迭代上限1000ifdelta=teminate%%atetexfkmin)(break;Else(3)确定下降方向)(kddk=-linsolve(bk+muk*eye(n),gk);%%%%求解下降方向gk1=gk;fk1=fk;gkdk=gk'*dk;ifgk'*dk=-1.0e-14%当dk不是充分下降时采用负梯度为搜索方向dk=-gk;end(4)确定步长k%%%%%%%%%%%%%%%%%%%%%%%%%%%%利用Wolfe-Powell搜索计算步长[alphak,fk,gk,wfnum,wgnum]=wolfe2(n,m,xk,dk,fk1,gk1,nprob);%%%%%%%%%%%%%%%%%%%%%%%%%%%%%利用Wolfe-Powell搜索计算步长(5)计算1kxfnum=fnum+wfnum;gnum=gnum+wgnum;xk1=xk;xk=xk1+alphak*dk;fk=objfcn(n,m,xk,nprob);gk=grdfcn(n,m,xk,nprob);ifnorm(gk,2)=teminatek=k+1;break;end(6)由BFGS修正公式得1kB%%%%%%%%%%%%%%%%%Bkupdatesk=xk-xk1;bks2=sk'*bk*sk;yk=gk-gk1;yksk=yk'*sk;ifyksk0bks1=bk*sk*sk'*bk;yks=yk*yk'/yksk;bk1=bk;bk=bk1-bk1*sk*sk'*bk1/(sk'*bk1*sk)+yk*yk'/(yk'*sk);4endendk=k+1;End(7)无约束问题运算结束后记录所花费时间time=toc;%终止计时iftime=0.000001t(i,s)=0.0001;elset(i,s)=time;%%%将每个无约束问题求解时间记录End(8)输出无约束问题的运行结果fprintf('\n\t%s\t\t\t%2d\t\t\t%5d\t\t\t\t%5d\t\t\t%5d\t\t\t%4f\n',filename,n,k,fnum,gnum,time);%%%%结果输出End（9）拟牛顿法算法终止：当)()(kxf时，此处60.1mineatete，迭代次数1000k，若迭代次数达到1000，仍无法满足)()(kxf的条件，则退出算法。【实验过程】（实验步骤、记录、数据、分析）1、实验步骤：1、编辑Wolfe非精确搜索+BFGS的MATLAB程序，其中包括.m文件一个，脚本文件一个，详细程序见附录1.2、程序调试.3、运行程序分析结果.2：实验结果运行程序，得到如下实验结果：***************************拟牛顿法results***************************ProblemDim.Iter.fnumgnumtime********************************************************************rose23273623301.701463froth22022282040.2016365badscp21000108110020.911348badscb21562191590.170202beale23943953950.338338jensam281109840.098432helix31312121360.160998bard31000105210032.357615gauss37717727721.112494gulf31000100110011.130130box32622632630.276804sing41000102810030.877423wood42453652540.236166kowosb41000100110011.025711bd41000+312757911754601.421517bigss61000101410026.634311osb2111000105010044.903811watson10010001172100932.726229rosex10042716514954.125570singx201000102810032.215915pen1101000100110013.435982pen2101000100110012.011244vardim1084148860.197684trig106263630.1782396bv101000100110011.587811IE1006061613.226137trid1031180460.185056band1028241460.243491lin108788880.295781lin11045660.093807lin01045260.043293【实验结论】（结果）从实验结果可明显看出对于不同的问题，除个别问题外，拟牛顿法运行时间基本保持在很短的水平，且波动较小。故可以得出结论拟牛顿法在解决无约束问题上效率较高，稳定性好。【实验小结】（收获体会）牛顿法具有运行时间短且比较稳定的特性，这次试验也很好的体现了这些特点。并且通过基于matlab的编程让我对于最优化方法获得更多的启发，在学习最优化方法上有了更好的体验。三、指导教师评语及成绩：评语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确.成绩：指导教师签名：批阅日期：附录1：源程序7%%%%拟牛顿法programusingWolfe-Powellsearch%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%clc;muk=10;teminate=1.0e-6;factor=0.1;numer=[1,2,3,4,5,6,7,8,9,11,12,13,14,15,16,18,19,20,21,22,23,24,25,26,28,29,30,31,32,33,34];no=size(numer);nn=no(:,2);s=1;fprintf('\n\t***************************拟牛顿法results***************************\n');fprintf('\tProblem\t\tDim.\t\tIter.\t\t\tfnum\t\tgnum\t\ttime\n');fprintf('\t********************************************************************\n');fori=1:nnnprob=numer(i);[n,m,xk,filename]=initf(nprob);%%%%%%%%读初始数据xk=factor*xk;bk=eye(n);k=0;tic;%计时开始fk=objfcn(n,m,xk,nprob);fnum=1;gk=grdfcn(n,m,xk,nprob);gnum=1;delta=norm(gk,2);whilek1000%%%%%%%%%迭代上限1000ifdelta=teminatebreak;elsedk=-linsolve(bk+muk*eye(n),gk);gk1=gk;fk1=fk;gkdk=gk'*dk;ifgk'*dk=-1.0e-14%当dk不是充分下降时采用负梯度为搜索方向8dk=-gk;end%%%%%%%%%%%%%%%%%%%%%%利用Wolfe-Powell搜索计算步长[alphak,fk,gk,wfnum,wgnum]=wolfe2(n,m,xk,dk,fk1,gk1,nprob);%%%%%%%%%%%%%%%%%%%%%%利用Wolfe-Powell搜索计算步长fnum=fnum+wfnum;gnum=gnum+wgnum;xk1=xk;xk=xk1+alphak*dk;fk=objfcn(n,m,xk,nprob);gk=grdfcn(n,m,xk,nprob);ifnorm(gk,2)=teminatek=k+1;break;end%%%%%%%%%%%%%%%%%Bkupdatesk=xk-xk1;bks2=sk'*bk*sk;yk=gk-gk1;yksk=yk'*sk;ifyksk0bks1=bk*sk*sk'*bk;yks=yk*yk'/yksk;bk1=bk;bk=bk1-bk1*sk*sk'*bk1/(sk'*bk1*sk)+yk*yk'/(yk'*sk);endendk=k+1;endtime=toc;%终止计时iftime=0.000001t(i,s)=0.0001;elset(i,s)=time;endfprintf('\n\t%s\t\t%2d\t\t%5d\t\t\t%5d\t\t%5d\t\t%4f\n',filename,n,k,fnum,gnum,time);ends=2;