最优化实验报告

《最优化实验报告》由会员分享，可在线阅读，更多相关《最优化实验报告（15页珍藏版）》请在装配图网上搜索。

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

2、用使问题整体迭代效率较高的非线性共轭梯度H-S算法，同时选用迭代速度较慢的最速下降法进行比较。通过编程，上机实验对所老师提供的测试问题进行测试、运行，然后提供实验报告。并在实验报告中指出了选用的算法、参数设置、终止准则、线性搜索以及实验结果、实验心得，并在报告结尾附上主程序及选用的线性搜索代码。三、实验过程3.1算法选择我组经过对各种算法及运行结果的比较，最终采用非线性共轭梯度H-S算法和最速下降法求解老师所提供的测试问题，在老师所提供的noise.m的基础上对程序进行修改，主要修改便是对方向计算的修改：H-S算法中方向dk的计算：当k=0时，dk=-gk;当k=1时，dk=-gk+bbk*d

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

4、00,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，delta取gk的二范：delta=norm（gk,2），当norm（gk,2）v=teminate时程序终止；（2）为了节约程序运行的时间，我们设置每个问题最多迭代1000次，即迭代次数k

5、=1000时程序终止。3.4线性搜索通过对程序的多次调试比较，最终选定采用wolfe2作为本程序的搜索方式。四、实验结果与图像运行结果如下：*最速下降法methodresults*ProblemDim.Iter.fnumgnumCPU*rose210001753515012.207049froth210002197215021.215546badscp210004628615012.381451badscb210006891115013.546717beale210001239215010.828143jensam265397619820.702124helix310001813915011.

6、180877bard310001132515011.385253gauss348538907300.388772meyer310001737515011.724184gulf311440.099556box341333906220.386249sing410001534915010.893398wood410001863415011.112975kowosb41000835115010.888131bd47742265611622.816804watson1001000334521501112.678843watson1001000334521501116.999442rosex1001000

7、1753515013.771796singx2010001534915011.312565singx2010001534915011.237520penl101000115610160.626925penl101000115610160.499451pen21010001284215011.490321pen21010001284215011.305813vardim1010001870515011.492790vardim1010001870515011.444957trig1043198620.045168trig1043198620.027591bv1010001113715011.07

8、5922bv1010001113715010.964815IE100754951152.573623IE100754951152.178786trid1015923492410.305379trid1015923492410.201084band1011716961780.263157lin1053298820.076442lin1053298820.038946Iin11014346102170.362424Iin01010531821600.300578*共轭梯度法H-Smethodresults*ProblemDim.Iter.fnumgnumCPU*rose219130192870.1

9、94278froth225740133880.302971badscp2227101373250.510244badscb26953471310421.939694beale2939731350.054113jensam214319002160.129890helix310182160.015878bard365364409790.827495gauss32019782550.096183meyer31000136810090.219034gulf311440.001979box31000844312320.888340sing48391136312610.642189wood41000188

10、1615011.177239kowosb41000482112670.630418bd424869673730.809928watson100100028599150199.887660watson100100028599150198.279792rosex10039563595931.155830singx208911207813391.018593singx208911207813391.014329penl101000118710180.468902penl101000118710180.521887pen2101000723012630.698659pen210100072301263

11、0.753243vardim1043176636490.526210vardim1043176636490.594956trig10853811190.058357trig10853811190.057003bv1045944736910.386874bv1045944736910.435729IE1001499412264.135373IE1001499412264.055840trid1024333213670.302492trid1024333213670.240762band1064927970.083523lin1053298820.042389lin1053298820.04540

12、8linl1038831540.295686linO1024657350.065704五、结果分析通过对两种迭代方法迭代速度的比较我们可以得出以下结论：（1）最速下降法收敛速度较慢，很多问题无法的规定迭代次数内得到最优解即达到终止条件。（2）共轭梯度H-S法收敛速度较快，可以得出大多数测试问题的最优解。六、优缺点分析6.1优点（1）通过两种算法比较，直观表现两种算法的优缺点（2）程序通用性高，可读性强。6.2缺点(1)共轭梯度H-S法中k的求解分母上存在减法，当分母很小时会产生较大误差。(2)共轭梯度法的步长需采用精确搜索，采用Wolfe-Powell搜索难以保证方向共轭性。七、实验心得对最优

13、化半学期的学习，我基本掌握了无约束优化梯度法，但这些仅仅是课本上学来的理论知识，这次的上机实践，使得我们对这些算法的思想更加了解，在选用算法时，总结出：解决问题的算法对问题至关重要，但是没有万能的算法，所以要根据实际问题来选用能够使问题整体效率最高的算法。在选择线性搜索的方法时，我们深刻体会到各类参数设置对程序效率的重要性，不同的问题要选用合适的参数来求解，这样使得问题求解及程序运行的效率最高。上学期学习计算方法时也学习过matlab，但还是学的只是表面简单的东西，本次实验过程中遇到了很多棘手的问题，但是通过不断地翻阅课本，剖析程序，互相探讨以及老师的悉心指导，我们最后实现了对程序的修改和完善

14、，对提供的问题作出了较好的解答。总的来说，对无约束最优化的求解，每种方法在解决不同的问题中效果不能都达到最优，所以我们在实际应用中，要根据实际情况选择合适的方法，争取最大可能的尽快的接近最优。本次上机实验不仅使我们基本了解了最优化的实用算法的结构及性能，而且也使得我们对matlab的一些编程技巧更加熟悉，收获很大。八、附录主程序：%最速下降与共轭梯度H-SprogramusingWolfe-Powellsearch%clc;epsilon=0.051;teminate=1.0e-5;factor=0.1;numer=1,2,3,4,5,6,7,89,10,11,12,13,14,15,16,2

15、0,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,1000,200,500,50,200,200,500,1000,10,10no=size(numer);nn=no(:,2);fors=1:2ifs=1epsilon=0.05;fprintf(nt*最速下降法methodresults*、n)fprintf(tProblemtDim

16、.tlter.tfnumtgnumtCPUn);fprintf(t*n);elseepsilon=0;fprintf(t*共轭梯度法H-Smethodresultsfprintf(tProblemtDim.tlter.tfnumtgnumtCPUn);endfprintf(t*forp=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;

17、delta=norm(gk,2);whilek1000ifdelta=-1.0e-14%当dk不是充分下降时采用负梯度为搜索方向dk=_gk;endendendgk仁gk;fk仁fk;dk仁dk;alphak,fk,gk,wfnum,wgnum=wolfe2(n,m,xk,dk,fk1,gk1,nprob);ifalphak=Obreak;endfnum=fnum+wfnum;gnum=gnum+wgnum;xk仁xk;xk=xk1+alphak*dk;k=k+1;fk=objfcn(n,m,xk,nprob);fnum=fnum+1;gk=grdfcn(n,m,xk,nprob);gnum=

18、gnum+1;ifnorm(gk,2)=teminate%终止测试break;endk=k+1;endtime=toc;iftime=0.000001t(p,s)=0.0001;elset(p,s)=time;endfprintf(nt%st%4dt%5dt%5dt%5dt%3fn,filename,n,k,fnum,gnum,time);endend%clc;%作图开始ZT=0.01;Tau=10;Mp=size(t,1);%测试问题数目%Ms=size(t,2);%求解方法数目%r=zeros(Mp,Ms);forp=1:Mpmintp=min(t(p,1:Ms);%在所有求解器中对每一测

19、试问题提取最小CPU时间%ifmintp=0mintp=O.OO1;endfors=1:Msr(p,s)=t(p,s)/mintp;endendrho=zeros(Ms);holdon;%numbers=zeros(1,Ms);fors=1:Msnumbers=zeros(1,(Tau)/ZT);fortau=0.00001:ZT:Tauforp=1:Mpifr(p,s)=tauk=ceil(tau-1)/ZT);numbers(k)=numbers(k)+1;endendendswitchscase1%最速下降法tau=1.00001:ZT:Tau;k=ceil(tau-1)/ZT);plo

20、t(tau,numbers(k)/Mp,:b);ax=plot(tau,numbers(k)/Mp)case2%共轭梯度法tau=1.00001:ZT:Tau;k=ceil(tau-1)/ZT);plot(tau,numbers(k)/Mp,-.m);end%plot(tau-0.01tau,rho(s)rho(s),-r);%set(gca,xtick,1.:ZT:Tau);%gridon;%画网格线set(gca,xTick,1:1:10);set(gca,yTick,0:0.1:1);%box;end%title(distrubtionfunction);xlim=get(gca,XLi

21、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:1leqsleqn_s);%设置y坐标名称legend(最速下降法,共轭梯度法H-S,4)holdoff;%作图结束wolfe2搜索：%WolfeLineSearchfunctionalphak1,fk2,

22、gk2,wfnum,wgnum=wolfe2(n,m,xk,dk,fk,gk,nprob)rho1=0.8;rho2=0.6;sigma1=0.01;sigma2=0.6;fk仁fk;gk仁gk;wfnum=0;wgnum=0;%step0alphak仁1;fk2=objfcn(n,m,xk+alphak1*dk,nprob);wfnum=wfnum+1;gk2=grdfcn(n,m,xk+alphak1*dk,nprob);wgnum=wgnum+1;iffk2-fk1=sigma2*gk1*dkreturn;end%step0else%step1%i=-8;while1ifi=0alpha

23、k仁rho1Ai;fk2=objfcn(n,m,xk+alphak1*dk,nprob);wfnum=wfnum+1;endiffk2-fk1sigma1*rho1Ai*gk1*dk%alphak=alphak1break;endelseendend%alphak仁rho19%step1%j=0；while1alphak仁rho2Aj*alphak1;ifalphak仁=0break;endgk2=grdfcn(n,m,xk+alphak1*dk,nprob);wgnum=wgnum+1;ifgk2*dk=sigma2*gk1*dk%alphak=alphak1;break;endj=j+1;endend注：加黑处为对程序的主要修改。