Wolfe非精确搜索+BFGS.doc

数学与计算科学学院
实 验 报 告

实验项目名称 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) 用”Backtracking line search“算法沿搜索方向找到下一个迭代点：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
二、实验内容：
【实验方案】
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)确定下降方向
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)确定步长
%%%%%%%%%%%%%%%%%%%%%%%%%%%%利用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);
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'*sk);
end
end
kk+1;
End
(7)无约束问题运算结束后记录所花费时间
time=toc;%终止计时
if time<=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***************************
Problem Dim. Iter. fnum gnum time
*******************

rose 2 327 362 330 1.701463

froth 2 202 228 204 0.201636

badscp 2 1000 1081 1002 0.911348

badscb 2 156 219 159 0.170202

beale 2 394 395 395 0.338338

jensam 2 81 109 84 0.098432

helix 3 131 212 136 0.160998

bard 3 1000 1052 1003 2.357615

gauss 3 771 772 772 1.112494

gulf 3 1000 1001 1001 1.130130

box 3 262 263 263 0.276804

sing 4 1000 1028 1003 0.877423

wood 4 245 365 254 0.236166

kowosb 4 1000 1001 1001 1.025711

bd 4 1000 + 3127579 11754 601.421517

bigss 6 1000 1014 1002 6.634311

osb2 11 1000 1050 1004 4.903811

watson 100 1000 1172 1009 32.726229

rosex 100 427 1651 495 4.125570

singx 20 1000 1028 1003 2.215915

pen1 10 1000 1001 1001 3.435982

pen2 10 1000 1001 1001 2.011244

vardim 10 84 148 86 0.197684

trig 10 62 63 63 0.178239

bv 10 1000 1001 1001 1587811

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：源 程 序

%%%%拟牛顿法 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\t***************************拟牛顿法results***************************\n');
fprintf('\tProblem\t\tDim.\t\tIter.\t\t\tfnum\t\tgnum\t\ttime\n');
fprintf('\t********************************************************************\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不是充分下降时采用负梯度为搜索方向
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\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;