共軛梯度算法的設(shè)計與實現(xiàn)畢業(yè)設(shè)計

1、<p>　　本科畢業(yè)設(shè)計（論文）開題報告</p><p>　　題 目： 共軛梯度算法的設(shè)計與實現(xiàn) </p><p>　　學(xué)生姓名： </p><p>　　院 （系）： 理學(xué)院 </p><p>　　專業(yè)班級：

2、 </p><p>　　指導(dǎo)教師： </p><p>　　完成時間： 2010年 月 日 </p><p>　　共軛梯度算法的設(shè)計與實現(xiàn)</p><p>　　摘要：共軛梯度法是最優(yōu)化方法中一種重要的方法.它是介于最速下降法

3、與牛頓法之間的一個方法，它僅需利用一階導(dǎo)數(shù)信息，克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化問題最有效的算法之一.</p><p>　　近年來，隨著計算機的飛速發(fā)展和實際問題中大規(guī)模優(yōu)化問題的涌現(xiàn)，尋找快速有效的共軛梯度法成為了學(xué)者們研究的熱門方向之一.本文主要研究求解無約束最優(yōu)化問題的共軛梯度法.

4、具體從以下方面著手，介紹所選課題的研究背景、意義和研究現(xiàn)狀；闡述共軛梯度法理論，包括共軛梯度法的一些基本概念，計算公式和迭代步驟；引入一些實際問題，建立共軛梯度算法；根據(jù)已有學(xué)者的研究結(jié)果，分析算法的收斂性；運用MATLAB編程，代入實例中的相關(guān)數(shù)據(jù)得到一些相關(guān)的數(shù)值結(jié)果；最后對數(shù)據(jù)進行分析驗證，判斷該算法的有效性.</p><p>　　關(guān)鍵詞：無約束最優(yōu)化；共軛梯度法；迭代；全局收斂性</p>&

5、lt;p>　　Conjugate Gradient Algorithm Design and Implementation</p><p>　　Abstract：Conjugate gradient method is one of the important optimization methods. It is between the steepest descent method and Newton

6、 method, which only requires the first order derivative. It not only overcomes the shortcomings of slow convergence of steepest descent method, but also avoids the shortcomings of storing and calculating the inverse Hess

7、e matrix of Newton method. The conjugate gradient method is not only one of the most useful methods to solve the large-scale linear equations, but </p><p>　　In recent years, with the rapid development of com

8、puter and the practical issues in the emergence of large-scale optimization problems, looking for quick and efficient conjugate gradient method becomes one of the most popular directions of scholars. This paper mainly di

9、scusses the conjugate gradient method in the unconstrained optimization methods. We focus on the following aspects, describe the background and the significance of the selected research projects; elaborate the theory of

10、conjugate </p><p>　　Key words：Unconstrained optimization；Conjugate gradient method；Iteration；Global convergence</p><p><b>　　目 錄</b></p><p><b>　　第一章 緒論1</b>

11、;</p><p>　　1.1 研究背景和意義1</p><p>　　1.2 共軛梯度法的研究現(xiàn)狀1</p><p>　　1.2.1 理論研究1</p><p>　　1.2.2 應(yīng)用研究3</p><p>　　1.3 本文工作和結(jié)構(gòu)安排4</p><p>　　第二章 共軛梯

12、度法5</p><p>　　2.1 最優(yōu)化方法5</p><p>　　2.2 共軛梯度法理論5</p><p>　　2.2.1 共軛梯度法的概念5</p><p>　　2.2.2 共軛方向及性質(zhì)6</p><p>　　2.2.3 共軛梯度法的公式結(jié)構(gòu)7</p><p>　　

13、2.2.4 共軛梯度法的算法步驟11</p><p>　　2.2.5 共軛梯度法的優(yōu)點11</p><p>　　2.3 算法實例12</p><p>　　第三章 算法的收斂性15</p><p>　　3.1 共軛梯度法的性質(zhì)與收斂性定理15</p><p>　　3.1.1 共軛梯度法的性質(zhì)15&

14、lt;/p><p>　　3.1.2 共軛梯度法的收斂性定理17</p><p>　　3.2 戴彧虹-袁亞湘共軛梯度法19</p><p>　　第四章 算法編程24</p><p>　　4.1 MATLAB的發(fā)展歷程和影響24</p><p>　　4.2 共軛梯度法的MATLAB程序24</p>

15、;<p>　　第五章 結(jié)論30</p><p><b>　　參考文獻31</b></p><p><b>　　致 謝33</b></p><p><b>　　第一章 緒論</b></p><p>　　本章首先闡明了所選課題的研究背景和意義；然后對最優(yōu)化

16、方法下的共軛梯度方法的產(chǎn)生、主要研究內(nèi)容以及國內(nèi)外的研究現(xiàn)狀進行闡述；最后給出了本論文的主要研究工作和結(jié)構(gòu)安排.</p><p>　　1.1 研究背景和意義 </p><p>　　最優(yōu)化方法是近幾十年形成的，它主要運用數(shù)學(xué)方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學(xué)決策的依據(jù).最優(yōu)化方法的目的在于針對所研究的系統(tǒng)，求得一個合理運用人力、物力和財力的最佳方案，發(fā)揮和提高系統(tǒng)的效率

17、及效益，最終達到系統(tǒng)的最優(yōu)目標(biāo).實踐表明，隨著科學(xué)技術(shù)的日益進步和生產(chǎn)經(jīng)營的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學(xué)的重要理論基礎(chǔ)和不可缺少的方法，被人們廣泛地應(yīng)用到公共管理、經(jīng)濟管理、國防等各個領(lǐng)域，發(fā)揮著越來越重要的作用.</p><p>　　最優(yōu)化方法又可分為無約束最優(yōu)化方法和約束最優(yōu)化方法，其中無約束最優(yōu)化方法包括最速下降法，牛頓法，共軛方向法，以及共軛梯度法和變尺度法，約束優(yōu)化方法包括單純形法，解線性規(guī)劃

18、的圖解法，等式約束的罰函數(shù)法，以及Rosen梯度投影法.其中最優(yōu)化方法下的共軛梯度法，具有較快的收斂速度和二次終止性等優(yōu)點，得到許多學(xué)者們的青睞，使得尋找快速有效的共軛梯度法成為了學(xué)者們研究的熱門方向.因此研究所選課題的意義非常重大.</p><p>　　1.2 共軛梯度法的研究現(xiàn)狀</p><p>　　共軛梯度法最早是由Hestenes和Stiefle(1952)提出來的，用于解正定系

19、數(shù)矩陣的線性方程組，在這個基礎(chǔ)上，F(xiàn)letcher和Reeves(1964)首先提出了解非線性最優(yōu)化問題的共軛梯度法.共軛梯度法是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導(dǎo)數(shù)信息，克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一.</p><p>　　共軛梯度法又是一個典型的

20、共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便.由于共軛梯度法不需要矩陣存儲，且有較快的收斂速度和二次終止性等優(yōu)點，現(xiàn)在共軛梯度法已經(jīng)廣泛地應(yīng)用到實際問題中.</p><p>　　1.2.1 理論研究</p><p>　　目前，國內(nèi)外對共軛梯度法的研究已經(jīng)相當(dāng)完善，更有一套幾乎完美的共軛梯度法理論，并且廣泛

21、的應(yīng)用到實際問題中，為其應(yīng)用研究奠定了堅實的基礎(chǔ).在此簡單給出共軛梯度法的一些理論，內(nèi)容主要如下：</p><p>　　1.2.1.1 共軛方向的概念與性質(zhì)   在優(yōu)化方法中，共軛方向有著重要的意義.一些有效的無約束優(yōu)化算法大多是以共軛方向作為搜索方向的.共軛梯度法就是共軛方向法的一種.若要使第二個迭代點成為該正定二元二次函數(shù)的極小點，只要使兩次一維搜索的搜索方向和關(guān)于函數(shù)的二階導(dǎo)數(shù)矩陣

22、為共軛就可以了.</p><p>　　對于一般函數(shù)，共軛方向具有以下性質(zhì)：</p><p>　　(1)若 (＝1，2，…，)是以共軛的個向量，則對于正定二次函數(shù)從任意初始點出發(fā)，依次沿這個方向進行一維搜索，最多次即可達到極小點.</p><p>　　(2)從任意兩個點和出發(fā)，分別沿同一方向進行一維搜索，得到兩個一維極小點和，則連接此兩點構(gòu)成的向量=-，與原方向關(guān)于該

23、函數(shù)的二階導(dǎo)數(shù)矩陣相共軛.</p><p>　　1.2.1.2 共軛梯度法的計算公式  共軛梯度法是在每一迭代步利用當(dāng)前點處的最速下降方向來生成二次函數(shù)的Hesse矩陣的共軛方向，并建立求在上的極小點的方法.根據(jù)這個思想，下面簡單給出共軛梯度法的一些計算公式.</p><p>　　設(shè) ，</p><p>　　其中，為階對

24、稱正定矩陣，為維常量，為實數(shù)，的梯度向量為</p><p><b>　　.</b></p><p>　　詳細求解過程在第二章中給出.于此同時我們還能給出計算步長的算式.</p><p>　　設(shè)是上的一組線性無關(guān)的向量，則從任意指定的出發(fā)，按以下迭代產(chǎn)生的序列：</p><p><b>　?。喝?，，； </

25、b></p><p>　?。河嬎?，??； 計算，得出； </p><p>　　如此進行下去，直到第步； </p><p><b>　?。河嬎悖。?lt;/b></p><p><b>　　計算，得出． </b></p><p><b>　　顯然：</b>

26、</p><p>　　1.2.2 應(yīng)用研究</p><p>　　近年來，隨著模糊理論、神經(jīng)網(wǎng)絡(luò)等智能技術(shù)和計算機技術(shù)的發(fā)展，智能式的優(yōu)化方法越來越受重視.現(xiàn)今，國內(nèi)外主要研究的方法有：</p><p>　　(1)神經(jīng)網(wǎng)絡(luò)優(yōu)化方法</p><p>　　人工神經(jīng)網(wǎng)絡(luò)的研究起源于1943年和Mc Culloch和Pitts的工作.在優(yōu)化方面，19

27、82年Hopfield首先引入Lyapuov能量函數(shù)用于5判斷網(wǎng)絡(luò)的穩(wěn)定性，提出Hopfield單層離散模型；Hopfield和Tank又發(fā)展了Hopfield單層連續(xù)模型.1986年，Hopfield和Tank將電子電路與Hopfield模型直接對應(yīng)，實現(xiàn)了硬件模擬；Kennedy和Chua基于非線性電路理論提出了模擬電路模型，并使用系統(tǒng)微分方程的Lyapuov函數(shù)研究了電子電路的穩(wěn)定性.這些工作都有力地促進了對神經(jīng)網(wǎng)絡(luò)優(yōu)化方法的研究

28、.</p><p><b>　　(2)模糊優(yōu)化方法</b></p><p>　　最優(yōu)化問題一直都是模糊理論應(yīng)用最為廣泛的領(lǐng)域之一.自從Bellman和L.A.zadeh在70年代初期對這一研究作出開創(chuàng)性工作以來，其主要研究集中在一般意義下的理論研究、模糊線性規(guī)劃、多目標(biāo)模糊規(guī)劃、以及模糊規(guī)劃理論在隨機規(guī)劃及許多實際問題中的應(yīng)用.主要的研究方法是利用模糊集的截集或確定模

29、糊集的隸屬函數(shù)將模糊規(guī)劃問題轉(zhuǎn)化為經(jīng)典的規(guī)劃問題來解決. </p><p>　　(3)支持向量機方法</p><p>　　支持向量機是由Vapnik領(lǐng)導(dǎo)的AT&TBell實驗室研究小組在1963年提出的一種新的非常有潛力的分類技術(shù)，SVM是一種基于統(tǒng)計學(xué)習(xí)理論的模式識別方法，主要應(yīng)用于模式識別領(lǐng)域.由于當(dāng)時這些研究尚不十分完善，在解決模式識別問題中往往趨于保守，且數(shù)學(xué)上比較艱澀，這

30、些研究一直沒有得到充分的重視.直到90年代，統(tǒng)計學(xué)習(xí)理論的實現(xiàn)和由于神經(jīng)網(wǎng)絡(luò)等較新興的機器學(xué)習(xí)方法的研究遇到一些重要的困難，比如如何確定網(wǎng)絡(luò)結(jié)構(gòu)的問題、過學(xué)習(xí)與欠學(xué)習(xí)問題、局部極小點問題等，使得SVM迅速發(fā)展和完善，在解決小樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應(yīng)用到函數(shù)擬合等其他機器學(xué)習(xí)問題中.</p><p>　　共軛梯度法在以上的優(yōu)化方法中都得到了應(yīng)用，例如，有學(xué)者就應(yīng)用共軛梯度法

31、對網(wǎng)絡(luò)的權(quán)值和閡值進行優(yōu)化計算，完成神經(jīng)網(wǎng)絡(luò)訓(xùn)練的方法；還有學(xué)者在支持向量機方法中應(yīng)用共軛梯度法，得到了一種更有效的光滑支持向量機方法.</p><p>　　除此之外，共軛梯度法還被應(yīng)用于其他一些優(yōu)化方法，由于本文對應(yīng)用領(lǐng)域不做專門研究，其他應(yīng)用共軛梯度法的優(yōu)化方法不再詳細列舉.</p><p>　　1.3 本文工作和結(jié)構(gòu)安排</p><p>　　本文研究的課題主

32、要圍繞無約束最優(yōu)化方法下的共軛梯度法進行.通過一個具體的實際問題，結(jié)合參考資料已經(jīng)自己所了解的知識，建立一個求解該問題的共軛梯度算法；針對該算法，運用所學(xué)知識和一些學(xué)者的研究結(jié)果，對該算法在指定的搜索方向下的全局收斂性，進行討論分析；基于以上的步驟實現(xiàn)后，通過MATLAB編程，代入實例中的相關(guān)數(shù)據(jù)得到一些相關(guān)的數(shù)值結(jié)果，最后對數(shù)據(jù)進行分析驗證，判斷該算法是否有效.具體內(nèi)容安排如下：</p><p>　　第一章為緒

33、論.首先闡明了所選課題的研究背景和意義；然后介紹了共軛梯度法的研究現(xiàn)狀；最后是全文的內(nèi)容和結(jié)構(gòu)安排.</p><p>　　第二章引入共軛梯度法理論.簡單的介紹最優(yōu)化方法；然后詳細的闡述共軛梯度法，并引入共軛梯度法的一些基本概念，計算公式和迭代步驟；引入一個實際問題，建立共軛梯度算法，為以后各章的研究奠定了基礎(chǔ).</p><p>　　第三章分析算法的全局收斂性.該章主要分兩部分，第一部分先給

34、出共軛梯度法的一些性質(zhì)和收斂性定理；然后第二部分則是分析算法的全局收斂性，通過總結(jié)已有學(xué)者的研究結(jié)果，證明該算法在一定條件下具有全局收斂性.</p><p>　　第四章驗證算法的有效性.也是論文的關(guān)鍵部分，主要思想就是通過MATLAB編程，代入實例中的相關(guān)數(shù)據(jù)得到一些相關(guān)的數(shù)值結(jié)果，最后對數(shù)據(jù)進行分析驗證，判斷該算法是否有效.</p><p>　　最后是結(jié)論.系統(tǒng)的總結(jié)了本文的研究工作，不

35、僅指出了一些有待解決的問題，還展望了共軛梯度法未來的研究方向.</p><p>　　第二章 共軛梯度法</p><p>　　本章先簡單的介紹最優(yōu)化方法；然后詳細的闡述共軛梯度法，并引入共軛梯度法的一些基本概念，迭代公式和迭代步驟；最后引入一個實際問題，建立共軛梯度算法，為以后各章的研究奠定了基礎(chǔ).</p><p>　　2.1 最優(yōu)化方法</p>&

36、lt;p>　　最優(yōu)化方法大體可分為無約束最優(yōu)化方法和約束最優(yōu)化方法，而無約束最優(yōu)化方法就是求元函數(shù)的極值的方法，它包括最速下降法，擬牛頓法，以及共軛梯度法和信賴域方法.其中最速下降法是以負梯度方向作為下降方向的極小化算法，又稱梯度法，是1874年法國科學(xué)家Cauchy提出的，該方法是無約束最優(yōu)化中最簡單的方法；擬牛頓法是目前為止最為行之有效的一種算法，具有收斂速度快、算法穩(wěn)定性強、編寫程序容易等優(yōu)點，在現(xiàn)今的大型計算程序中有著廣泛

37、的應(yīng)用.</p><p>　　我們知道約束優(yōu)化問題是在自變量滿足約束條件的情況下目標(biāo)函數(shù)最小化的問題，其中約束條件既可以是等式約束也可以是不等式約束,而約束最優(yōu)化方法就是用來求解這一類問題的方法，它包括單純形法，解線性規(guī)劃的圖解法，等式約束的罰函數(shù)法，以及Rosen梯度投影法.其中單純形法是由美國數(shù)學(xué)家G.B.丹齊克于1947年首先提出來的，其理論根據(jù)是：線性規(guī)劃問題的可行域是維向量空間中的多面凸集，其最優(yōu)值如果

38、存在，必在該凸集的某頂點處達到，而頂點所對應(yīng)的可行解稱為基本可行解.以上是最優(yōu)化方法的一些基本介紹，接下來本文將討論最優(yōu)化方法下的共軛梯度法.</p><p>　　2.2 共軛梯度法理論</p><p>　　2.2.1 共軛梯度法的概念</p><p>　　共軛梯度法是在每一迭代步利用當(dāng)前點處的最速下降方向來生成二次函數(shù)的Hesse矩陣的共軛方向，并建立求在上的

39、極小點的方法.這一方法早年稱為共軛斜量法，于1952年由Hestenes和Stiefle提出來，用于解正定系數(shù)矩陣的線性方程組.后經(jīng)Fletcher和Reeves等人研究并應(yīng)用于優(yōu)化問題，取得了豐富的成果，共軛梯度法也成為當(dāng)前最優(yōu)化方法的重要算法類.</p><p>　　共軛梯度法是利用目標(biāo)函數(shù)的梯度逐步產(chǎn)生共軛方向并將其作為搜索方向的方法.本節(jié)先引進共軛方向的概念，討論目標(biāo)函數(shù)是二次函數(shù)產(chǎn)生共軛方向的方法，由此

40、得到無約束二次規(guī)劃問題的共軛梯度法，然后將該算法推廣到求解一般的無約束非線性規(guī)劃問題.</p><p>　　2.2.2 共軛方向及性質(zhì)</p><p>　　在第一章我們已經(jīng)給出共軛方向的一些基本概念和性質(zhì)，在此我們再次詳細的介紹一下該概念，為后面建立共軛梯度算法做鋪墊.</p><p>　　定義2.1 設(shè)是對稱正定陣.</p><p>&

41、lt;b>　　若對非零向量，有</b></p><p><b>　　(2-1)</b></p><p>　　則稱向量，對共軛. </p><p><b>　　例如=，，，則</b></p><p><b>　　，</b></p><p>

42、;　　所以向量，對共軛. </p><p>　　當(dāng)時，(2-1)變?yōu)?，即與互相正交，由此可見，“共軛”概念是“正交”概念的推廣.</p><p>　　定義2.2 若對非零向量組中任意兩個向量對共軛，即</p><p><b>　　， ，，</b></p><

43、p>　　成立，則稱為的共軛向量組.</p><p>　　定理2.3 是共軛向量組，必是線性無關(guān)向量組.</p><p>　　定理2.4 假設(shè)為連續(xù)可微的嚴(yán)格凸函數(shù)，且存在極小點，為一組線性無關(guān)的向量，則 </p><p><b>　　(2-2)</b></p><p>　　是在通過點由向量生成的維超平面上的唯一

44、極小點的充要條件是：</p><p>　　， . (2-3)</p><p>　　證明 設(shè)，則，為任意實數(shù).將的表達式代入，令</p><p><b>　　==， .</b></p><p>　　可證亦是嚴(yán)格凸函數(shù).因而在上的極小點就是的無約束極小點.設(shè)極小點為，則它應(yīng)滿足

45、</p><p>　　， . (2-4)</p><p>　　將解出代入式(2-2)得，由式(2-4)既得式(2-3)成立.</p><p>　　定理2.5 設(shè)，正定，是關(guān)于的共軛方向組.若以為初始點順次沿方向采用精確搜索進行迭代，則是在上的最小點.當(dāng)時，就是在上的最小點.</p><p>　　這個定理說明，若能得

46、到的個共軛方向，，則從任一初始點出發(fā)，順次沿方向采用精確搜索求步長進行迭代，則步迭代后得到的點是上的最小點，步迭代后，其最后一點即為在上的最小點.這一定理又稱為擴張子空間定理.</p><p>　　2.2.3 共軛梯度法的公式結(jié)構(gòu)</p><p>　　共軛梯度法是在每一迭代步利用當(dāng)前點處的最速下降方向來生成二次函數(shù)的Hesse矩陣的共軛方向，并建立求在上的極小點的方法.根據(jù)這個思想，可以

47、給出共軛梯度法的公式結(jié)構(gòu).</p><p>　　設(shè) ，</p><p>　　其中，為階對稱正定矩陣，為維常量，為實數(shù)，的梯度向量為</p><p>　　. (2-5)</p><p>　　我們?nèi)〉谝粋€方向為初始點處的負梯度方向，即</p><p>

48、;<b>　　=，</b></p><p>　　從出發(fā)沿做精確一維搜索求的步長，得點</p><p><b>　　，</b></p><p>　　由定理2.4可得滿足條件</p><p>　　. (2-6)</p><p>　　在處

49、，我們可以用的負梯度方向與的組合來生成方向，即令</p><p>　　=+ (2-7)</p><p>　　選取一個系數(shù)使得與關(guān)于共軛，即令</p><p><b>　　(2-8)</b></p><p>　　通過這個式子我們可以確定系數(shù)</p>&l

50、t;p>　　將式(2-7)代入式(2-8)可得</p><p>　　. (2-9)</p><p><b>　　由式(2-5)得</b></p><p>　　， (2-10)</p><p>　　因此

51、 . </p><p>　　又由式(2-6)可知，上式可簡化為</p><p>　　， (2-11)</p><p>　　一經(jīng)求出，也可求出.若從出發(fā)沿方向的步長為，有</p><p><b>　　， </b></p><p><b

52、>　　則令方向</b></p><p>　　， (2-12)</p><p>　　選取待定系數(shù)與，使?jié)M足共軛條件</p><p>　　， (2-13)</p><p>　　即要求方向與，共軛.</p><

53、p>　　將式(2-12)代入式(2-13)并解出</p><p>　　， ， (2-14) </p><p>　　代回式(2-12)便可得.由式(2-7)和(2-10)知，是與即與的線性組合，而是與的線性組合，由定理2.5，即擴張子空間定理，可知與，正交.因而，從而</p><p>　　=0.

54、 (2-15)</p><p><b>　　類似地，可得</b></p><p>　　. (2-16)</p><p>　　從而式(2-12)中的方向僅由兩項組合而成.我們要證明這一性質(zhì)對一般情形也成立，下面給出證明.</p><p>　　一般地，若已得及，則令</p

55、><p>　　， (2-17)</p><p>　　為使與共軛，選擇，滿足共軛條件</p><p>　　， ， (2-18)</p><p>　　將式(2-17)代入式(2-18)并利用共軛性，可得</p><p>　　.

56、 (2-19)</p><p>　　在式(2-17)中，令，并且寫成</p><p><b>　　，</b></p><p><b>　　由定理2.4可知</b></p><p>　　， . (2-20)</

57、p><p>　　接下來我們要證明，在式(2-19)中</p><p>　　，， (2-21)</p><p>　　與 </p><p>　　成立，即對任一均有式(2-12)的只含兩項的簡單結(jié)構(gòu).</p><p>　　類似式(2-10)和式(2-16)，我們有<

58、;/p><p>　　及 . (2-22)</p><p><b>　　由此可得</b></p><p><b>　　，</b></p><p>　　由式(2-20)及上式，便可得到</p><p><b>

59、　　，.</b></p><p>　　這一重要性質(zhì)，使得我們在求各時避免了式(2-17)中的繁復(fù)計算，每次產(chǎn)生的共軛方向只由處的與兩項組成，從而得到了結(jié)構(gòu)簡單的共軛梯度法.</p><p>　　下面給出組合系數(shù)的另一種公式表示.</p><p><b>　　由于，所以</b></p><p><b>

60、;　　.</b></p><p>　　在式(2-17)中，應(yīng)用的表達式，即</p><p>　　再由定理2.4，可得</p><p><b>　　， </b></p><p>　　從而得到公式(2-21) </p><p><b>　　(2-23)&

61、lt;/b></p><p>　　又由式(2-20)，這樣便可得到由Fletcher-Reeves給出的公式(簡稱FR公式)</p><p><b>　　(2-24)</b></p><p>　　如上，采用FR公式的共軛梯度法，稱為Fletcher-Reeves共軛梯度法.</p><p>　　2.2.4 共軛梯

62、度法的算法步驟</p><p>　　根據(jù)不同的函數(shù)結(jié)構(gòu)，我們會得出不同的共軛梯度算法，而利用共軛梯度法求解二次凸函數(shù)的最小點，在我們的理論學(xué)習(xí)中最常見而且應(yīng)用相當(dāng)熟練.</p><p>　　下面我們給出共軛梯度法求二次凸函數(shù)的最小點的算法步驟.</p><p>　　步驟1 任取初始點，令</p><p><b>　　，</

63、b></p><p><b>　　，轉(zhuǎn)步驟3.</b></p><p>　　步驟2 對，計算及，</p><p>　　， (2-25)</p><p>　　步驟3 線性搜索求步長：</p><p><b>　　.

64、</b></p><p><b>　　令.</b></p><p>　　步驟4 若，則計算結(jié)束，.否則轉(zhuǎn)步驟5.</p><p>　　步驟5 令，，轉(zhuǎn)回步驟2.</p><p>　　2.2.5 共軛梯度法的優(yōu)點</p><p>　　近年來，隨著計算機的飛速發(fā)展和實際問題中大規(guī)

65、模優(yōu)化問題的涌現(xiàn)，再加上共軛梯度法具有相當(dāng)多的優(yōu)點，使得尋找快速有效的共軛梯度法成為了學(xué)者們研究的熱門方向之一.主要優(yōu)點有：</p><p>　　(1)共軛梯度法不僅克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點，使得共軛梯度法已成為解大型非線性最優(yōu)化最有效的算法之一.</p><p>　　(2)共軛梯度法是一個典型的共軛方向法，它的每一個搜索方向是互

66、相共軛的，而這些搜索方向d僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，共軛梯度法具有存儲量少、計算方便的優(yōu)點.</p><p>　　(3)共軛梯度法不需要矩陣存儲，所以它具有較快的收斂速度和二次終止性等優(yōu)點.</p><p><b>　　2.3 算法實例</b></p><p>　　我們知道，共軛梯度法是在每一迭代步利用當(dāng)前點處的最速

67、下降方向來生成二次函數(shù)的Hesse矩陣的共軛方向，并建立求在上的極小點的方法.所以我們要先生成共軛方向，再建立求解方法.</p><p>　　例1 ，，為的共軛方向.取初始點，求共軛方向，.</p><p>　　解 由題可知，取初始點，由，得</p><p><b>　　，.</b></p><p>　　然后求從出發(fā)

68、沿方向的線性最優(yōu)步長：</p><p><b>　　.</b></p><p><b>　　令，因而</b></p><p><b>　　.</b></p><p>　　由定理2.5可知，，解得.所以有</p><p><b>　　.</

69、b></p><p><b>　　計算處的和，有</b></p><p><b>　　，</b></p><p><b>　　.</b></p><p><b>　　因而</b></p><p><b>　　.<

70、;/b></p><p>　　由上可知共軛方向，.</p><p>　　從上面的例子中，我們可以很容易的得到二元二次方程共軛方向的求解過程，而對于三次以上的方程，由于計算復(fù)雜，在此不列出詳細求解過程.接下來我們都將討論二元二次方程的求解過程，從簡單的求解過程當(dāng)中理解什么是共軛梯度法，以及如何熟練的應(yīng)用共軛梯度法求解，這些即是本文的主要目的.下面給出的例子，詳細給出了共軛梯度法的全部求

71、解過程，并最終求得方程的最小解.而且這個例子將被用在第四章，作為MATLAB編程的算法實例.</p><p>　　例2 用共軛梯度法求的最小解.</p><p>　　解 取初始點，由，得</p><p><b>　　，.</b></p><p>　　然后求從出發(fā)沿方向的線性最優(yōu)步長：</p><p

72、><b>　　.</b></p><p><b>　　令，因而</b></p><p><b>　　.</b></p><p>　　由定理2.5可知，，解得.所以有</p><p><b>　　.</b></p><p>&l

73、t;b>　　計算處的和，有</b></p><p><b>　　，</b></p><p><b>　　.</b></p><p><b>　　因而</b></p><p><b>　　.</b></p><p>

74、　　求從出發(fā)沿方向的線性最優(yōu)步長.</p><p>　　令 ， (2-26)</p><p>　　將的表達式代入中，得</p><p><b>　　=.</b></p><p><b>　　同樣的有</b></p><p><b>　　，<

75、/b></p><p>　　解得 .</p><p>　　再將的值代入式（2-26），可得</p><p><b>　　.</b></p><p>　　以代入中，得=0.因此，</p><p><b>　　.</b></p><

76、;p>　　值得注意的是，在共軛梯度法中，初始方向應(yīng)取最速下降方向，否則產(chǎn)生的方向不一定是共軛方向.</p><p>　　例3 用共軛梯度法求的最小點.</p><p>　　解 取初始點，由題可知，</p><p>　　取初始方向，令，則.</p><p>　　從方程中，解出沿的步長.因而</p><p>

77、<b>　　，.</b></p><p><b>　　由于，可得.</b></p><p>　　接下來驗證.取，因而可得</p><p><b>　　.</b></p><p>　　這說明與對不共軛，從出發(fā)沿方向求解也得不到的最小點.這個例子充分解釋了，在選取初始方向時，應(yīng)取最

78、速下降方向，否則產(chǎn)生的方向不一定是共軛方向.</p><p>　　第三章 算法的收斂性</p><p>　　本章主要分兩部分，第一部分先給出共軛梯度法的一些性質(zhì)和收斂性定理；然后第二部分則是分析算法的收斂性，通過總結(jié)已有學(xué)者的研究結(jié)果，證明該算法在一定條件下具有全局收斂性.</p><p>　　3.1 共軛梯度法的性質(zhì)與收斂性定理</p><

79、p>　　3.1.1 共軛梯度法的性質(zhì)</p><p>　　定理3.1 對于二次凸函數(shù)，若用共軛梯度法求解且采用線性最優(yōu)步長，則算法對任一迭代步，有下述關(guān)系式成立：</p><p>　　， ， (3-1)</p><p>　　， ， (3-2)</p><

80、p>　　， (3-3)</p><p>　　且算法最多步便可求得的最小點. </p><p>　　證明 利用歸納法.由共軛梯度法的計算公式，若初始點為，則取初始方向，又由步長采用精確線性搜索求得，因而步長滿足關(guān)系即.由，的選擇使，即式(3-1)成立.由的定義，當(dāng)時式(3-3)成立.因而當(dāng)時式(3-1)，(3-2)，(3-3

81、)均成立.</p><p>　　現(xiàn)設(shè)對于任一迭代步，式(3-1)～式(3-3)均成立，要證時，它們也成立.</p><p>　　由式(2-5)可得 </p><p><b>　　，</b></p><p>　　. (3-4)</p>&

82、lt;p>　　下面證明式(3-1)和式(3-2)當(dāng)時成立.由式(3-4)和式(2-25)，可得</p><p><b>　　(3-5)</b></p><p>　　又由的定義，以及在式(3-4)中，令，可得</p><p>　　. (3-6) </p><p>　　由歸納假設(shè)，式(3-1)～式(3-

83、3)，當(dāng)時成立，因而式(3-5)與式(3-6)的右端都為零，即 </p><p><b>　　, ,</b></p><p>　　， (3-7)</p><p>　　成立，亦即式(3-1)和式(3-2)當(dāng)時對也成立.</p><p>　　當(dāng)時，式(3-5)可寫成&l

84、t;/p><p><b>　　.</b></p><p>　　對于，我們在式(3-4)中兩邊乘，注意到，將解出，利用式(3-3)的歸納假設(shè)，可得的另一個表達式</p><p>　　. (3-8)</p><p>　　將此式代入上式，可得</p><p>&l

85、t;b>　　(3-9)</b></p><p>　　成立，即式(3-2)對成立.</p><p>　　對于式(3-1)，當(dāng)時，式(3-6)變?yōu)?lt;/p><p><b>　　，</b></p><p>　　利用式(3-8)以及的FR公式，可知</p><p><b>　　

86、(3-10)</b></p><p>　　成立，亦即式(3-1)成立.</p><p>　　對于式(3-3)，當(dāng)時，由的定義及精確搜索，可得</p><p>　　. (3-11)</p><p>　　因而上述式(3-9)～式(3-11)當(dāng)時也成立，這就充分證明了式(3-1)～式(3-3)當(dāng)時也成立.</p>

87、<p>　　3.1.2 共軛梯度法的收斂性定理</p><p>　　前面我們已經(jīng)簡要給出了FR共軛梯度法，下面我們簡述一下FR共軛梯度法應(yīng)用于極小化非二次函數(shù)時，在精確一維搜索與非精確強Wolfe搜索下的收斂性問題.因此，現(xiàn)在我們要引用一維搜索與強Wolfe搜索的基本概念.</p><p>　　在迭代算法求步長的計算中，要有充分下降性要求，否則當(dāng)移動步長很小時，點與點很接近，函

88、數(shù)值與相差很小.因此我們必須有求得步長的有效方法.</p><p>　　令 ，</p><p>　　若是一元函數(shù).則求使的方法，稱為一維搜索方法.</p><p>　　一維搜索方法有多種，下面介紹兩種常用的方法.</p><p><b>　　(1)線性最優(yōu)步長</b></p>

89、<p>　　在式()中求()的最小點或第一個極小點對于的步長.這種方法是理論上的，常在理論論證中使用，稱為精確線性搜索.而且在上章的算法實例中都使用了該方法求線性最優(yōu)步長.</p><p>　　(2)Wolfe方法</p><p>　　給定數(shù)，.求使下列兩個不等式</p><p>　　， (3-12)</p>&l

90、t;p><b>　　(3-13)</b></p><p>　　同時成立.式(3-13)有時也可用更強的條件</p><p><b>　　(3-14)</b></p><p>　　來代替.條件(3-12)和條件(3-14)則稱為強Wolfe搜索.若充分小，則式(3-14)就變成了近似精確線性搜索.</p>

91、<p>　　接下來是給出共軛梯度法的一些收斂性定理，同樣是針對FR共軛梯度法.</p><p>　　對于FR共軛梯度法，對于當(dāng)前點，令</p><p>　　， ， (3-15)</p><p><b>　　其中的組合系數(shù)</b></p><p>　　，.

92、 (3-16)</p><p><b>　　作一維搜索求，令</b></p><p>　　， (3-17)</p><p>　　重復(fù)上述計算.算法停止規(guī)則，可取.</p><p>　　定理3.2 （FR共軛梯

93、度法的收斂性定理）設(shè)連續(xù)可微，水平集有界，則當(dāng)FR算法采用一維精確搜索應(yīng)用于極小化時，若產(chǎn)生的迭代點列為，則有以下結(jié)論：</p><p>　　(1)若為有窮點列，則其最后一點為的穩(wěn)定點.</p><p>　　(2)若為無窮點列，則其任一極限點是的穩(wěn)定點. </p><p>　　證明 (1)當(dāng)為有限點列時，由停止規(guī)則可知，點列的最后一點有，因而為的穩(wěn)定點或近似穩(wěn)定點

94、.</p><p>　　(2)若為無窮點列，則有與.由式(3-15)及一維搜索性質(zhì)可得</p><p><b>　　，</b></p><p>　　是在處的一個下降方向，因而</p><p><b>　　，</b></p><p>　　是單調(diào)下降序列且點列.由水平集合有界，可

95、知為有界序列且必有極限點存在.</p><p>　　設(shè)極限點為，則存在的子列，使得</p><p><b>　　.</b></p><p>　　因為，所以.由的連續(xù)性,可知對于，有</p><p><b>　　.</b></p><p>　　同理，也是有界點列，因而有極限點及

96、子列，當(dāng)時，</p><p><b>　　，</b></p><p><b>　　. </b></p><p><b>　　于是，我們得到</b></p><p>　　. (3-18)</p><p&g

97、t;　　接下來證明.用反證法，設(shè)，并令，則在處，對于充分小的，有</p><p>　　成立.由一維精確搜索，</p><p><b>　　，</b></p><p>　　因而，對，當(dāng)時，由上面的結(jié)果可得</p><p><b>　　，</b></p><p>　　此式與式(3

98、-18)矛盾，即.從而證明了極限點為穩(wěn)定點.</p><p>　　當(dāng)FR方法采用強Wolfe非精確搜索時，又有如下的收斂性定理.</p><p>　　定理3.3 設(shè)二階連續(xù)可微，水平集有界，步長采用強Wolfe非精確搜索，且，則對FR方法產(chǎn)生的點列，有</p><p>　　成立，即FR共軛梯度法具有全局收斂性.</p><p>　　3.2

99、 戴彧虹-袁亞湘共軛梯度法</p><p>　　由于證明算法的收斂性相對困難，而且所掌握的知識有限，所以本節(jié)主要是借鑒已有學(xué)者的研究結(jié)果，闡明該算法在一定的條件下具有收斂性.</p><p>　　在以往的共軛梯度法的收斂性證明中，通常要求步長滿足強Wolfe搜索.1999年，戴彧虹、袁亞湘給出了一個新的共軛梯度法，降低了搜索條件，并給出了一個非常簡捷的收斂性證明.下面我們介紹這個方法.&l

100、t;/p><p>　　算法中，點列與方向仍由公式</p><p>　　， (3-19)</p><p>　　給出，其中由搜索條件</p><p>　　， (3-20)</p><p><b>　　(3-21)</b>

101、;</p><p>　　確定，.由下式定義：</p><p>　　， (3-22)</p><p><b>　　其中，為歐氏模.</b></p><p>　　由式(3-21)可得</p><p><b>　　這說明有意義，且有<

102、/b></p><p><b>　　.</b></p><p>　　對于式(3-22)定義的，由上式與式(3-19)可得</p><p><b>　　，</b></p><p><b>　　即為的下降方向.</b></p><p>　　應(yīng)用及的表示

103、式，可得</p><p>　　. (3-23)</p><p>　　從而得到一個新的公式：</p><p>　　. (3-24)</p><p>　　這個表示式將在下面定理的證明中起著非常重要的作用.</p><p>　　為證明算法的收斂性，

104、假定：</p><p>　　(1)在有下界且在水平集的一個鄰域上連續(xù)可微.</p><p>　　(2)在上Lipschitz連續(xù)，即存在常數(shù)，使得</p><p>　　， (3-25)</p><p><b>　　成立.</b></p><p>　　引理3.4

105、 設(shè)初始點滿足假設(shè)條件，若在算法模型(3-19)中，是下降的，由式(3-20)和式(3-21)確定，則Zoutendijk條件</p><p><b>　　(3-26)</b></p><p><b>　　成立.</b></p><p>　　證明 從式(3-21)可知</p><p><b&

106、gt;　　.</b></p><p>　　由式(3-25)，有 </p><p><b>　　，</b></p><p>　　從而可得 .</p><p>　　由式(3-20)得到</p><p>　　， (

107、3-27)</p><p><b>　　其中.</b></p><p>　　將式(3-27)對求和，應(yīng)用有下界，可知引理成立.</p><p>　　定理3.5 若假設(shè)條件成立，為算法的初始點，則算法產(chǎn)生的點列或終止于穩(wěn)定點或</p><p><b>　　成立.</b></p><

108、;p>　　證明 若算法不在有限步終止，則對所有，成立.</p><p>　　現(xiàn)在先證明所有的方向都是下降方向，即，有 </p><p><b>　　.</b></p><p>　　顯然，上述不等式當(dāng)時成立.應(yīng)用歸納法，設(shè)不等式對成立.利用式(3-21)，上面已證明當(dāng)時，有.因此由式(3-23)可知</p><p>

109、;　　成立.將式(3-19)中的表示式寫成</p><p><b>　　，</b></p><p><b>　　兩邊的模平方可得</b></p><p><b>　　.</b></p><p>　　上式除以并利用式(3-24)有</p><p><

110、b>　　.</b></p><p>　　應(yīng)用這個遞推關(guān)系式及，可知對任一，有</p><p><b>　　(3-28)</b></p><p><b>　　成立.</b></p><p>　　若定理不真，則存在常數(shù)使得對，.由此式與式(3-28)，便得

111、 </p><p><b>　　，</b></p><p><b>　　這說明</b></p><p><b>　　，</b></p><p>　　這與Zontendijk條件(3-26)矛盾.因此，定理成立.</p><p>　　以上就是戴彧虹-

112、袁亞湘共軛梯度法收斂性證明的全部過程，通過對算法的收斂性的證明，使我們更大程度的學(xué)習(xí)和理解了共軛梯度法的性質(zhì)，并能有效的發(fā)揮和運用到共軛梯度法的求解當(dāng)中.</p><p><b>　　第四章 算法編程</b></p><p>　　本章的主要思想就是通過MATLAB編程，先介紹MATLAB的背景，以及發(fā)展歷程和影響；然后通過算法實例編程，代入實例中的相關(guān)數(shù)據(jù)得到一些相

113、關(guān)的數(shù)值結(jié)果；最后對數(shù)據(jù)進行分析驗證，判斷該算法是否有效.</p><p>　　4.1 MATLAB的發(fā)展歷程和影響</p><p>　　20世紀(jì)70年代，時任美國新墨西哥大學(xué)計算機科學(xué)主任的Cleve Moler教授出于減輕學(xué)生編程負擔(dān)的目的，為學(xué)生設(shè)計了一組調(diào)用LINPACK和EISPACK庫程序的接口，此即用FORTRAN語言編寫的萌芽狀態(tài)的MATLAB.經(jīng)過幾年的校際流傳，在Li

114、ttle的推動下，由Little、Moler、Steve Bangert，于1984年成立了MathWorks公司，并把MATLAB正式推向市場.從那時起，MATLAB的內(nèi)核采用C語言編寫，而且除原有的數(shù)值計算能力外，還新增了數(shù)據(jù)圖視功能.MATLAB以商品形式出現(xiàn)后的短短幾年，就以其良好的開放性和運行的可靠性，使原先控制領(lǐng)域里的封閉式軟件包紛紛淘汰，而改在MATLAB平臺上重建.到了20世紀(jì)90年代，MATLAB已經(jīng)成為國際控制界公認

115、的標(biāo)準(zhǔn)計算軟件.90年代初期，在國際上的數(shù)學(xué)類科技應(yīng)用軟件中，MATLAB在數(shù)值計算方面已獨占鰲頭.</p><p>　　目前，MATLAB已成為國際上最為流行的軟件之一，它除了傳統(tǒng)的交互式編程之外，還提供了豐富可靠的矩陣運算、圖形繪制、數(shù)據(jù)處理、圖像處理、語言編程等便利工具，出現(xiàn)了以各種MATLAB為基礎(chǔ)的實用工具箱，廣泛地應(yīng)用于自動控制、圖像信號處理、模糊推理、神經(jīng)網(wǎng)絡(luò)、小波變換、信號分析、振動理論、時序分析

116、與建模、化學(xué)統(tǒng)計學(xué)、優(yōu)化設(shè)計等領(lǐng)域，并表現(xiàn)出一般高級語言難以比擬的優(yōu)勢.</p><p>　　4.2 共軛梯度法的MATLAB程序</p><p>　　本節(jié)主要是通過MATLAB編寫共軛梯度法程序，然后針對實際問題，代入相關(guān)數(shù)據(jù)，即得問題所求解.下面給出共軛梯度法的程序，即cg程序，該程序是利用再開始技術(shù)和簡單線搜索的FR共軛梯度法.為了使程序容易讀懂，程序的開頭部分增加了程序名、程序功

117、能和變量用途的說明.</p><p><b>　　%</b></p><p>　　% 無約束優(yōu)化下的FR共軛梯度法</p><p><b>　　%</b></p><p>　　function [x,output]=cg(fun,dfun,x0)</p><p>&l

118、t;b>　　%</b></p><p>　　% fun: 字符變量,目標(biāo)函數(shù)的函數(shù)名. </p><p>　　% dfun: 字符變量,目標(biāo)函數(shù)梯度的函數(shù)名.</p><p>　　% x0: 實向量,輸入初始點.</p><p>　　% x: 實向量,輸出結(jié)果.</p

119、><p>　　% output: 結(jié)構(gòu)變量,輸出值f,迭代次數(shù),最終點x的梯度值.</p><p>　　% epsi: 實常數(shù),終止條件.</p><p>　　% k: 整型變量,迭代數(shù).</p><p>　　% funcN: 整型變量,函數(shù)值.</p><p>　　%

120、 rho,1,u: 實常數(shù),線搜索文件lines中的參數(shù).</p><p>　　% n: 常量,變量數(shù)</p><p>　　% g,gold: n維實向量,點x和最終點x的梯度.</p><p>　　% iterm: 整型變量,等于k的模的(n+1)次方.</p><p>　　% d,dold: n維

121、實向量,當(dāng)前和以前的搜索方向.</p><p>　　% alpha,alpha_0: 實變量,步長和初始步長. </p><p>　　% funcNk: 整型變量,函數(shù)值.</p><p>　　% 文件lines</p><p>　　% exitflag:整型變量,等于0時表示線搜索成功,等于-

122、1時表示線搜索失敗.</p><p><b>　　%</b></p><p>　　% Step 1: 初始化</p><p><b>　　%</b></p><p>　　epsi=1.0e-3;</p><p><b>　　k=0;</b><

123、;/p><p><b>　　funcN=0;</b></p><p>　　rho =0.01;l=0.15;u=0.85;</p><p><b>　　x=x0;</b></p><p>　　f=feval(fun,x);</p><p>　　funcN=funcN+1;<

124、/p><p>　　n=length(x0);</p><p><b>　　%</b></p><p>　　% Step 2: 判斷收斂條件</p><p><b>　　%</b></p><p>　　g=feval(dfun,x);</p><p>