最優(yōu)化課程設計

1、四川理工學院最優(yōu)化方法課程設計報告共軛梯度算法研究學 生：張偉 程進 朱春林 蔡國寶專 業(yè)：信息與計算科學班 級：2008級2班指導教師：蘭 恒 友四川理工學院理學院二零一一年十二月四川理工學院理學院課程設計任務書專業(yè)： 信息與計算科學 班級： 信計2008X 課程名稱： 最優(yōu)化方法課程設計 學生姓名： 張偉 程進 朱春林 蔡國寶 發(fā)題時間： 2011 年 12 月 18 日一、 課題名稱共軛梯度算法研究二、 課題條件1. 參考文獻：1 孫文瑜等, 最優(yōu)化方法(第二版M，北京:高等教育出版社,2010.2 王紅梅.算法設計與分析M.北京:清華大學出版社,2006.2. 安排10學時（18周五

2、8:00-11:45 13:30-17:15）上機（信計20081 N1S-229, 信計20082 N1S-231），指導老師到場指導網(wǎng)上和圖書館檢索文獻。三、 設計任務理解鞏固課程理論教學的知識，培養(yǎng)學生的實踐動手能力。具體任務：掌握共軛梯度法的思路及迭代過程；用共軛梯度法求，自定初始點，四、 設計說明書（或論文）內(nèi)容摘要、問題描述、具體理論知識點、具體實例、程序清單、程序實現(xiàn)、參考文獻、總結、小組成員分工合作清單。五、 進度計劃（列出完成項目設計內(nèi)容、繪圖等具體起始日期）12月19-25日圖書館或網(wǎng)絡查資料，12月26-29日，根據(jù)資料整理出基礎理論與實例；12月30日上機10學時，編程

3、并上機實現(xiàn)；12月31日完成報告并上繳電子文檔。指導教師（簽名）：年 月 日教研室主任（簽名）：年 月 日共軛梯度算法研究摘 要共軛梯度法是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導數(shù)信息，但客服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點。共軛梯度法不僅是解大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化問題最有效的算法之一。在各種優(yōu)化算法中，共軛梯度法是非常重要的一種。其優(yōu)點是所需存儲量小，具有步收斂性，穩(wěn)定性高，而且不需要任何外來參數(shù)。共軛梯度法最早是由Hestenes和Stiefle（1952）提出來的，用于解正定系數(shù)矩陣的線性方程

4、組，在這個基礎上，F(xiàn)letcher和Reeves （1964）首先提出了解非線性最優(yōu)化問題的共軛梯度法。由于共軛梯度法不需要矩陣存儲，且有較快的收斂速度和二次終止性等優(yōu)點，現(xiàn)在共軛梯度法已經(jīng)廣泛地應用于實際問題中。共軛梯度法是一個典型的共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向d僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便。關鍵詞：共軛梯度法 線性搜索 正定二次函數(shù) 最優(yōu)解目 錄一、問題提出 1二、設計思路和步驟 2三、程序設計 33.1問題分析 33.2 算法設計 33.3 算法框圖 33.4 程序編制 3四、結果分析 44.1設計結果 44.2 進

5、一步討論和驗證 4五、收獲和總結 5六、結束語 66.1設計的優(yōu)缺點 66.2設計工作展望 6參考文獻 7附 錄 8一、問題提出共軛梯度法是一個典型的共軛方向法。它的每一個搜索方向是互相共軛的。而這些搜索方向僅僅是負梯度方向與上一次迭代的搜索方向的組合。因此，存儲量少，計算方便。記 左乘（Hestenes-Stiefel公式） 利用和，上式也可以寫成另外三個常用的公式為 對于正定二次函數(shù)，若采用精確線性搜索，以上幾個關于幾個的共軛梯度公式等價。在實際計算中，F(xiàn)R公式和PRP公式最常用。二、設計思路和步驟2.1設計思路注意到對于正定二次函數(shù)， （）其中是方程組的殘量，以及2.2設計步驟共軛梯度法

6、步驟一：初始步： 給出令。步驟二：如果|<=，停止。步驟三：計算 步驟四：令k:=k+1，轉步驟二。三、程序設計3.1問題分析3.2 算法設計3.3 算法框圖掌握共軛梯度法的思路及迭代過程；用共軛梯度法求，自定初始點，3.4 程序編制function f=conjugate_grad_2d(x0,t%input this:conjugate_grad_2d(2,2,0.01x=x0;syms xi yi af=2*xi2+yi2-xi*yi;fx=diff(f,xi;fy=diff(f,yi;fx=subs(fx,xi,yi,x0;fy=subs(fy,xi,yi,x0;fi=fx,fy

7、;count=0;while double(sqrt(fx2+fy2>ts=-fi;if count<=0s=-fi;elses=s1;endx=x+a*s;f=subs(f,xi,yi,x;f1=diff(f;f1=solve(f1;if f1=0ai=double(f1;elsebreakx,f=subs(f,xi,yi,x,count;endx=subs(x,a,ai;f=3/2*xi2+1/2*yi2-2*xi-xi*yi;fxi=diff(f,xi;fyi=diff(f,yi;fxi=subs(fxi,xi,yi,x;fyi=subs(fyi,xi,yi,x;fii=fxi,fyi;d=(fxi2+fyi2/(fx2+fy2;s1=-fii+d*s;count=count+1;fx=fxi;fy=fyi;endx,f=subs(f,xi,yi,x,count 四、結果分析4.1設計結果（可用文字描述和貼圖等方式表現(xiàn)設計結果）4.2 進一步討論和驗證（比如：設計的改進、推廣等）五