最優(yōu)化實驗報告

《數(shù)值最優(yōu)化算法與理論》課程實驗報告姓名：周飛飛(202210020231)張琳靖(202210020228)班級： 信息與計算科學(xué)2班指導(dǎo)教師：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)無約束問題運算結(jié)束后記錄所花費時間time=toc;%終止計時iftime<=0.000001t(i,s)=0.0001;elset(i,s)=time;End(8)輸出無約束問題的運行結(jié)果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)參數(shù)設(shè)置：Wolf-powell搜索中的兀=0.8,兀=0.6,。-0.01,a=0.6；1 1 2擬牛頓法及共拆梯度法中相關(guān)參數(shù)：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,迭代次數(shù)k<1000,若迭代次數(shù)達到1000,仍無法滿足Rf(x(k))||w￡的條件，則退出算法。三、實驗結(jié)果及分析運行Matlab程序(見附錄)得如下結(jié)果：***************************才以屯員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運行時間分布圖對照:結(jié)果分析：總體上可明顯看出擬牛頓法比FR共甄梯度法效率要高。雖然對某一特定的無約束問題，可能會浮現(xiàn)用擬牛頓法反而沒有FR共輒梯度法節(jié)約時間，計算量小，迭代次數(shù)少的情況。從得出的數(shù)據(jù)上看，由于34個不同的問題，除個別問題外，擬牛頓法運行時間基本保持在很短的水平，故得出的圖象較為平整，波動較??；而共輾梯度法在處理不同問題時所用的時間較不穩(wěn)定，且有些問題耗費時間明顯較多，故圖象浮動較大。故可以得出結(jié)論，較FR共粗梯度法，擬牛頓法在解決無約束問題上效率更高，穩(wěn)定性更好。四、實驗心得在平時上課時有不少求解無約束問題的方法只知道一些大概，許多算法上的細節(jié)上缺乏深入的理解，通過這次實驗在這方面知識上得到了補充，同時在Matlab軟件應(yīng)用上也有了一定的進步。實驗的準備期，通過翻閱課本及網(wǎng)上資源的查找，我逐漸理解了最速下降法、牛頓法、擬牛頓法及共粗梯度法在算法上的區(qū)別，各個算法的性質(zhì)，存在的優(yōu)點和缺陷。了解到這些方法之間并非獨立的，牛頓法可以說是在最速下降法上的升華，擬牛頓法又是在克服牛頓法的缺陷的基礎(chǔ)上建立的，共輾梯度法則是介于最速下降法和牛頓法之間的一種方法。解決無約束問題的算法百樣，但是我們現(xiàn)所學(xué)的都是基于下降算法的方法，無論是最速下降法，擬牛頓法，或者是共班梯度法，都是主要解決如何尋覓更優(yōu)更快的下降方向，及如何更加合理地取得步長，這一共同點使我在理解算法上得到了很大的匡助。Matlab軟件實現(xiàn)過程，由于Matlab軟件是這學(xué)期夏季學(xué)期學(xué)習(xí)了，雖然一些基本語法還記得，但是在編寫程序上還是存在艱難，時常遇到報錯的情況，通過多次的調(diào)試才得以運行。無非正是這個算法轉(zhuǎn)化為程序語言的過程，讓我較之前能更熟練得運用Matlab軟件，也更加注意算法中的一些細節(jié)。附錄:%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%擬牛頓法及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);%%%%%%%%讀初始數(shù)據(jù)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);%%%%%%%%讀初始數(shù)據(jù)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);《數(shù)值最優(yōu)化算法與理論》課程實驗報告課程名稱數(shù)值最優(yōu)化算法與理論 班級 信息與計算科學(xué)2班小組成員周飛飛(202210020231)張琳靖(202210020228)實驗課題擬Newton法（BFGS算法）及FR共加梯度法求解無約束問題實驗?zāi)康耐ㄟ^上機實驗掌握最優(yōu)化的實用算法的結(jié)構(gòu)及性能，并用這些算法解決實際的最優(yōu)化問題，掌握一些實用的編程技巧。實驗要求選用你喜歡的無約束優(yōu)化的某種梯度法（最速下降法，Newton法，擬牛頓法，共輾梯度法）通過編程，上機實驗對所提供的測試問題進行測試、運行，然后提供實驗報告。在實驗報告中指出你選用的算法、參數(shù)設(shè)置、終止準則、線性搜索以及實驗結(jié)果，附加你的實驗心得。實驗內(nèi)容使用非精確Wolf-Powell線性搜索實現(xiàn)擬牛頓法（BFGS算法）及FR共輾梯度法求解無約束問題，并通過Matlab軟件實現(xiàn)算法，觀察分析實驗過程，對照實驗結(jié)果來進一步理解兩種方法的原理及優(yōu)點與缺陷。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);%測試問題數(shù)目％Ms=size(t,2);%求解方法數(shù)目%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;%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%作圖結(jié)束TOC\o"1-5"\h\z\o"CurrentDocument"1、實驗原理 1\o"CurrentDocument"2、實驗內(nèi)容 43、實驗結(jié)果與分析 8\o"CurrentDocument"4、實驗心得 12附錄 13一、實驗原理無約束問題minf(x),x=Rn這里函數(shù)f：RnTR是連續(xù)可微的下降算法是求解無約束優(yōu)化問題的一類最基本的算法。其普通步驟為：(已知近似最優(yōu)解X)k1.首先，計算下降方向d滿足：Vf(x)Td<0k kk2?然后計算步長a>0滿足：f(X+ad)<f(X)k kkk k.計算新的近似最優(yōu)解：X=X+adk+1kkk這次實驗所運用的擬牛頓法及FR共朝梯度法主要是在下降算法的基礎(chǔ)上，求解下降方向的方法上有所不同。(一)擬牛頓法(1)擬牛頓法的簡述擬牛頓法(Quasi-NewtonMethods)是求解非線性優(yōu)化問題最有效的方法之一，于20世紀50年代由美國Argonne國家實驗室的物理學(xué)家W.C.Davidon所提出來。Davidon設(shè)計的這種算法在當時看來是非線性優(yōu)化領(lǐng)域最具創(chuàng)造性的發(fā)明之一。不久R.Fletcher和業(yè)J.D.Powell證實了這種新的算法遠比其他方法快速和可靠，使得非線性優(yōu)化這門學(xué)科在一夜之間突飛猛進。擬牛頓法和最速下降法(SteepestDescentMethods)一樣只要求每一步迭代時知道目標函數(shù)的梯度。通過測量梯度的變化，構(gòu)造一個目標函數(shù)的模型使之足以產(chǎn)生超線性收斂性。這種方法大大優(yōu)于最速下降法，特別對于艱難的問題。另外，因為擬牛頓法不需要二階導(dǎo)數(shù)的信息，所以有時比牛頓法(Newton'sMethod)更為有效。如今，優(yōu)化軟件中包含了大量的擬牛頓算法用來解決無約束，約束，和大規(guī)模的優(yōu)化問題。(2)擬牛頓法的思想擬牛頓法是對牛頓法的一種改善保持其優(yōu)點：快速收斂性克服其缺陷：需計算Hessian矩陣且要求其正定方法：構(gòu)造對稱正定矩陣B或者H使其滿足kkB?V2f(x)或者H?V2f(x)-1k k k k4留土由方七面d=-BZf(x)(擬Newton方向)計算搜索方向： kkk ,或者：d=-HVf(x)(擬Newton方向)k kk構(gòu)造B的要求如下：kB必條2f(x)使得產(chǎn)生的擬Newton方向近似Newton方向；k kVk>0,B對稱正定,使得產(chǎn)生的擬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,算法終止.否則轉(zhuǎn)下一步；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,轉(zhuǎn)步3.(二)非線性共趣梯度法(FR算法)(1)共軌梯度法的簡述共班梯度法是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導(dǎo)數(shù)信息，但克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hessian矩陣并求逆的缺點，共枕梯度法不僅是解決大型線性方程組最實用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一。 共加梯度法最早是由Hestenes和Stiefle(1952)提出來的，用于解正定系數(shù)矩陣的線性方程組，在這個基礎(chǔ)上，F(xiàn)letcher和Reeves(1964)首先提出了解非線性最優(yōu)化問題的共掘梯度法。由于共輾梯度法不需要矩陣存儲，且有較快的收斂速度和二次終止性等優(yōu)點，現(xiàn)在共班梯度法已經(jīng)廣泛地應(yīng)用與實際問題中。共軌梯度法是一個典型的共班方向法，它的每一個搜索方向是互相共加的，而這些搜索方向d僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便。(2)共甄梯度法的思想Fletcher-Reeves共加梯度法，簡稱FR法。共軌梯度法的基本思想是把共輒性與最速下降方法相結(jié)合，利用已知點處的梯度構(gòu)造一組共甄方向，并沿這組方向進行搜素，求出目標函數(shù)的極小點。根據(jù)共鈍方向基本性質(zhì)，這種方法具有二次終止性。給定初始點x=Rn,取初始搜索方向d二一條f(x),在后面的迭代中取負梯度方0 0 0向和前一搜索方向的線性組合作為搜索方向即d二一條f(x)+bd,k＞1,其中k kkk—1b是待定參數(shù)，適當選取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,算法終止.否則轉(zhuǎn)步3；k k步3由線性搜索計算步長以；k步4令x=x+以d；k+1 kkk步5由(21)確定d，其中b=bFR令k:=k+1,轉(zhuǎn)步2k+1 k+1k+1(三)囚。1￡6一口皿611線搜索Wolfe-Powel線性搜索：給定常數(shù)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;否則轉(zhuǎn)下一步.步1：給定常數(shù)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轉(zhuǎn)步長, 3.步3k:令以…4 ｛集合以(訃+pj(僅“一以m)卜01J中使得(3.1)中第一個不等式成立k k1kk的最大值.令：=i+1.轉(zhuǎn)步2二、實驗內(nèi)容擬牛頓法程序：fori=l:nn%%%1-nn函數(shù)挨次進入運算(1)初值準備nprob=numer(i);[n,m,xk,filename]=initf(nprob);%%%%%%%%讀初始數(shù)據(jù)xk=fact