Wolfe非精确搜索+BFGS.docx
《Wolfe非精确搜索+BFGS.docx》由会员分享，可在线阅读，更多相关《Wolfe非精确搜索+BFGS.docx（10页珍藏版）》请在冰点文库上搜索。
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）计算线搜索方向：
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算法
【实验环境】
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）;
fnum=1;
gk=grdfcn（n,m,xk,nprob）;
gnum=1;
delta=norm（gk,2）;
（2）迭代开始
whilek<1000%%%%%%%%%迭代上限1000
ifdelta<=teminate%%
break;
Else
（3）确定下降方向
dk=-linsolve（bk+muk*eye（n）,gk）;%%%%求解下降方向
gk1=gk;fk1=fk;gkdk=gk'*dk;
ifgk'*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;
fk=objfcn（n,m,xk,nprob）;
gk=grdfcn（n,m,xk,nprob）;
ifnorm（gk,2）<=teminate
k=k+1;
break;
end
（6）由BFGS修正公式得
%%%%%%%%%%%%%%%%%Bkupdate
sk=xk-xk1;bks2=sk'*bk*sk;yk=gk-gk1;
yksk=yk'*sk;
ifyksk>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
（7）无约束问题运算结束后记录所花费时间
time=toc;%终止计时
iftime<=0.000001
t（i,s）=0.0001;
else
t（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）拟牛顿法算法终止：
当
时，此处
，迭代次数
，若迭代次数达到1000，仍无法满足
的条件，则退出算法。
【实验过程】（实验步骤、记录、数据、分析）
1、实验步骤：
1、编辑Wolfe非精确搜索+BFGS的MATLAB程序，其中包括.m文件一个，脚本文件一个，详细程序见附录1.
2、程序调试.
3、运行程序分析结果.
2：
实验结果
运行程序，得到如下实验结果：
***************************拟牛顿法results***************************
ProblemDim.Iter.fnumgnumtime
********************************************************************
rose23273623301.701463
froth22022282040.201636
badscp21000108110020.911348
badscb21562191590.170202
beale23943953950.338338
jensam281109840.098432
helix31312121360.160998
bard31000105210032.357615
gauss37717727721.112494
gulf31000100110011.130130
box32622632630.276804
sing41000102810030.877423
wood42453652540.236166
kowosb41000100110011.025711
bd41000+312757911754601.421517
bigss61000101410026.634311
osb2111000105010044.903811
watson10010001172100932.726229
rosex10042716514954.125570
singx201000102810032.215915
pen1101000100110013.435982
pen2101000100110012.011244
vardim1084148860.197684
trig106263630.178239
bv101000100110011.587811
IE1006061613.226137
trid1031180460.185056
band1028241460.243491
lin108788880.295781
lin11045660.093807
lin01045260.043293
【实验结论】（结果）
从实验结果可明显看出对于不同的问题，除个别问题外，拟牛顿法运行时间基本保持在很短的水平，且波动较小。
故可以得出结论拟牛顿法在解决无约束问题上效率较高，稳定性好。
【实验小结】（收获体会）
牛顿法具有运行时间短且比较稳定的特性，这次试验也很好的体现了这些特点。
并且通过基于matlab的编程让我对于最优化方法获得更多的启发，在学习最优化方法上有了更好的体验。
三、指导教师评语及成绩：
评语
评语等级
优
良
中
及格
不及格
1.实验报告按时完成,字迹清楚,文字叙述流畅,逻辑性强
2.实验方案设计合理
3.实验过程（实验步骤详细,记录完整,数据合理,分析透彻）
4实验结论正确.
成绩：
指导教师签名：
批阅日期：
附录1：
源程序
%%%%拟牛顿法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:
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）;
whilek<1000%%%%%%%%%迭代上限1000
ifdelta<=teminate
break;
else
dk=-linsolve（bk+muk*eye（n）,gk）;
gk1=gk;fk1=fk;gkdk=gk'*dk;
ifgk'*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搜索计算步长
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）<=teminate
k=k+1;
break;
end
%%%%%%%%%%%%%%%%%Bkupdate
sk=xk-xk1;bks2=sk'*bk*sk;yk=gk-gk1;
yksk=yk'*sk;
ifyksk>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;%终止计时
iftime<=0.000001
t（i,s）=0.0001;
else
t（i,s）=time;
end
fprintf（'\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）;
end
s=2;
升级会员 