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

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