最优化实验报告

1、 最优化课程实验报 告课程题目 共轭梯度H-S算法与最速下降法求解无约束优化问题 小组成员 学生学号 指导老师 刘陶文 目录一、实验目的- 2 -二、实验步骤- 2 -三、实验过程- 2 -3.1算法选择- 2 -3.2参数设置- 3 -3.3终止准则- 3 -3.4线性搜索- 3 -四、实验结果与图像- 3 -五、结果分析- 10 -六、优缺点分析- 10 -6.1 优点- 10 -6.2 缺点- 11 -七、实验心得- 11 -八、附录- 11 -一、实验目的通过上机实验进一步掌握使用MATLAB软件，掌握最优化的实用算法的结构及性能，并通过MATLAB软件编写这些算法的程序解决实际的最优

2、化问题； 二、实验步骤本实验我组从无约束优化法 (最速下降法，Newton法，拟牛顿法，共轭梯度法)中选用使问题整体迭代效率较高的非线性共轭梯度H-S算法，同时选用迭代速度较慢的最速下降法进行比较。通过编程，上机实验对所老师提供的测试问题进行测试、运行，然后提供实验报告。并在实验报告中指出了选用的算法、参数设置、终止准则、线性搜索以及实验结果、实验心得，并在报告结尾附上主程序及选用的线性搜索代码。三、实验过程3.1算法选择我组经过对各种算法及运行结果的比较，最终采用非线性共轭梯度H-S算法和最速下降法求解老师所提供的测试问题，在老师所提供的noise.m的基础上对程序进行修改，主要修改便是对方

3、向计算的修改：H-S算法中方向dk的计算： 当k=0时， dk=-gk; 当k>=1时，dk=-gk+bbk*dk1; 其中 (gk'*(gk-gk1)/(dk1'*(gk-gk1);最速下降法的计算： dk=-gk;3.2参数设置（1） 迭代上限k:为了节约程序运行的时间，我们设置每个问题最多迭代1000次，即迭代上限k=1000.（2） 本题求解的问题编号设置如下：numer=1,2,3,4,5,6,7,8 9,10,11,12,13,14,15,16, 21, 22,22, 23,23, 24,24,25,25, 26, 26, 28, 28, 29, 29, 30

4、,30, 31, 32, 32, 33,34; （3） 各问题编号分别对应的维数：dim=2,2,2,2,2,2,3,3,3,3,3,3,4,4,4,4,100,20,100,50,200,10,20,10,100,200,600,200,1000,200,500,50,200,200,500,1000,10,10; （4） 由于老师所给程序中是用到BFGS修正算法，故用到了epsilon，而此处本程序中未用到，故没有epsilon参数。（5） 其他参数继续沿用老师程序所给：精度eminate=1.0e-5; factor=0.1;3.3终止准则（1） 本程序中设置teminate=1.0e-

5、5，delta取gk的二范：delta=norm(gk,2)，当norm(gk,2)<=teminate时程序终止；（2） 为了节约程序运行的时间，我们设置每个问题最多迭代1000次，即迭代次数k=1000时程序终止。3.4线性搜索通过对程序的多次调试比较，最终选定采用wolfe2作为本程序的搜索方式。四、实验结果与图像运行结果如下：*最速下降法 method results *ProblemDim.Iter. fnum gnum CPU*rose 2 100017535 15012.207049froth 2 100021972 15021.215546badscp 2 1000462

6、86 15012.381451badscb 2 100068911 15013.546717beale 2 100012392 15010.828143jensam 2 653 9761 9820.702124helix 3 100018139 15011.180877bard 3 100011325 15011.385253gauss 3 485 3890 7300.388772meyer 3 100017375 15011.724184gulf 3 1 14 40.099556box 3 413 3390 6220.386249sing 4 100015349 15010.893398wo

7、od 4 100018634 15011.112975kowosb 4 1000 8351 15010.888131bd 4 77422656 11622.816804watson 100 100033452 1501112.678843watson 100 100033452 1501116.999442rosex 100 100017535 15013.771796singx 20 100015349 15011.312565singx 20 100015349 15011.237520pen1 10 1000 1156 10160.626925pen1 10 1000 1156 1016

8、0.499451pen2 10 100012842 15011.490321pen2 10 100012842 15011.305813vardim 10 100018705 15011.492790vardim 10 100018705 15011.444957trig 10 43 198 620.045168trig 10 43 198 620.027591bv 10 100011137 15011.075922bv 10 100011137 15010.964815IE 100 75 495 1152.573623IE 100 75 495 1152.178786trid 10 159

9、2349 2410.305379trid 10 159 2349 2410.201084band 10 117 1696 1780.263157lin 10 53 298 820.076442lin 10 53 298 820.038946lin1 10 143 4610 2170.362424lin0 10 105 3182 1600.300578*共轭梯度法H-S method results *Problem Dim. Iter. fnum gnum CPU*rose 2 191 3019 2870.194278froth 2 257 4013 3880.302971badscp 2 2

10、27 10137 3250.510244badscb 2 695 34713 10421.939694beale 2 93 973 1350.054113jensam 2 143 1900 2160.129890helix 3 10 182 160.015878bard 3 653 6440 9790.827495gauss 3 201 978 2550.096183meyer 3 1000 1368 10090.219034gulf 3 1 14 40.001979box 3 1000 8443 12320.888340sing 4 83911363 12610.642189wood 4 1

11、00018816 15011.177239kowosb 4 1000 4821 12670.630418bd 4 248 6967 3730.809928watson 100 100028599 150199.887660watson 100 100028599 150198.279792rosex 100 395 6359 5931.155830singx 20 89112078 13391.018593singx 20 89112078 13391.014329pen1 10 1000 1187 10180.468902pen1 10 1000 1187 10180.521887pen2

12、10 1000 7230 12630.698659pen2 10 1000 7230 12630.753243vardim 10 431 7663 6490.526210vardim 10 431 7663 6490.594956trig 10 85 381 1190.058357trig 10 85 381 1190.057003bv 10 459 4473 6910.386874bv 10 459 4473 6910.435729IE 100 149 941 2264.135373IE 100 149 941 2264.055840trid 10 243 3321 3670.302492t

13、rid 10 243 3321 3670.240762band 10 64 927 970.083523lin 10 53 298 820.042389lin 10 53 298 820.045408lin1 10 38 831 540.295686lin0 10 24 657 350.065704五、结果分析通过对两种迭代方法迭代速度的比较我们可以得出以下结论：（1）最速下降法收敛速度较慢，很多问题无法的规定迭代次数内得到最优解即达到终止条件。（2）共轭梯度H-S法收敛速度较快，可以得出大多数测试问题的最优解。六、优缺点分析6.1 优点（1） 通过两种算法比较，直观表现两种算法的优缺点。（2

14、） 程序通用性高，可读性强。6.2 缺点（1） 共轭梯度H-S法 中的求解分母上存在减法，当分母很小时会产生较大误差。（2） 共轭梯度法的步长需采用精确搜索，采用Wolfe-Powell搜索难以保证方向共轭性。七、实验心得对最优化半学期的学习，我基本掌握了无约束优化梯度法，但这些仅仅是课本上学来的理论知识，这次的上机实践，使得我们对这些算法的思想更加了解，在选用算法时，总结出：解决问题的算法对问题至关重要，但是没有万能的算法，所以要根据实际问题来选用能够使问题整体效率最高的算法。在选择线性搜索的方法时，我们深刻体会到各类参数设置对程序效率的重要性，不同的问题要选用合适的参数来求解，这样使得问题

15、求解及程序运行的效率最高。上学期学习计算方法时也学习过matlab，但还是学的只是表面简单的东西，本次实验过程中遇到了很多棘手的问题，但是通过不断地翻阅课本，剖析程序，互相探讨以及老师的悉心指导，我们最后实现了对程序的修改和完善，对提供的问题作出了较好的解答。总的来说，对无约束最优化的求解，每种方法在解决不同的问题中效果不能都达到最优，所以我们在实际应用中，要根据实际情况选择合适的方法，争取最大可能的尽快的接近最优。本次上机实验不仅使我们基本了解了最优化的实用算法的结构及性能，而且也使得我们对matlab的一些编程技巧更加熟悉，收获很大。八、附录主程序：% 最速下降与共轭梯度H-S progr

16、am using Wolfe-Powell search %clc;epsilon=0.051;teminate=1.0e-5;factor=0.1;numer=1,2,3,4,5,6,7,8 9,10,11,12,13,14,15,16,20,20, 21, 22,22, 23,23, 24,24,25,25, 26, 26, 28, 28, 29, 29, 30,30, 31, 32, 32, 33,34; dim=2,2,2,2,2,2,3,3,3,3, 3, 3, 4,4, 4, 4,20,100,100,20,100,50,200,10,20,10,100,200,600,200,1

17、000,200,500,50,200,200,500,1000,10,10;no=size(numer);nn=no(:,2); for s=1:2 if s=1 epsilon=0.05; fprintf('nt*最速下降法 method results *n'); fprintf('tProblemtDim.tIter.tfnumtgnumtCPUn'); fprintf('t*n'); else epsilon=0; fprintf('t*共轭梯度法H-S method results *n'); fprintf('

18、tProblemtDim.tIter.tfnumtgnumtCPUn'); fprintf('t*n'); end for p=1:nnnprob=numer(p);rep=dim(p); n,m,xk,filename=initf(nprob,rep); 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 if delta<=teminate break; else

19、 if s=1 dk=-gk; else if k=0 dk=-gk; else bbk=(gk'*(gk-gk1)/(dk1'*(gk-gk1); % 的计算公式 dk=-gk+bbk.*dk1; %方向的计算不同 end if gk'*dk>=-1.0e-14 %当dk不是充分下降时采用负梯度为搜索方向 dk=-gk; end end end gk1=gk;fk1=fk; dk1=dk; alphak,fk,gk,wfnum,wgnum=wolfe2(n,m,xk,dk,fk1,gk1,nprob); if alphak=0 break; end fnum=f

20、num+wfnum; gnum=gnum+wgnum; xk1=xk; xk=xk1+alphak*dk;k=k+1; fk=objfcn(n,m,xk,nprob); fnum=fnum+1; gk=grdfcn(n,m,xk,nprob); gnum=gnum+1; if norm(gk,2)<=teminate %终止测试 break; end k=k+1;end time=toc;if time<=0.000001 t(p,s)=0.0001;else t(p,s)=time;endfprintf('nt%st%4dt%5dt%5dt%5dt%3fn',fi

21、lename,n,k,fnum,gnum,time);endend% clc;%作图开始ZT=0.01;Tau=10; Mp=size(t,1);%测试问题数目%Ms=size(t,2);%求解方法数目%r=zeros(Mp,Ms);for p=1:Mp mintp=min(t(p,1:Ms);%在所有求解器中对每一测试问题提取最小CPU时间% if mintp=0 mintp=0.001; end for s=1:Ms r(p,s)=t(p,s)/mintp; endendrho=zeros(Ms);hold on;% numbers=zeros(1,Ms); for s=1:Ms numb

22、ers=zeros(1,(Tau)/ZT); for tau=0.00001:ZT:Tau for p=1:Mp if r(p,s)<=tau k=ceil(tau-1)/ZT); numbers(k)=numbers(k)+1; end end end switch s case 1 % 最速下降法 tau=1.00001:ZT:Tau; k=ceil(tau-1)/ZT); plot(tau,numbers(k)/Mp,':b');% ax= plot(tau,numbers(k)/Mp) case 2 % 共轭梯度法 tau=1.00001:ZT:Tau; k=ce

23、il(tau-1)/ZT); plot(tau,numbers(k)/Mp,'-.m'); end% % plot(tau-0.01 tau,rho(s) rho(s),'-r');% set(gca,'xtick',1.:ZT:Tau);% grid on;%画网格线 set(gca,'xTick',1:1:10); set(gca,'yTick',0:0.1:1);% box; end% title('distrubtion function'); xlim = get(gca,'XLi

24、m');ylim = get(gca,'YLim');h = xlabel('tau');set(h,'Position',xlim(2)+(xlim(2)-xlim(1)*0.05,ylim(1);% set(k,'Position',xlim(1)-0.5,ylim(2)+0.04);text(xlim(1)-0.4,ylim(2)+0.02,'p','rotation',0);% ylabel('P(r_p,sleqtau:1leq sleq n_s)');%设置y坐标名称legend('最速下降法','共轭梯度法H-S',4)hold off;%作图结束wolfe2搜索：% Wolfe Line Searchfunction alphak1,fk2,gk2,wfnum,wgnum=wolfe2(n,m,xk,dk,fk,