1、最優化課程設計-共軛梯度法算法分析與實現（設計程序）題目共軛梯度法算法分析與實現班級/學號14140101/2011041401011學 生姓名 黃中武 指導 教師王吉波王微微課程設計任務書課 程名稱 最優化方法課程設計 院（系）理學院 專業 信息與計算科學 課程設計題目 共軛梯度法算法分析與實現 課程設計時間：2014年6月16日至2014年6月27日課程設計的要求及內容：要求1.學習態度要認真，要積極參與課程設計，鍛煉獨立思考能力；2.嚴格遵守上機時間安排；3. 按照MATLAB®程訓練的任務要求來編寫程序；4. 根據任務書來完成課程設計論文；5. 報告書寫格式要求按照沈陽航空航

2、天大學“課程設計報告撰寫規范”；6.報告上交時間：課程設計結束時上交報告；7.嚴禁抄襲行為，一旦發現，課程設計成績為不及格。一、運用共軛梯度法求解無約束最優化問題要求：1） 了解求解無約束最優化問題的共軛梯度法；2）繪出程序流程圖；3）編寫求解無約束最優化問題的共軛梯度法 MATLAB?序；4）利用編寫文件求解某無約束最優化問題；5）給出程序注釋。指導教師年 月曰負責教師年 月曰學生簽字年 月曰沈陽航空航天大學課程設計成績評定單課 程名稱 最優化理論與算法課程設計 院（系）理學院 專業 信息與計算科 學 課程設計題目 共軛梯度法算法分析與實現 學號2011041401011姓名 黃中武 指導教

3、師評語：課程設計成績指導教師簽字年 月曰最優化方法課程設計沈陽航空航天大學課程設計用紙目錄目錄一、正文1二、總結8參考文獻9附錄10第I頁最優化方法課程設計沈陽航空航天大學課程設計用紙正文一、正文一無約束最優化問題的共軛梯度法共軛梯度法最初是由Hesteness和Stiefel于1952年為求解線形方程組而提 出的。后來，人們把這種方法用于求解無約束最優化問題，使之成為一種重要的最 優化方法。下面，重點介紹Fletcher-Reeves共軛梯度法，簡稱FR法。共軛梯度法的基本思想是把共軛性與最速下降法相結合，利用已知點處的梯度 構造一組共軛方向，并沿這組方向進行搜索，求出目標函數的極小點。根據

4、共軛梯 度方向的基本性質，這種方法具有二次終止性。首先討論對于二次函數的共軛梯度 法，然后再把這種方法推廣到極小化一般函數的情形。考慮問題TTmi fx(),， ， 0.5xAxbxcn其中A是對稱正定矩陣，c是常數。具體求解方法如下： 首先，任意給定一個初始點，計算出目變函數在這點的梯度，fx()xg若=0,則停止計算，否則，令1(1)(1)dfxg,() 1(1)(2)(2),0沿方向搜索，得到點，計算在處的梯度，若g，貝閑用dxx2(1) (2)(2)和構造第二個搜索方向，再沿搜索。,gddd2()k()k()k()k一般地，若已知點和搜索方向，貝以出發，沿進行 xdxd搜索,得到(1)

5、()()kkk，xxd,，, k其中步長滿足,k()()kk()()kkfxd()，,fxd()，,min k此時可求出的顯式表達。令,k()()kk,()(),，fxd,()求得極小點，令'(1)()kTk, ,()()O,fxd第1頁最優化方法課程設計沈陽航空航天大學課程設計用紙正文根據二次函數 的梯度表達式，即(1)()kTk ，()OAxbd，,T()()kkk Axdbd(+)O, ，,kT()()kk (10.3.16) gAdd ，,0,()kk由(10.3.16)式得到Tk()gd()()kTkk (10.3.17) ,dAdk(1)k，計算在處的梯度，若，則停止計算；

6、否則，用fx()g,0x,gk ，1k，1()k(1)k ，(1)k，()k和構造下一個搜索方向，并使和關于 A共軛。按此設 dddd想，令(1)()kk ，dgd,，, (10.3.18) kk ，1()kT上式兩端左乘，并令dA()(1)()()()kTkkTkTk，dAddAgdAd,，,0 kk ，1由此得到()kT()()kTk,dAg (10.3.19) dAd ，kk1(1)k，(1)k，再從出發，沿方向搜索xd綜上分析，在第一個搜索方向取負梯度的前提下，重復使用公式 (10.3.14)， (10.3.17) ，(10.3.18)和(10.3.19)，就能伴隨計算點的增加，構造出

7、一組搜索方 向。第2頁最優化方法課程設計 沈陽航空航天大學 課程設計用紙正文二程序流程圖開始輸入初始點X0精度e繼續迭代滿足精度要N求Y輸出迭代結果結束圖一共軛梯度法程序流程圖三共軛梯度法的MATLAB?序function x,val,k=frcg(fun,gfun,xO)maxk=5000;rho=0.6;sigma=0.4;k=0;epsil on=1e-7;n=len gth(x0);while (kvmaxk)g=feval(gfu n, x0);第3頁最優化方法課程設計沈陽航空航天大學課程設計用紙正文itern=k-( n+1)*floor(k/( n+1);itern=iterin

8、+1;if(itern=1)d=-g;elsebeta=(g'*g)/(gO'*gO);d=-g+beta*dO;gd=g'*d;if(gd>=0)d=-g;endendif (n orm(g)<epsilo n)break;endm=0;mk=0;while (m<20)if(feval(fu n,x0+rh°Am*d)vfeval(fu n,x0)+sigma*rh°Am*g'*d)mk=m;break;endm=m+1;endx0=x0+rhoAmk*d;val=feval(f un, x0);g0=g;dO=d;k=

9、k+1;end第4頁最優化方法課程設計沈陽航空航天大學課程設計用紙正文x=xO;val=feval(f un, x);fun cti on f=fun(x)f=100*(x(1)A2-x(2)A2+(x(1)-1)A2;fun cti on g=gf un(x)g=400*x(1)*(x(1)A2-x (2)+2*(x(1)-1),-200*(x(1F2-x (2)'四利用所編程序求解實際問題222mifxxxx()100*()(1),，,例 n 121*Txfx,(1,1),()0該問題有精確解利用所編程序求解此問題，在命令窗口輸入：» ±0= -1.2 lY I

10、je, valj k=frcs (J fuif / e'fun" jxO)運行結果為：L 0000L 0000val =6.7224e-0!7k -8&第5頁最優化方法課程設計 沈陽航空航天大學 課程設計用紙正文五程序注釋function x,val,k=frcg(fun,gfun,xO)%用FR共軛梯度法求解無約束問題:min f(x) % 輸入:x0時初始點，fun， gfun 分別是目標函數和梯度 輸出:x，val分別是近似最優點和最優值，k是迭代次 數。maxk=5000;%最大迭代次數rho=0.6;sigma=0.4;k=0;epsil on=1e-7;n

11、=len gth(x0);while (kvmaxk)g=feval(gfu n, x0);%計算梯度itern=k-( n+1)*floor(k/( n+1);itern=itern+1;% 計算搜索方向if(itern=1)d=-g;elsebeta=(g'*g)/(gO'*gO);d=-g+beta*dO;gd=g'*d;if(gd>=0)d=-g;endendif (n orm(g)<epsilo n)%檢驗終止條件break;endm=0;mk=0;while (m<20)第6頁最優化方法課程設計沈陽航空航天大學課程設計用紙正文if(feva

12、l(fu n,x0+rhoAm*d)<feval(fu n,x0)+sigma*rhoAm*g'*d)mk=m;break;endm=m+1;endx0=x0+rhoAmk*d;val=feval(f un, xO);go=g;dO=d;k=k+1;endx=xO;val=feval(f un, x);fun cti on f=fun(x)f=100*(x(1)A2-x(2)A2+(x(1)-1F2;%需要求解的函數fun cti on g=gf un(x)g=400*x(1)*(x(1F2-x (2) )+2*(x(1)-1),-200*(x(1)A2-x(2)'%梯度

13、第7頁最優化方法課程設計沈陽航空航天大學課程設計用紙正文二、總結不知不覺，一個學期就這樣過去了，隨著期末尾聲的到來，最優化這門課也已經結課了，接著而來的是為期兩個星期的課程設計。作為信息與計算科學系的一員，我們在課堂上接觸最多的就是理論部分，剛好課程設計可以給我們驗證理論，聯系實際的機會，所以，這次課程設計，我一直都 在認真完成。在拿到自己的課程設計題目的時候，我對它進行了一定時間的審題， 題目中要求我用共軛梯度法求解無約束優化問題，所以我拿到課本，仔細地看了共軛梯度法的原理與例題求解，以便幫助我更好的理解共軛梯度法的應用。我記得，再一次研究生面試中，有的老師問過考生 ：你在你的大學生涯中學到

14、了什么，如果讓我回答，我會說：我學到了一種發現問題與解決問題的方法，這種方 法是在我的學習中慢慢形成的一種潛移默化的思想，關于學到的內容，我們不會一 直保留太清晰的記憶，也不會在以后的生活中用到太多，就像買菜不會用到微積 分，不會求導，但是，數學方法和思想給我們思考問題所帶來的方法論卻是大有裨 益。這次課程設計，我發現我的很多不足，比如在MATLA上的應用上，我還不熟練，這與我在平時的練習中沒有加以重視有關，而且在最優化的很多知識點 上，自己還沒有很好地掌握。最后，我要感謝我們的任課教師王吉波老師，感謝他在給我們上課中的帶來 的幽默感和知識的傳授。在此，祝愿老師身體健康，工作順利。完稿日期：2

15、014年6月21日第8頁最優化方法課程設計沈陽航空航天大學課程設計用紙參考文獻參考文獻1陳寶林最優化理論與算法M.北京,清華大學出版社，2013. 2 劉 衛國.MATLABg序設計教程M.北京，中國水利水電出版社,2010. 3 馬昌鳳.最優化方法及其MATLAB?序設計M.北京,科學出版社,2010.第9頁最優化方法課程設計沈陽航空航天大學課程設計用紙附錄附錄源程序：function x,val,k=frcg(fun,gfun,x0)maxk=5000;rho=0.6;sigma=0.4;k=0;epsilo n=1e-7;n=len gth(xO);while (kvmaxk)g=feval(gfu n, xO);itern=k-( n+1)*floor(k/( n+1);itern=iterin+1;if(itern=1)d=-g;elsebeta=(g'*g)/(gO'*gO);d=-g+beta*dO;gd=g'*d;if(gd>=O)d=-g;endendif (n orm(g)<epsilo n)break;endm=O;mk=O;while (m<2O)if(feval(fu n,xO+rh°Am*d)vfeval(fu n,xO)+sigma*rh°Am*g'*d)第10頁最優化方法課