Wolfe非精确搜索+BFGS

1、数学与计算科学学院实 验 报 告实验项目名称 Wolfe非精确搜索+BFGS 所属课程名称 最优化方法 实 验 类 型 算法编程 实 验 日 期 2015.11.13 班 级 信计1201班 学 号 姓 名 成 绩 一、实验概述：【实验目的】(1) 通过上机实验掌握最优化的实用算法的结构及性能，并用这些算法解决实际的最优化问题，掌握一些实用的编程技巧。(2) 了解Wolfe非精确搜索+BFGS的原理及时间效率等优点。【实验原理】1. 拟牛顿法（BFGS）BFGS(BroydenFletcherGoldfarbShanno)的算法流程如下：(1) 初始化：初始点x0以及近似逆Hessian矩阵B

2、10。通常，B0=I,既为单位矩阵。(2) 计算线搜索方向：pk=B1kf(xk)(3) 用”Backtracking line search“算法沿搜索方向找到下一个迭代点：xk+1=xk+kpk(4) 根据ArmijoGoldstein 准则，判断是否停止。(5) 计算xk+1=xk+kpk; 以及 yk=f(xk+1)f(xk)(6) 迭代近似逆Hessian矩阵：B1k+1=(IskyTkyTksk)B1k(IyksTkyTksk)+sksTkyTksk上式5中的推到方法比较复杂，有兴趣的可以搜一下相关文献。2.非精确线搜索wolfe算法【实验环境】Winows7.

3、0，matalb二、实验内容：【实验方案】 for i=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);fnum=1;gk=grdfcn(n,m,xk,nprob);gnum=1;delta=norm(gk,2);(2)迭代开始while k<1000 %迭代上限1000 if delta<=teminate % break;Else(3)确定下降方向 d

4、k=-linsolve(bk+muk*eye(n),gk);%求解下降方向 gk1=gk;fk1=fk;gkdk=gk'*dk; if gk'*dk>=-1.0e-14%当dk不是充分下降时采用负梯度为搜索方向 dk=-gk; end(4)确定步长%利用Wolfe-Powell搜索计算步长 alphak,fk,gk,wfnum,wgnum=wolfe2(n,m,xk,dk,fk1,gk1,nprob);%利用Wolfe-Powell搜索计算步长 (5)计算 fnum=fnum+wfnum; gnum=gnum+wgnum; xk1=xk;xk=xk1+alphak*dk;

5、 fk=objfcn(n,m,xk,nprob); gk=grdfcn(n,m,xk,nprob); if norm(gk,2)<=teminate k=k+1; break; end(6)由BFGS修正公式得 % Bk update sk=xk-xk1;bks2=sk'*bk*sk;yk=gk-gk1; yksk=yk'*sk; if yksk>0 bks1=bk*sk*sk'*bk; yks=yk*yk'/yksk;bk1=bk; bk=bk1-bk1*sk*sk'*bk1/(sk'*bk1*sk)+yk*yk'/(yk&

6、#39;*sk); end end k=k+1;End(7)无约束问题运算结束后记录所花费时间time=toc;%终止计时if time<=0.000001 t(i,s)=0.0001;else t(i,s)=time;%将每个无约束问题求解时间记录End(8)输出无约束问题的运行结果fprintf('nt%sttt%2dttt%5dtttt%5dttt%5dttt%4fn',filename,n,k,fnum,gnum,time);%结果输出End（9）拟牛顿法算法终止：当时，此处，迭代次数，若迭代次数达到1000，仍无法满足的条件，则退出算法。【实验过程】（实验步骤、

7、记录、数据、分析）1、实验步骤： 1、编辑Wolfe非精确搜索+BFGS的MATLAB程序，其中包括.m文件一个，脚本文件一个，详细程序见附录1.2、程序调试.3、运行程序分析结果.2：实验结果 运行程序，得到如下实验结果：*拟牛顿法results*ProblemDim.Iter.fnumgnumtime*rose 2 327 362 3301.701463froth 2 202 228 2040.201636badscp 2 1000 1081 10020.911348badscb 2 156 219 1590.170202beale 2 394 395 3950.338338jensam

8、2 81 109 840.098432helix 3 131 212 1360.160998bard 3 1000 1052 10032.357615gauss 3 771 772 7721.112494gulf 3 1000 1001 10011.130130box 3 262 263 2630.276804sing 4 1000 1028 10030.877423wood 4 245 365 2540.236166kowosb 4 1000 1001 10011.025711bd 4 1000+312757911754601.421517bigss 6 1000 1014 10026.63

9、4311osb211 1000 1050 10044.903811watson100 1000 1172 100932.726229rosex100 427 1651 4954.125570singx20 1000 1028 10032.215915pen110 1000 1001 10013.435982pen210 1000 1001 10012.011244vardim10 84 148 860.197684trig 10 62 63 630.178239bv 10 1000 1001 10011.587811IE 100 60 61 613.226137trid 10 31 180 4

10、60.185056band10 28 241 460.243491lin 10 87 88 880.295781lin1 10 4 56 60.093807lin0 10 4 52 60.043293【实验结论】（结果） 从实验结果可明显看出对于不同的问题，除个别问题外，拟牛顿法运行时间基本保持在很短的水平，且波动较小。故可以得出结论拟牛顿法在解决无约束问题上效率较高，稳定性好。【实验小结】（收获体会） 牛顿法具有运行时间短且比较稳定的特性，这次试验也很好的体现了这些特点。并且通过基于matlab的编程让我对于最优化方法获得更多的启发，在学习最优化方法上有了更好的体验。三、指导教师评语及成绩：

11、评 语评语等级优良中及格不及格1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强2.实验方案设计合理3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）4实验结论正确. 成 绩： 指导教师签名： 批阅日期：附录1：源 程 序%拟牛顿法 program using Wolfe-Powell search %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)

12、;nn=no(:,2);s=1;fprintf('nt*拟牛顿法results*n');fprintf('tProblemttDim.ttIter.tttfnumttgnumtttimen');fprintf('t*n');for i=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;de

13、lta=norm(gk,2);while k<1000 %迭代上限1000 if delta<=teminate break; else dk=-linsolve(bk+muk*eye(n),gk); gk1=gk;fk1=fk;gkdk=gk'*dk; if gk'*dk>=-1.0e-14 %当dk不是充分下降时采用负梯度为搜索方向 dk=-gk; end %利用Wolfe-Powell搜索计算步长 alphak,fk,gk,wfnum,wgnum=wolfe2(n,m,xk,dk,fk1,gk1,nprob); %利用Wolfe-Powell搜索计算步长

14、 fnum=fnum+wfnum; gnum=gnum+wgnum; xk1=xk;xk=xk1+alphak*dk; fk=objfcn(n,m,xk,nprob); gk=grdfcn(n,m,xk,nprob); if norm(gk,2)<=teminate k=k+1; break; end % Bk update sk=xk-xk1;bks2=sk'*bk*sk;yk=gk-gk1; yksk=yk'*sk; if yksk>0 bks1=bk*sk*sk'*bk; yks=yk*yk'/yksk;bk1=bk; bk=bk1-bk1*sk*sk'