Wolfe非精确搜索+BFGS

数学与计算科学学院

实 验 报 告

实验项目名称 Wolfe非精确搜索+BFGS 所属课程名称 最优化方法 实 验 类 型 算法编程 实 验 日 期 2015.11.13

班 级 信计1201班 学 号 姓 名

成 绩

一、实验概述： 【实验目的】 (1) 通过上机实验掌握最优化的实用算法的结构及性能，并用这些算法解决实际的最优化问题，掌握一些实用的编程技巧。 (2) 了解Wolfe非精确搜索+BFGS的原理及时间效率等优点。 【实验原理】 1. 拟牛顿法（BFGS） BFGS(Broyden–Fletcher–Goldfarb–Shanno)的算法流程如下： (1) 初始化：初始点x0以及近似逆Hessian矩阵B−10。通常，B0=I,既为单位矩阵。 (2) (3) 计算线搜索方向：pk=−B−1k∇f(xk) 用”Backtracking line search“算法沿搜索方向找到下一个迭代点：xk+1=xk+αkpk (4) (5) (6) 根据Armijo–Goldstein 准则，判断是否停止。 计算xk+1=xk+αkpk; 以及 yk=∇f(xk+1)−∇f(xk) 迭代近似逆Hessian矩阵： B−1k+1=(I−skyTkyTksk)B−1k(I−yksTkyTksk)+sksTkyTksk 上式5中的推到方法比较复杂，有兴趣的可以搜一下相关文献。 2.非精确线搜索wolfe算法 1

步0:若k1满足（3.1），则取k1;否则转下一步.步1:给定常数0，,1(0,1).令k(0)是集合i|i0,1,2,中使得（3.1）中的第一个不等式成立的最大值.令i:0.步2:若k(i)满足（3.1）中的第二个不等式，则终止计算，并得步长kk(i)；否则， 令k(i)1k(i).转步长3.步3:令k(i1)是集合k(i)1j(k(i)k(i)),j0,1,中使得（3.1）中第一个不等式成立的最大值.令i:i1.转步2. 【实验环境】 Winows7.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);

2

fnum=1; gk=grdfcn(n,m,xk,nprob); gnum=1; delta=norm(gk,2); (2)迭始 while k<1000 %%%%%%%%%迭代上限1000 if delta<=teminate %%f(x)teminate break; Else k(3)确定下降方向d(k) dk=-linsolve(bk+muk*eye(n),gk);%%%%求解下降方向 gk1=gk;fk1=fk;gkdk=gk'*dk; if gk'*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)计算xk1 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 (6)由BFGS修正公式得Bk1 %%%%%%%%%%%%%%%%% 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'*sk); 3

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('\\n\%s\\\%2d\\\%5d\\\\%5d\\\%5d\\\%4f\\n',filename,n,k,fnum,gnum,time);%%%%结果输出 End （9）拟牛顿法算法终止： 当f(x(k))时，此处teminate1.0e6，迭代次数k1000，若迭代次数达到1000，仍无法满足f(x(k))的条件，则退出算法。 【实验过程】（实验步骤、记录、数据、分析） 1、实验步骤： 1、编辑Wolfe非精确搜索+BFGS的MATLAB程序，其中包括.m文件一个，脚本文件一个，详细程序见附录1. 2、程序调试. 3、运行程序分析结果. 2：实验结果 运行程序，得到如下实验结果： ***************************拟牛顿法results*************************** Problem Dim. Iter. fnum gnum time ******************************************************************** rose 2 327 362 330 1.701463 froth 2 202 228 204 0.201636

4

badscp badscb beale 2 2 2 2 3 3 3 1000 156 394 81 131 1000 771 1000 262 1000 245 1000 1000 1000 1000 1000 427 1000 1000 1000 84 62 1081 219 395 109 212 1052 772 1001 263 1028 365 1001 1002 159 395 84 136 1003 772 1001 263 1003 2 1001 117 1002 1004 1009 495 1003 1001 1001 86 63 0.911348 0.170202 0.338338 0.098432 0.160998 2.357615 1.112494 1.130130 0.276804 0.877423 0.236166 1.025711 601.421517 6.634311 4.903811 32.726229 4.125570 2.215915 3.435982 2.011244 0.197684 0.178239 jensam helix bard gauss gulf box sing 3 3 4 4 4 4 6 11 100 100 20 10 10 10 wood kowosb bd bigss osb2 + 3127579 1014 1050 1172 1651 1028 1001 1001 148 63 5

watson rosex singx pen1 pen2 vardim trig 10 bv 10 1000 1001 1001 1.587811 IE 100 60 61 61 3.226137 trid 10 31 180 46 0.185056 band 10 28 241 46 0.243491 lin 10 87 88 88 0.295781 lin1 10 4 56 6 0.093807 lin0 10 4 52 6 0.043293 【实验结论】（结果） 从实验结果可明显看出对于不同的问题，除个别问题外，拟牛顿法运行时间基本保持在很短的水平，且波动较小。故可以得出结论拟牛顿法在解决无约束问题上效率较高，稳定性好。 【实验小结】（收获体会） 牛顿法具有运行时间短且比较稳定的特性，这次试验也很好的体现了这些特点。并且通过基于matlab的编程让我对于最优化方法获得更多的启发，在学习最优化方法上有了更好的体验。 三、指导教师评语及成绩： 评语等级 评 语 1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强 优 良 中 2.实验方案设计合理 3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻） 4实验结论正确. 成 绩： 指导教师签名： 批阅日期： 及格 不及格 附录1：源 程 序

6

%%%%拟牛顿法 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); nn=no(:,2); s=1; fprintf('\\n\***************************拟牛顿法results***************************\\n'); fprintf('\Problem\\Dim.\\Iter.\\\fnum\\gnum\\time\\n'); fprintf('\********************************************************************\\n'); for i=1:nn 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); 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不是充分下降时采用负梯度为搜索方向

7

dk=-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); 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'*bk1/(sk'*bk1*sk)+yk*yk'/(yk'*sk); end end k=k+1; end time=toc;%终止计时 if time<=0.000001 t(i,s)=0.0001; else t(i,s)=time; end fprintf('\\n\%s\\%2d\\%5d\\\%5d\\%5d\\%4f\\n',filename,n,k,fnum,gnum,time); end s=2;

8