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

1、最優(yōu)化課程設(shè)計(jì)-共軛梯度法算法分析與實(shí)現(xiàn)(設(shè)計(jì)程序) 題目 共軛梯度法算法分析與實(shí)現(xiàn) 班級(jí) / 學(xué)號(hào) 14140101/2011041401011 學(xué) 生 姓 名 黃中武 指 導(dǎo) 教 師 王吉波 王微微 課 程 設(shè) 計(jì) 任 務(wù) 書 課 程 名 稱 最優(yōu)化方法課程設(shè)計(jì) 院(系) 理學(xué)院 專業(yè) 信息與計(jì)算科學(xué) 課程設(shè)計(jì)題目 共軛梯度法算法分析與實(shí)現(xiàn) 課程設(shè)計(jì)時(shí)間: 2014 年 6月 16日至 2014 年 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ù)要求來編寫程序; 4

2、. 根據(jù)任務(wù)書來完成課程設(shè)計(jì)論文; 5. 報(bào)告書寫格式要求按照沈陽航空航天大學(xué)“課程設(shè)計(jì)報(bào)告撰寫規(guī)范”; 6. 報(bào)告上交時(shí)間:課程設(shè)計(jì)結(jié)束時(shí)上交報(bào)告; 7. 嚴(yán)禁抄襲行為，一旦發(fā)現(xiàn)，課程設(shè)計(jì)成績(jī)?yōu)椴患案瘛?一、 運(yùn)用共軛梯度法求解無約束最優(yōu)化問題 要求:1)了解求解無約束最優(yōu)化問題的共軛梯度法; 2)繪出程序流程圖; 3)編寫求解無約束最優(yōu)化問題的共軛梯度法MATLAB程序; 4)利用編寫文件求解某無約束最優(yōu)化問題; 5)給出程序注釋。 指導(dǎo)教師 年 月 日 負(fù)責(zé)教師 年 月 日 學(xué)生簽字 年 月 日 沈陽航空航天大學(xué) 課 程 設(shè) 計(jì) 成 績(jī) 評(píng) 定 單 課 程 名 稱 最優(yōu)化理論與算法課程設(shè)

3、計(jì) 院(系) 理學(xué)院 專業(yè) 信息與計(jì)算科學(xué) 課程設(shè)計(jì)題目 共軛梯度法算法分析與實(shí)現(xiàn) 學(xué)號(hào) 2011041401011 姓名 黃中武 指導(dǎo)教師評(píng)語: 課程設(shè)計(jì)成績(jī) 指導(dǎo)教師簽字 年 月 日 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 目 錄 目 錄 一、正文 . 1 二、總結(jié) . 8 參考文獻(xiàn) . 9 附 錄 . 10 第 I 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文 一、正文 一 無約束最優(yōu)化問題的共軛梯度法 共軛梯度法最初是由Hesteness和Stiefel于1952年為求解線形方程組而提出的。后來，人們把這種方法用于求解無約束最優(yōu)化問題，使之成為一種重要的最

4、優(yōu)化方法。 下面，重點(diǎn)介紹Fletcher-Reeves共軛梯度法，簡(jiǎn)稱FR法。 共軛梯度法的基本思想是把共軛性與最速下降法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極小點(diǎn)。根據(jù)共軛梯度方向的基本性質(zhì)，這種方法具有二次終止性。首先討論對(duì)于二次函數(shù)的共軛梯度法，然后再把這種方法推廣到極小化一般函數(shù)的情形?？紤]問題 TTmi fx(),，0.5xAxbxcn其中A是對(duì)稱正定矩陣，c是常數(shù)。 具體求解方法如下: (1)首先，任意給定一個(gè)初始點(diǎn)，計(jì)算出目變函數(shù)在這點(diǎn)的梯度，fx()xg若=0，則停止計(jì)算，否則，令 1(1)(1)dfxg,() 1(1)(2)(2)

5、,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)滿足 ,k()()kk()()kkfxd()，,fxd()，,min k此時(shí)可求出的顯式表達(dá)。令 ,k()()kk,()(),，fxd ,()求得極小點(diǎn)，令 '(1)()kTk，,()()0,fxd 第 1 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文 根據(jù)二次函數(shù)的梯度表達(dá)式，即 (1)()kTk， ()0Axb

6、d，, T()()kkk Axdbd(+)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,，,0 kk，1由此得到 ()kT()()kTk,dAg (10.3.19

7、) dAd，kk1(1)k，(1)k，再從出發(fā)，沿方向搜索 xd綜上分析，在第一個(gè)搜索方向取負(fù)梯度的前提下，重復(fù)使用公式(10.3.14)，(10.3.17)，(10.3.18)和(10.3.19)，就能伴隨計(jì)算點(diǎn)的增加，構(gòu)造出一組搜索方向。 第 2 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文 二 程序流程圖 開始 輸入初始點(diǎn)x0 精度e 繼續(xù)迭代 滿足精度要 N 求 Y 輸出迭代結(jié)果 結(jié)束 圖一 共軛梯度法程序流程圖 三 共軛梯度法的MATLAB程序 function x,val,k=frcg(fun,gfun,x0) maxk=5000; rho=0.6;sigma=0

8、.4; k=0;epsilon=1e-7; n=length(x0); while (k<maxk) g=feval(gfun,x0); 第 3 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文 itern=k-(n+1)*floor(k/(n+1); itern=itern+1; if(itern=1) d=-g; else beta=(g'*g)/(g0'*g0); d=-g+beta*d0; gd=g'*d; if(gd>=0) d=-g; end end if (norm(g)<epsilon) break; end m=0; m

9、k=0; while (m<20) if (feval(fun,x0+rhom*d)<feval(fun,x0)+sigma*rhom*g'*d) mk=m; break; end m=m+1; end x0=x0+rhomk*d; val=feval(fun,x0); g0=g; d0=d; k=k+1; end 第 4 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文 x=x0; val=feval(fun,x); function f=fun(x) f=100*(x(1)2-x(2)2+(x(1)-1)2; function g=gfun(x) g=40

10、0*x(1)*(x(1)2-x(2)+2*(x(1)-1),-200*(x(1)2-x(2)' 四 利用所編程序求解實(shí)際問題 222mifxxxx()100*()(1),，,例 n121*Txfx,(1,1),()0該問題有精確解 利用所編程序求解此問題，在命令窗口輸入: 運(yùn)行結(jié)果為: 第 5 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文 五 程序注釋 function x,val,k=frcg(fun,gfun,x0) %用FR共軛梯度法求解無約束問題:min f(x) %輸入:x0時(shí)初始點(diǎn)，fun，gfun分別是目標(biāo)函數(shù)和梯度 %輸出:x，val分別是近似最優(yōu)點(diǎn)和

11、最優(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; else beta=(g'*g)/(g0'*g0); d=-g+beta*d0; gd=g'*d; if(gd>=0) d=-g; end end if (norm(g)<epsil

12、on)%檢驗(yàn)終止條件 break; end m=0; mk=0; while (m<20) 第 6 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文 if (feval(fun,x0+rhom*d)<feval(fun,x0)+sigma*rhom*g'*d) mk=m; break; end m=m+1; end x0=x0+rhomk*d; val=feval(fun,x0); g0=g; d0=d; k=k+1; end x=x0; val=feval(fun,x); function f=fun(x) f=100*(x(1)2-x(2)2+(x(1)-

13、1)2;%需要求解的函數(shù) function g=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è)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文 二、總結(jié) 不知不覺，一個(gè)學(xué)期就這樣過去了，隨著期末尾聲的到來，最優(yōu)化這門課也已經(jīng)結(jié)課了，接著而來的是為期兩個(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í)間的審題，題目中要

14、求我用共軛梯度法求解無約束優(yōu)化問題， 所以我拿到課本，仔細(xì)地看了共軛梯度法的原理與例題求解，以便幫助我更好的理解共軛梯度法的應(yīng)用。 我記得，再一次研究生面試中，有的老師問過考生:你在你的大學(xué)生涯中學(xué)到了什么,如果讓我回答，我會(huì)說:我學(xué)到了一種發(fā)現(xiàn)問題與解決問題的方法，這種方法是在我的學(xué)習(xí)中慢慢形成的一種潛移默化的思想，關(guān)于學(xué)到的內(nèi)容，我們不會(huì)一直保留太清晰的記憶，也不會(huì)在以后的生活中用到太多，就像買菜不會(huì)用到微積分，不會(huì)求導(dǎo)，但是，數(shù)學(xué)方法和思想給我們思考問題所帶來的方法論卻是大有裨益。 這次課程設(shè)計(jì)，我發(fā)現(xiàn)我的很多不足，比如在MATLAB上的應(yīng)用上，我還不熟練，這與我在平時(shí)的練習(xí)中沒有加以重

15、視有關(guān)，而且在最優(yōu)化的很多知識(shí)點(diǎn)上，自己還沒有很好地掌握。 最后 ，我要感謝我們的任課教師王吉波老師，感謝他在給我們上課中的帶來的幽默感和知識(shí)的傳授。在此，祝愿老師身體健康，工作順利。 完稿日期: 2014 年 6月 21日第 8 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 參考文獻(xiàn) 參考文獻(xiàn) 1 陳寶林.最優(yōu)化理論與算法M.北京,清華大學(xué)出版社,2013. 2 劉衛(wèi)國.MATLAB程序設(shè)計(jì)教程M.北京,中國水利水電出版社,2010. 3 馬昌鳳.最優(yōu)化方法及其MATLAB程序設(shè)計(jì)M.北京,科學(xué)出版社,2010. 第 9 頁 最優(yōu)化方法課程設(shè)計(jì) 沈陽航空航天大學(xué) 課程設(shè)計(jì)用紙 附

16、錄 附 錄 源程序: 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; else beta=(g'*g)/(g0'*g0); d=-g+beta*d0; gd=g'*d; if(gd>=0) d=-g; end end if (norm(g)<epsilon) break; end m=0; mk=0; while (m<20) if (feval(fun,x0+rhom*d)<feval(fun,x0)+sigma*rhom*g'*d) 第 10 頁 最優(yōu)化方法課程設(shè)計(jì)