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ù)要求來(lái)編寫程序

2、;4. 根據(jù)任務(wù)書來(lái)完成課程設(shè)計(jì)論文 ;5. 報(bào)告書寫格式要求按照沈陽(yáng)航空航天大學(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)用共軛梯度法求解無(wú)約束最優(yōu)化問(wèn)題要求 :1) 了解求解無(wú)約束最優(yōu)化問(wèn)題的共軛梯度法 ; 2) 繪出程序流程圖 ;3) 編寫求解無(wú)約束最優(yōu)化問(wèn)題的共軛梯度法 MATLAB程序 ;4) 利用編寫文件求解某無(wú)約束最優(yōu)化問(wèn)題 ;.5) 給出程序注釋。指導(dǎo)教師年 月 日負(fù)責(zé)教師年 月 日學(xué)生簽字年 月 日沈陽(yáng)航空航天大學(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)語(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 年為求解線形方程組而提出的。后來(lái)，人們把這種方法用于求解無(wú)約束最優(yōu)化問(wèn)題，使之成為一種重要的最優(yōu)化方法。下面，重點(diǎn)介紹Fletcher

4、-Reeves共軛梯度法，簡(jiǎn)稱FR法。共軛梯度法的基本思想是把共軛性與最速下降法相結(jié)合，利用已知點(diǎn)處的梯度構(gòu)造一組共軛方向，并沿這組方向進(jìn)行搜索，求出目標(biāo)函數(shù)的極小點(diǎn)。根據(jù)共軛梯度方向的基本性質(zhì)，這種方法具有二次終止性。首先討論對(duì)于二次函數(shù)的共軛梯度法，然后再把這種方法推廣到極小化一般函數(shù)的情形?？紤]問(wèn)題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),0沿方向搜索，得到點(diǎn)，計(jì)算在處的

5、梯度，若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è)最優(yōu)化方法課程設(shè)計(jì)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)用紙正 文 根據(jù)二次函數(shù)的梯度表達(dá)式，即(1)()kTk， ()0Axbd ，,T()()kkk Axdbd(+)0,，,kT(

6、)()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) dAd，kk1(1)k ，

7、(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ì)用紙正 文 二 程序流程圖.開始輸入初始點(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.4;k=0;epsilon=1e-7;n=lengt

8、h(x0);while (k=0)d=-g;endendif (norm(g)epsilon)break;endm=0;mk=0;while (m20)if(feval(fun,x0+rhom*d)feval(fun,x0)+sigma*rhom*g*d)mk=m;break;endm=m+1;endx0=x0+rhomk*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);function f=fun(x)f=100*(x(1)2-x(2)2+(x(1)-1

9、)2;function g=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)題 :min f(x) % 輸入 :x0 時(shí)初始點(diǎn)， fun ，gfun分別是目標(biāo)函數(shù)和梯

10、度 %輸出 :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=0)d=-g;endendif (norm(g)epsilon)%檢驗(yàn)終止條件break;endm=0;mk=0;while (m20)第 6 頁(yè)最優(yōu)化方法課程設(shè)計(jì)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)用紙正 文if(feval(fun,x0+rhom*d)feval(fun,x0)+sigma*rhom*g*d)mk=m;break;endm=m+1;end.x0=x0+rhomk*d;v

11、al=feval(fun,x0);g0=g;d0=d;k=k+1;endx=x0;val=feval(fun,x);function f=fun(x)f=100*(x(1)2-x(2)2+(x(1)-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è)最優(yōu)化方法課程設(shè)計(jì) 沈陽(yáng)航空航天大學(xué) 課程設(shè)計(jì)用紙 正 文二、總結(jié)不知不覺，一個(gè)學(xué)期就這樣過(guò)去了，隨著期末尾聲的到來(lái)，最優(yōu)化這門課也已經(jīng)結(jié)課了，接著而來(lái)的是為期兩個(gè)星期的課程設(shè)計(jì)。作為信息與計(jì)算科學(xué)系的一員，我們?cè)谡n堂上

12、接觸最多的就是理論部分，剛好課程設(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ì)在以后的生活中用到太多，就像買菜不會(huì)用

13、到微積分，不會(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í)的傳授。在此，祝愿老師身體健康，工作順利。完稿日期 : 2014年 6 月 21 日第 8頁(yè)最優(yōu)化方法課程設(shè)計(jì)沈陽(yáng)航空航天大學(xué)課程設(shè)計(jì)用紙參考文獻(xiàn)參考文獻(xiàn)1陳寶林 . 最優(yōu)化理論與算法 M. 北京 , 清華大學(xué)出版社 ,2013. 2劉衛(wèi)國(guó) . MATLAB程序設(shè)計(jì)教程

14、 M. 北京 , 中國(guó)水利水電出版社 ,2010. 3馬昌鳳 .最優(yōu)化方法及其MATLAB程序設(shè)計(jì) M. 北京 , 科學(xué)出版社 ,2010.第 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=0)d=-g;endendif (norm(g)epsilon)break;endm=0;mk=0;while (m20)if(feval(fun,x0+rhom*d)feval(fun,x0)+sigma*rhom*g*d)第 10 頁(yè).最優(yōu)化方法課程設(shè)計(jì)沈陽(yáng)航空航天大學(xué)課程設(shè)