最優(yōu)化課程設(shè)計共軛梯度法算法分析與實現(xiàn)樣本

資料內(nèi)容僅供您學(xué)習(xí)參考，如有不當(dāng)或者侵權(quán)，請聯(lián)系改正或者刪除。最優(yōu)化課程設(shè)計--共軛梯度法算法分析與實現(xiàn)(設(shè)計程序)題目共軛梯度法算法分析與實現(xiàn)班級/學(xué)號14140101/學(xué)生姓名黃中武指導(dǎo)教師王吉波王微微課程設(shè)計任務(wù)書課程名稱最優(yōu)化方法課程設(shè)計院(系)理學(xué)院專業(yè)信息與計算科學(xué)課程設(shè)計題目共軛梯度法算法分析與實現(xiàn)課程設(shè)計時間:年6月16日至年6月27日課程設(shè)計的要求及內(nèi)容:[要求]1.學(xué)習(xí)態(tài)度要認(rèn)真,要積極參與課程設(shè)計,鍛煉獨立思考能力;2.嚴(yán)格遵守上機時間安排;3.按照MATLAB編程訓(xùn)練的任務(wù)要求來編寫程序;4.根據(jù)任務(wù)書來完成課程設(shè)計論文;5.報告書寫格式要求按照沈陽航空航天大學(xué)”課程設(shè)計報告撰寫規(guī)范”;6.報告上交時間:課程設(shè)計結(jié)束時上交報告;7.嚴(yán)禁抄襲行為,一旦發(fā)現(xiàn),課程設(shè)計成績?yōu)椴患案?。一、運用共軛梯度法求解無約束最優(yōu)化問題要求:1)了解求解無約束最優(yōu)化問題的共軛梯度法;2)繪出程序流程圖;3)編寫求解無約束最優(yōu)化問題的共軛梯度法MATLAB程序;4)利用編寫文件求解某無約束最優(yōu)化問題;5)給出程序注釋。指導(dǎo)教師年月日負(fù)責(zé)教師年月日學(xué)生簽字年月日沈陽航空航天大學(xué)課程設(shè)計成績評定單課程名稱最優(yōu)化理論與算法課程設(shè)計院(系)理學(xué)院專業(yè)信息與計算科學(xué)課程設(shè)計題目共軛梯度法算法分析與實現(xiàn)學(xué)號姓名黃中武指導(dǎo)教師評語:課程設(shè)計成績指導(dǎo)教師簽字年月日最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙目錄目錄一、正文...............................................................1二、總結(jié)...............................................................8參考文獻(xiàn)...............................................................9附錄.................................................................10第I頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙正文一、正文一無約束最優(yōu)化問題的共軛梯度法共軛梯度法最初是由Hesteness和Stiefel于1952年為求解線形方程組而提出的。后來,人們把這種方法用于求解無約束最優(yōu)化問題,使之成為一種重要的最優(yōu)化方法。下面,重點介紹Fletcher-Reeves共軛梯度法,簡稱FR法。共軛梯度法的基本思想是把共軛性與最速下降法相結(jié)合,利用已知點處的梯度構(gòu)造一組共軛方向,并沿這組方向進(jìn)行搜索,求出目標(biāo)函數(shù)的極小點。根據(jù)共軛梯度方向的基本性質(zhì),這種方法具有二次終止性。首先討論對于二次函數(shù)的共軛梯度法,然后再把這種方法推廣到極小化一般函數(shù)的情形?？紤]問題TTmifx(),,,0.5xAxbxcn其中A是對稱正定矩陣,c是常數(shù)。具體求解方法如下:(1)首先,任意給定一個初始點,計算出目變函數(shù)在這點的梯度,fx()xg若=0,則停止計算,否則,令1(1)(1)dfxg,,,,,()1(1)(2)(2),0沿方向搜索,得到點,計算在處的梯度,若g,則利用dxx2(1)(2)(2)和構(gòu)造第二個搜索方向,再沿搜索。,gddd2()k()k()k()k一般地,若已知點和搜索方向,則從出發(fā),沿進(jìn)行xdxd搜索,得到(1)()()kkk,xxd,,,k其中步長滿足,k()()kk()()kkfxd(),,,fxd(),,mink此時可求出的顯式表示。令,k()()kk,,,()(),,fxd,,()求得極小點,令'(1)()kTk,,,()()0,,,fxd第1頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙正文根據(jù)二次函數(shù)的梯度表示式,即(1)()kTk,()0Axbd,,T()()kkkAxdbd(+)0,,,,,kT()()kk(10.3.16)gAdd,,,0,,()kk由(10.3.16)式得到Tk()gd()()kTkk(10.3.17),,,dAdk(1)k,計算在處的梯度,若,則停止計算;否則,用fx()g,0x,gk,1k,1()k(1)k,(1)k,()k和構(gòu)造下一個搜索方向,并使和關(guān)于A共軛。按此設(shè)dddd想,令(1)()kk,dgd,,,,(10.3.18)kk,1()kT上式兩端左乘,并令dA()(1)()()()kTkkTkTk,dAddAgdAd,,,,,0kk,1由此得到()kT()()kTk,,dAg(10.3.19)dAd,kk1(1)k,(1)k,再從出發(fā),沿方向搜索xd綜上分析,在第一個搜索方向取負(fù)梯度的前提下,重復(fù)使用公式(10.3.14),(10.3.17),(10.3.18)和(10.3.19),就能伴隨計算點的增加,構(gòu)造出一組搜索方向。第2頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙正文二程序流程圖開始輸入初始點x0精度e繼續(xù)迭代滿足精度要N求Y輸出迭代結(jié)果結(jié)束圖一共軛梯度法程序流程圖三共軛梯度法的MATLAB程序function[x,val,k]=frcg(fun,gfun,x0)maxk=5000;rho=0.6;sigma=0.4;k=0;epsilon=1e-7;n=length(x0);while(k<maxk)g=feval(gfun,x0);第3頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙正文itern=k-(n+1)*floor(k/(n+1));itern=itern+1;if(itern==1)d=-g;elsebeta=(g'*g)/(g0'*g0);d=-g+beta*d0;gd=g'*d;if(gd>=0)d=-g;endendif(norm(g)<epsilon)break;endm=0;mk=0;while(m<20)if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d)mk=m;break;endm=m+1;endx0=x0+rho^mk*d;val=feval(fun,x0);g0=g;d0=d;k=k+1;end第4頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙正文x=x0;val=feval(fun,x);functionf=fun(x)f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;functiong=gfun(x)g=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1),-200*(x(1)^2-x(2))]'四利用所編程序求解實際問題222mifxxxx()100*()(1),,,,例n121**Txfx,,(1,1),()0該問題有精確解利用所編程序求解此問題,在命令窗口輸入:運行結(jié)果為:第5頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙正文五程序注釋function[x,val,k]=frcg(fun,gfun,x0)%用FR共軛梯度法求解無約束問題:minf(x)%輸入:x0時初始點,fun,gfun分別是目標(biāo)函數(shù)和梯度%輸出:x,val分別是近似最優(yōu)點和最優(yōu)值,k是迭代次數(shù)。maxk=5000;%最大迭代次數(shù)rho=0.6;sigma=0.4;k=0;epsilon=1e-7;n=length(x0);while(k<maxk)g=feval(gfun,x0);%計算梯度itern=k-(n+1)*floor(k/(n+1));itern=itern+1;%計算搜索方向if(itern==1)d=-g;elsebeta=(g'*g)/(g0'*g0);d=-g+beta*d0;gd=g'*d;if(gd>=0)d=-g;endendif(norm(g)<epsilon)%檢驗終止條件break;endm=0;mk=0;while(m<20)第6頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙正文if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d)mk=m;break;endm=m+1;endx0=x0+rho^mk*d;val=feval(fun,x0);g0=g;d0=d;k=k+1;endx=x0;val=feval(fun,x);functionf=fun(x)f=100*(x(1)^2-x(2))^2+(x(1)-1)^2;%需要求解的函數(shù)functiong=gfun(x)g=[400*x(1)*(x(1)^2-x(2))+2*(x(1)-1),-200*(x(1)^2-x(2))]'%梯度第7頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙正文二、總結(jié)不知不覺,一個學(xué)期就這樣過去了,隨著期末尾聲的到來,《最優(yōu)化》這門課也已經(jīng)結(jié)課了,接著而來的是為期兩個星期的課程設(shè)計。作為信息與計算科學(xué)系的一員,我們在課堂上接觸最多的就是理論部分,剛好課程設(shè)計能夠給我們驗證理論,聯(lián)系實際的機會,因此,這次課程設(shè)計,我一直都在認(rèn)真完成。在拿到自己的課程設(shè)計題目的時候,我對它進(jìn)行了一定時間的審題,題目中要求我用共軛梯度法求解無約束優(yōu)化問題,因此我拿到課本,仔細(xì)地看了共軛梯度法的原理與例題求解,以便幫助我更好的理解共軛梯度法的應(yīng)用。我記得,再一次研究生面試中,有的老師問過考生:你在你的大學(xué)生涯中學(xué)到了什么,如果讓我回答,我會說:我學(xué)到了一種發(fā)現(xiàn)問題與解決問題的方法,這種方法是在我的學(xué)習(xí)中慢慢形成的一種潛移默化的思想,關(guān)于學(xué)到的內(nèi)容,我們不會一直保留太清晰的記憶,也不會在以后的生活中用到太多,就像買菜不會用到微積分,不會求導(dǎo),可是,數(shù)學(xué)方法和思想給我們思考問題所帶來的方法論卻是大有裨益。這次課程設(shè)計,我發(fā)現(xiàn)我的很多不足,比如在MATLAB上的應(yīng)用上,我還不熟練,這與我在平時的練習(xí)中沒有加以重視有關(guān),而且在《最優(yōu)化》的很多知識點上,自己還沒有很好地掌握。最后,我要感謝我們的任課教師王吉波老師,感謝她在給我們上課中的帶來的幽默感和知識的傳授。在此,祝愿老師身體健康,工作順利。完稿日期:年6月21日第8頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙參考文獻(xiàn)參考文獻(xiàn)[1]陳寶林.《最優(yōu)化理論與算法》[M].北京,清華大學(xué)出版社,.[2]劉衛(wèi)國.《MATLAB程序設(shè)計教程》[M].北京,中國水利水電出版社,.[3]馬昌鳳.《最優(yōu)化方法及其MATLAB程序設(shè)計》[M].北京,科學(xué)出版社,.第9頁最優(yōu)化方法課程設(shè)計沈陽航空航天大學(xué)課程設(shè)計用紙附錄附錄源程序:function[x,val,k]=frcg(fun,gfun,x0)maxk=5000;rho=0.6;sigma=0.4;k=0;epsilon=1e-7;n=length(x0);while(k<maxk)g=feval(gfun,x0);itern=k-(n+1)*floor(k/(n+1));itern=itern+1;if(itern==1)d=-g;elsebeta=(g'*g)/(g0'*g0);d=-g+beta*d0;gd=g'*d;if(gd>=0)d=-g;endendif(norm(g)<epsilon)break;endm=0;mk=0;while(m<20)if(feval(fun,x0+rho^m*d)<feval(fun,x0)+sigma*rho^m*g'*d)第10頁