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

1、最優(yōu)化課程設計-共軛梯度法算法分析與實現(xiàn)(設計程序) 題目 共軛梯度法算法分析與實現(xiàn) 班級 / 學號 14140101/2011041401011 學 生 姓 名 黃中武 指 導 教 師 王吉波 王微微 課 程 設 計 任 務 書 課 程 名 稱 最優(yōu)化方法課程設計 院(系) 理學院 專業(yè) 信息與計算科學 課程設計題目 共軛梯度法算法分析與實現(xiàn) 課程設計時間: 2014 年 6月 16日至 2014 年 6月 27日 課程設計的要求及內容: 要求 1. 學習態(tài)度要認真，要積極參與課程設計，鍛煉獨立思考能力; 2. 嚴格遵守上機時間安排; 3. 按照MATLAB編程訓練的任務要求來編寫程序; 4

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

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

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

5、,0沿方向搜索，得到點，計算在處的梯度，若g，則利用dxx2(1)(2)(2)和構造第二個搜索方向，再沿搜索。 ,gddd2()k()k()k()k一般地，若已知點和搜索方向，則從出發(fā)，沿進行xdxd搜索，得到 (1)()()kkk，xxd,，, k其中步長滿足 ,k()()kk()()kkfxd()，,fxd()，,min k此時可求出的顯式表達。令 ,k()()kk,()(),，fxd ,()求得極小點，令 '(1)()kTk，,()()0,fxd 第 1 頁 最優(yōu)化方法課程設計 沈陽航空航天大學 課程設計用紙 正 文 根據(jù)二次函數(shù)的梯度表達式，即 (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，計算在處的梯度，若，則停止計算;否則，用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

7、) dAd，kk1(1)k，(1)k，再從出發(fā)，沿方向搜索 xd綜上分析，在第一個搜索方向取負梯度的前提下，重復使用公式(10.3.14)，(10.3.17)，(10.3.18)和(10.3.19)，就能伴隨計算點的增加，構造出一組搜索方向。 第 2 頁 最優(yōu)化方法課程設計 沈陽航空航天大學 課程設計用紙 正 文 二 程序流程圖 開始 輸入初始點x0 精度e 繼續(xù)迭代 滿足精度要 N 求 Y 輸出迭代結果 結束 圖一 共軛梯度法程序流程圖 三 共軛梯度法的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)化方法課程設計 沈陽航空航天大學 課程設計用紙 正 文 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)化方法課程設計 沈陽航空航天大學 課程設計用紙 正 文 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)' 四 利用所編程序求解實際問題 222mifxxxx()100*()(1),，,例 n121*Txfx,(1,1),()0該問題有精確解 利用所編程序求解此問題，在命令窗口輸入: 運行結果為: 第 5 頁 最優(yōu)化方法課程設計 沈陽航空航天大學 課程設計用紙 正 文 五 程序注釋 function x,val,k=frcg(fun,gfun,x0) %用FR共軛梯度法求解無約束問題:min f(x) %輸入:x0時初始點，fun，gfun分別是目標函數(shù)和梯度 %輸出:x，val分別是近似最優(yōu)點和

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);%計算梯度 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)<epsil

12、on)%檢驗終止條件 break; end m=0; mk=0; while (m<20) 第 6 頁 最優(yōu)化方法課程設計 沈陽航空航天大學 課程設計用紙 正 文 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)化方法課程設計 沈陽航空航天大學 課程設計用紙 正 文 二、總結 不知不覺，一個學期就這樣過去了，隨著期末尾聲的到來，最優(yōu)化這門課也已經(jīng)結課了，接著而來的是為期兩個星期的課程設計。 作為信息與計算科學系的一員，我們在課堂上接觸最多的就是理論部分，剛好課程設計可以給我們驗證理論，聯(lián)系實際的機會，所以，這次課程設計，我一直都在認真完成。在拿到自己的課程設計題目的時候，我對它進行了一定時間的審題，題目中要

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

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

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)化方法課程設計