最优化实验报告

《数值最优化算法与理论》课程实验报告姓名：周飞飞(202210020231)张琳靖(202210020228)班级： 信息与计算科学2班指导教师：2022年11月27日gnum=l;delta=norm(gk,2);dk=-gk;(2)迭代开始whilek<1000 %%%%%%%%%迭代上限1000ifdelta<=teminatebreak;elsegkl=gk;fkl=fk;(3)确定步长九K%%%%%%%%%%%%%%%%%%%%%利用Wolfe-Powell搜索计算步长[alphak,fk,gk,wfnum,wgnum]=wolfe2(n,m,xk,dk,fkl,gkl,nprob);%%%%%%%%%%%%%%%%%%%%%t?JfflWolfe-Powell搜索计算步长(4)计算Xk+1fnum=fnum+wfnum;gnum=gnum+wgnum;xkl=xk;xk=xkl+alphak*dk;(5)确定下降方向d(k)fk=objfen(nzm,xk,nprob);gk=grdfcn(n,m,xk,nprob);temkl=norm(gkl,2);temk=norm(gk,2);dkl=dk;bk=temkA2/temklA2;dk=-gk+bk*dkl;endk=k+l;delta=norm(gk,2);End(6)无约束问题运算结束后记录所花费时间time=toc;%终止计时iftime<=0.000001t(i,s)=0.0001;elset(i,s)=time;End(8)输出无约束问题的运行结果fprintf(1\n\t%s\t\t\t%2d\t\t\t%5d\t\t\t\t%5d\t\t\t%5d\t\t\t%4f\n1rfilename,n,k,fnum,gnum,time);End非精确Wolf-powell线性搜索function[alphakl,fk2,gk2,wfnum,wgnum]=wolfe2(n,m,xk,dk,fk,gk,nprob)rhol=0.8;rho2=0.6;sigmal=0.01;sigma2=0.6;%兀=0.8,兀1二0.6,O1二0.01,%=0.6fkl=fk;gkl=gk;wfnum=0;wgnum=0;%step0alphakl=l;fk2=objfcn(n,m,xk+alphakl*dk,nprob);wfnum=wfnum4-1;gk2=grdfcn(n,mzxk+alphakl*dk,nprob);wgnum=wgnum+1;iffk2-fkl<=sigma1*alphakl*gkl1*dk

ifgk2'*dk>=sigma2*gkl1*dkreturn;end%step0else%step1%%%%%%%%%%%%%%%%%%%%%i=-8;while1ifi~=0alphakl=rholAi;fk2=objfen(n,m,xk+alphakl*dk,nprob);wfnum=wfnum+1;endiffk2-fkl<=sigma1*alphakl*gkl1*dki=i-l;fk2=objfen(nzmzxk+rholAi*dk,nprob);iffk2-fkl>sigmal*rholAi*gkl1*dk%alphak=alphaklbreak;endelsei=i+l;endend%alphakl=rholAi%step1%%%%%%%%%%%%%%%%%%%%%%%j=o；while1alphakl=rho2Aj*alphakl;ifalphakl==Obreak;endgk2=grdfcn(n,m,xk+alphakl*dk,nprob);wgnum=wgnum+1；ifgk2**dk>=sigma2*gkl'*dk%alphak=alphakl;break;endj=j+l；endEnd(1)参数设置：Wolf-powell搜索中的兀=0.8,兀=0.6,。-0.01,a=0.6；1 1 2拟牛顿法及共拆梯度法中相关参数：teminate=l.Oe-6;factor=0.1numer=[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];(2)终止准则：Wolf-powell算法终止：当搜索到步长aO)满足(3.1)的第二个不等式时终k止程序；拟牛顿法及共辄梯度法算法终止：当M(x⑹)|卜七时，此处匕=teminate=1.0e-6,迭代次数k<1000,若迭代次数达到1000,仍无法满足Rf(x(k))||w£的条件，则退出算法。三、实验结果及分析运行Matlab程序(见附录)得如下结果：***************************才以屯员resuits***************************ProblemDim.Iter.fnumgnumtime********************************************************************rose23273623301.701463froth22022282040.202236badscp21000108110020.911348badscb21562191590.170202beale23943953950.338338jensam281109840.098432helix31312121360.160998bard31000105210032.357615gauss37717727721.112494gulf31000100110011.130130box32622632630.276804sing41000102810030.877423wood42453652540.236166kowosb41000100110011.025711bd41000312757911754601.421517bigss61000101410026.634311osb2111000105010044.903811watson10010001172100932.726229rosex10042716514954.125570singx201000102810032.215915peril101000100110013.435982pen2101000100110012.011244vardim1084148860.197684trig106263630.178239bv101000100110011.587811IE1006061613.226137trid1031180460.185056band1028241460.243491lin108788880.295781Iin11045660.093807linO1045260.043293**********************FR共9梯度results***********************Problem，**********Dim.*******Iter.**********fnum**************gnum***********time**********rose221971654391.464882froth223494624691.806027badscp2100096436200115.215235badscb21000135547202215.917961beale225562525030.921001jensam29737361950.667411helix325185325031.418059bard336272697193.800870gauss322140344120.826613gulf311330.003870box310004190719947.366457sing410003059920013.308938wood410005676720015.802187kowosb410003937119876.781742bd4100023575318409317.418211bigss610002833919984.479351osb211100039071200116.598379watson1001000636672001351.867009rosex100439154298795.235774singx2010002952520017.609801peril10460116995368.503069pen2106341540012553.928670vardim1013848962770.771366trig1034179510.070117bv109052168318114.307150IE100107112420312.088222trid1010002879520013.960488band101000717831237013.859478lin1044243670.102122Iin1108450701690.782205linO101000297548010278321.160871运行时间分布图对照:结果分析：总体上可明显看出拟牛顿法比FR共甄梯度法效率要高。虽然对某一特定的无约束问题，可能会浮现用拟牛顿法反而没有FR共辄梯度法节约时间，计算量小，迭代次数少的情况。从得出的数据上看，由于34个不同的问题，除个别问题外，拟牛顿法运行时间基本保持在很短的水平，故得出的图象较为平整，波动较小；而共辗梯度法在处理不同问题时所用的时间较不稳定，且有些问题耗费时间明显较多，故图象浮动较大。故可以得出结论，较FR共粗梯度法，拟牛顿法在解决无约束问题上效率更高，稳定性更好。四、实验心得在平时上课时有不少求解无约束问题的方法只知道一些大概，许多算法上的细节上缺乏深入的理解，通过这次实验在这方面知识上得到了补充，同时在Matlab软件应用上也有了一定的进步。实验的准备期，通过翻阅课本及网上资源的查找，我逐渐理解了最速下降法、牛顿法、拟牛顿法及共粗梯度法在算法上的区别，各个算法的性质，存在的优点和缺陷。了解到这些方法之间并非独立的，牛顿法可以说是在最速下降法上的升华，拟牛顿法又是在克服牛顿法的缺陷的基础上建立的，共辗梯度法则是介于最速下降法和牛顿法之间的一种方法。解决无约束问题的算法百样，但是我们现所学的都是基于下降算法的方法，无论是最速下降法，拟牛顿法，或者是共班梯度法，都是主要解决如何寻觅更优更快的下降方向，及如何更加合理地取得步长，这一共同点使我在理解算法上得到了很大的匡助。Matlab软件实现过程，由于Matlab软件是这学期夏季学期学习了，虽然一些基本语法还记得，但是在编写程序上还是存在艰难，时常遇到报错的情况，通过多次的调试才得以运行。无非正是这个算法转化为程序语言的过程，让我较之前能更熟练得运用Matlab软件，也更加注意算法中的一些细节。附录:%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%拟牛顿法及FR共掘梯度法programusingWolfe-Powellsearch%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%clc;muk=10;teminate=l.Oe-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=l;fprintf(1\n\t*****************★★★夫夫夫大*火*拟牛顿法工㊀$口1七$********大*大********火★★**fprintf(r\tProblem\t\tDim.\t\tlter.\t\t\tfnum\t\tgnum\t\ttime\nT);fprintf('\t**********************************************fprintf('\t**********************fori=l:nnnprob=numer(i);[n,m,xk,filename]=initf(nprob);%%%%%%%%读初始数据xk=factor*xk;bk=eye(n);k=0;tic;%计时开始fk=objfen(n,m,xk,nprob);fnum=l;gk=grdfcn(n,m,xk,nprob);gnum=l;delta=norm(gk,2);whilek<1000%%%%%%%%%迭代上限1000ifdelta<=teminatebreak;elsedk=-linsolve(bk+muk*eye(n),gk);gkl=gk;fkl=fk;gkdk=gk1*dk;ifgk1ifgk1*dk>=-l.Oe-14当％~]＜不是充分下降时采用负梯度为搜索方向dk=-gk;end%%%%%%%%%%%%%%%%%%%%%利用Wolfe-Powell搜索计算步长[alphakAfk,gk,wfnum,wgnum]=wolfe2(n,m,xk,dk,fklrgkl,nprob)；%%%%%%%%%%%%%%%%%%%%%^ljfflWolfe-Powell搜索计算步长fnum=fnum+wfnum;gnum=gnum+wgriuim;xkl=xk;xk=xkl+alphak*dk;fk=objfen(n,m,xk,nprob);gk=grdfcn(n,m,xk,nprob);ifnorm(gkA2)dominatek=k+l;break;end%%%%%%%%%%%%%%%%%Bkupdatesk=xk-xkl;bks2=sk**bk*sk;yk=gk-gkl;yksk=yk1*sk;ifyksk>0bksl=bk*sk*sk1*bk;yks=yk*yk'/yksk;bkl=bk;bk=bkl-bkl*sk*sk!*bkl/(sk1*bkl*sk)+yk*yk1/(yk1*sk);endendk=k+l;endtime=toc;%终止计时iftime<=0.000001t(i,s)=0.0001;elset(i,s)=time;endfprintf(1\n\t%s\t\t%2d\t\t%5d\t\t\t%5d\t\t%5d\t\t%4f\n1zfilename,n,k,fnum,gnum,time);ends=2;fprintf(1\n\ti**************71r★★★★****★*FR共辆梯度法\n1);工㊀suits\n1);fprintf(1\tProblem\t\tDim.\t\tlter.\t\t\tfnum\t\tgnum\t\ttime\n1);fprintf('\t**********************************************fprintf('\t**********************\n])fori=l:nnnprob=numer(i);[n,m,xk,filename]=initf(nprob);%%%%%%%%读初始数据xk=factor*xk;bk=eye(n);k=0;tic;%计时开始fk=objfen(n,m,xk,nprob);fnum=l;gk=grdfcn(n,m,xk,nprob);gnum=l;delta=norm(gk,2);dk=-gk;whilek<1000%%%%%%%%%迭代上限1000ifdelta〈=teminat㊀break;elsegkl=gk;fkl=fk;%%%%%%%%%%%%%%%%%%%%%!«JfflWolfe-Powell搜索计算步长[alphak,fk,gk,wfnum,wgnum]=wolfe2(n,m,xk,dk,fklrgklrnprob)；用％会超％格居％%%%%%%%%%%%利用Wolfe-Powell搜索计算步长fnum=fnum+wfnuim;gnum=gnum+wgnum;xkl=xk;xk=xkl+alphak*dk;fk=objfen(n,m,xk,nprob);gk=grdfcn(n,m,xk,nprob);temkl=norm(gkl,2);temk=norm(gk,2);《数值最优化算法与理论》课程实验报告课程名称数值最优化算法与理论 班级 信息与计算科学2班小组成员周飞飞(202210020231)张琳靖(202210020228)实验课题拟Newton法（BFGS算法）及FR共加梯度法求解无约束问题实验目的通过上机实验掌握最优化的实用算法的结构及性能，并用这些算法解决实际的最优化问题，掌握一些实用的编程技巧。实验要求选用你喜欢的无约束优化的某种梯度法（最速下降法，Newton法，拟牛顿法，共辗梯度法）通过编程，上机实验对所提供的测试问题进行测试、运行，然后提供实验报告。在实验报告中指出你选用的算法、参数设置、终止准则、线性搜索以及实验结果，附加你的实验心得。实验内容使用非精确Wolf-Powell线性搜索实现拟牛顿法（BFGS算法）及FR共辗梯度法求解无约束问题，并通过Matlab软件实现算法，观察分析实验过程，对照实验结果来进一步理解两种方法的原理及优点与缺陷。dkl=dk;bk=temkA2/temklA2;dk=-gk+bk*dkl;endk=k+l;delta=norm(gk,2);endtime=toc;%终止计时iftime<=0.000001t(i,s)=0.0001;elset(i,s)=time;endfprintf(1\n\t%s\t\t%2d\t\t%5d\t\t\t%5d\t\t%5d\t\t%4f\n,rfilename,n,k,fnum,gnum,time);end%clc;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%作图开始ZT=0.01;Tau=10;Mp=size(t,1);%测试问题数目％Ms=size(t,2);%求解方法数目%r=zeros(Mp,Ms);fori=l:Mpmintp=min(t(iz1:Ms));%在所有求解器中对每一测试问题提取最小CPU时间%ifmintp==0mintp=0.001;endfors=l:Ms工(i,s)=t(i,s)/mintp;endendrho=zeros(Ms);holdon;fors=l:Msnumbers=zeros(1,(Tan)/ZT);fortau=0.00001:ZT:Taufori=l:Mpifr(i,s)<=tauk=ceil((tau-1)/ZT);numbers(k)=numbers(k)+1;endendendswitchscase1拟％牛顿法tau=l.00001:ZT:Tau;k=ceil((tau-1)/ZT);plot(tau,numbers(k)/Mp,1:b1);case2%块R粒梯度法tau=l.00001:ZT:Tau;k=ceil((tau-1)/ZT);plot(tau,numbers(k)/Mp,1-.m1);endset(gca,1xTick!,[1:1:10]);set(gca,1yTick!,[0:0.1:1]);endtitle(1distrubtionfunction1);xlim=get(gcaA1XLim1);ylim=get(gca,1YLim1);h=xlabel(1\tau1);set(hz1Position*r[xlim(2)+(xlim(2)-xlim(1))*0.05Aylim(l)])；text(xlim(l)-0.4,ylim(2)+0.02, 1rotation1A0);legend[拟牛顿法\1FR共辗梯度法I4)holdoff;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%作图结束TOC\o"1-5"\h\z\o"CurrentDocument"1、实验原理 1\o"CurrentDocument"2、实验内容 43、实验结果与分析 8\o"CurrentDocument"4、实验心得 12附录 13一、实验原理无约束问题minf(x),x=Rn这里函数f：RnTR是连续可微的下降算法是求解无约束优化问题的一类最基本的算法。其普通步骤为：(已知近似最优解X)k1.首先，计算下降方向d满足：Vf(x)Td<0k kk2•然后计算步长a>0满足：f(X+ad)<f(X)k kkk k.计算新的近似最优解：X=X+adk+1kkk这次实验所运用的拟牛顿法及FR共朝梯度法主要是在下降算法的基础上，求解下降方向的方法上有所不同。(一)拟牛顿法(1)拟牛顿法的简述拟牛顿法(Quasi-NewtonMethods)是求解非线性优化问题最有效的方法之一，于20世纪50年代由美国Argonne国家实验室的物理学家W.C.Davidon所提出来。Davidon设计的这种算法在当时看来是非线性优化领域最具创造性的发明之一。不久R.Fletcher和业J.D.Powell证实了这种新的算法远比其他方法快速和可靠，使得非线性优化这门学科在一夜之间突飞猛进。拟牛顿法和最速下降法(SteepestDescentMethods)一样只要求每一步迭代时知道目标函数的梯度。通过测量梯度的变化，构造一个目标函数的模型使之足以产生超线性收敛性。这种方法大大优于最速下降法，特别对于艰难的问题。另外，因为拟牛顿法不需要二阶导数的信息，所以有时比牛顿法(Newton'sMethod)更为有效。如今，优化软件中包含了大量的拟牛顿算法用来解决无约束，约束，和大规模的优化问题。(2)拟牛顿法的思想拟牛顿法是对牛顿法的一种改善保持其优点：快速收敛性克服其缺陷：需计算Hessian矩阵且要求其正定方法：构造对称正定矩阵B或者H使其满足kkB«V2f(x)或者H«V2f(x)-1k k k k4留土由方七面d=-BZf(x)(拟Newton方向)计算搜索方向： kkk ,或者：d=-HVf(x)(拟Newton方向)k kk构造B的要求如下：kB必条2f(x)使得产生的拟Newton方向近似Newton方向；k kVk>0,B对称正定,使得产生的拟Newton方向为下降方向；kB易于计算.k(3)拟牛顿法的BFGS算法BFGS修正公式：B=B—BsSTBkkkk-+yyTkk. (1.1)k+1kStBS yTSkkk kk该公式由：Broyden-Fletcher-Goldfarb-Shanno提出，是迄今为止最好的拟牛顿修正公式。BFGS算法：TOC\o"1-5"\h\z步1给定初始点x二Rn,初始对称正定矩阵B,精度C>0.0 0令k=0;步2若||条f(x)||共C,则得解x,算法终止.否则转下一步；k k步3解线性方程组Bd+条f(x)=0 (4.16)k k得解d;k步4由线性搜索计算步长a;k步5令x=x+ad,若||条f(x川共c,则得解x,k+1kkk k+1 k+1算法终止.否则由公式(1.1)计算B;k+1步6令k:=k+1,转步3.(二)非线性共趣梯度法(FR算法)(1)共轨梯度法的简述共班梯度法是介于最速下降法与牛顿法之间的一个方法，它仅需利用一阶导数信息，但克服了最速下降法收敛慢的缺点，又避免了牛顿法需要存储和计算Hessian矩阵并求逆的缺点，共枕梯度法不仅是解决大型线性方程组最实用的方法之一，也是解大型非线性最优化最有效的算法之一。 共加梯度法最早是由Hestenes和Stiefle(1952)提出来的，用于解正定系数矩阵的线性方程组，在这个基础上，Fletcher和Reeves(1964)首先提出了解非线性最优化问题的共掘梯度法。由于共辗梯度法不需要矩阵存储，且有较快的收敛速度和二次终止性等优点，现在共班梯度法已经广泛地应用与实际问题中。共轨梯度法是一个典型的共班方向法，它的每一个搜索方向是互相共加的，而这些搜索方向d仅仅是负梯度方向与上一次迭代的搜索方向的组合，因此，存储量少，计算方便。(2)共甄梯度法的思想Fletcher-Reeves共加梯度法，简称FR法。共轨梯度法的基本思想是把共辄性与最速下降方法相结合，利用已知点处的梯度构造一组共甄方向，并沿这组方向进行搜素，求出目标函数的极小点。根据共钝方向基本性质，这种方法具有二次终止性。给定初始点x=Rn,取初始搜索方向d二一条f(x),在后面的迭代中取负梯度方0 0 0向和前一搜索方向的线性组合作为搜索方向即d二一条f(x)+bd,k＞1,其中k kkk—1b是待定参数，适当选取b,使得drQd=0ok k kk—1FR共钝梯度法，搜索方向的计算公式为：(2.1)条f(x), k=0(2.1)d二〈. °kI-条f(X)+bkFRq］，k＞1FR共加梯度法算法“条由川2“条由川2II条f(X)||2k-1Fletcher-Reeves(1964)提出。FR算法：步1给定初始点X二Rn,精度c＞0.令d=-条f(X，令0 0 0k:=0;步2若||条f(x)||共C,则得解x,算法终止.否则转步3；k k步3由线性搜索计算步长以；k步4令x=x+以d；k+1 kkk步5由(21)确定d，其中b=bFR令k:=k+1,转步2k+1 k+1k+1(三)囚。1£6一口皿611线搜索Wolfe-Powel线性搜索：给定常数0＜装＜1/2,装＜装＜11 1 2取以＞0使得k(f(x+以d)共f(x)+装以条f(x)Td(kkkk1kkk(3.1)I条f£+/Q)Tdk＞选条f保)TdkArmijo型线性搜索的条件是 Wolfe-Powell型线性搜索中的第一个条件。Wo斤e-Powell型线性搜索中的第二个条件的作用在于限制过小的步长，减少了求解时的计算量。同时运用非精确Wo佗-Powell线性搜索保证了拟牛顿法(BFDS算法)中的B矩阵对称正定。kWolfe-Powell线搜索算法：步0:若以=1满足(3.1),则取以=1;否则转下一步.步1：给定常数b＞0,p,p=(0,1).令以(。)是集合｛bp|i=0,土1,±2,…｝中使得⑶1)中k i的第一个不等式成立的最大值.令：=0.步2:若以(i)满足(3.1)中的第二个不等式，则终止计算，并得步长以二以(i)；否则，k kk令b(i=p-mj转步长, 3.步3k:令以…4 ｛集合以(讣+pj(仅“一以m)卜01J中使得(3.1)中第一个不等式成立k k1kk的最大值.令：=i+1.转步2二、实验内容拟牛顿法程序：fori=l:nn%%%1-nn函数挨次进入运算(1)初值准备nprob=numer(i);[n,m,xk,filename]=initf(nprob);%%%%%%%%读初始数据xk=fact