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

1、 本科畢業(yè)設計（論文）開題報告 題 目： 共軛梯度算法的設計與實現(xiàn) 學生姓名： 院 （系）： 理學院 專業(yè)班級： 信息0602 指導教師： 完成時間： 2010年 月 日 一、課題的意義最優(yōu)化方法是近幾十年形成的，它主要運用數(shù)學方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學決策的依據(jù)。最優(yōu)化方法的目的在于針對所研究的系統(tǒng)，求得一個合理運用人力、物力和財力的最佳方案，發(fā)揮和提高系統(tǒng)的效率及效益，最終達到系統(tǒng)的最優(yōu)目標。實踐表明，隨著科學技術的日益進步和生產(chǎn)經(jīng)營的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學的重要理論基礎和不可缺少的方法，被人們廣泛地應用到公共管理、經(jīng)濟管理、國防等各個領域，發(fā)揮著越

2、來越重要的作用。最優(yōu)化方法又可分為無約束最優(yōu)化方法和約束最優(yōu)化方法，其中無約束最優(yōu)化方法包括最速下降法，牛頓法，共軛方向法，以及共軛梯度法和變尺度法，約束優(yōu)化方法包括單純形法，解線性規(guī)劃的圖解法，等式約束的罰函數(shù)法，以及Rosen梯度投影法。本文將討論無約束最優(yōu)化方法下的共軛梯度法，通過MATLAB編程實現(xiàn)，并以具體實例得出相應的數(shù)值結果，然后驗證該方法是否有效。二、國內(nèi)外研究現(xiàn)狀近年來，隨著模糊理論、神經(jīng)網(wǎng)絡等智能技術和計算機技術的發(fā)展，智能式的優(yōu)化方法越來越受重視。現(xiàn)今，國內(nèi)外主要研究的方法有：（1）神經(jīng)網(wǎng)絡優(yōu)化方法 HYPERLINK :/wiki.mbalib /wiki/%E4%BA

3、%BA%E5%B7%A5%E7%A5%9E%E7%BB%8F%E7%BD%91%E7%BB%9C o 人工神經(jīng)網(wǎng)絡 人工神經(jīng)網(wǎng)絡的研究起源于1943年和 HYPERLINK :/wiki.mbalib /w/index.php?title=Mc_Culloch&action=edit o Mc Culloch Mc Culloch和hp?title=Pitts&action=edit o Pitts Pitts的工作。在優(yōu)化方面，1982年 HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield&action=edit o Hopfield Ho

4、pfield首先引入Lyapuov能量函數(shù)用于5判斷網(wǎng)絡的穩(wěn)定性，提出了%8D%95%E5%B1%82%E7%A6%BB%E6%95%A3%E6%A8%A1%E5%9E%8B&action=edit o Hopfield單層離散模型 Hopfield單層離散模型； HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield&action=edit o Hopfield Hopfield和=Tank&action=edit o Tank Tank又發(fā)展了 HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfie

5、ld%E5%8D%95%E5%B1%82%E8%BF%9E%E7%BB%AD%E6%A8%A1%E5%9E%8B&action=edit o Hopfield單層連續(xù)模型 Hopfield單層連續(xù)模型。1986年，Hopfield和Tank將電子電路與Hopfield模型直接對應，實現(xiàn)了硬件模擬； HYPERLINK :/wiki.mbalib /w/index.php?title=Kennedy&action=edit o Kennedy Kennedy和 HYPERLINK :/wiki.mbalib /w/index.php?title=Chua&action=edit o Chua C

6、hua基于非線性電路理論提出了模擬電路模型，并使用系統(tǒng)微分方程的Lyapuov函數(shù)研究了電子電路的穩(wěn)定性。這些工作都有力地促進了對神經(jīng)網(wǎng)絡優(yōu)化方法的研究。（2）模糊優(yōu)化方法最優(yōu)化問題一直都是模糊理論應用最為廣泛的領域之一。自從 HYPERLINK :/wiki.mbalib /w/index.php?title=Bellman&action=edit o Bellman Bellman和 HYPERLINK :/wiki.mbalib /wiki/L.A.zadeh o L.A.zadeh 在70年代初期對這一研究作出開創(chuàng)性工作以來，其主要研究集中在一般意義下的理論研究、 HYPERLINK

7、:/wiki.mbalib /wiki/%E6%A8%A1%E7%B3%8A%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92 o 模糊線性規(guī)劃 模糊線性規(guī)劃、 HYPERLINK :/wiki.mbalib /w/index.php?title=%E5%A4%9A%E7%9B%AE%E6%A0%87%E6%A8%A1%E7%B3%8A%E8%A7%84%E5%88%92&action=edit o 多目標模糊規(guī)劃 多目標模糊規(guī)劃、以及模糊規(guī)劃理論在 HYPERLINK :/wiki.mbalib /wiki/%E9%9A%8F%E6%9C%BA%E8%A7%84%E5%

8、88%92 o 隨機規(guī)劃 隨機規(guī)劃及許多實際問題中的應用。主要的研究方法是利用模糊集的a截集或確定模糊集的隸屬函數(shù)將模糊規(guī)劃問題轉化為經(jīng)典的規(guī)劃問題來解決。 （3）支持向量機方法支持向量機是由Vapnik領導的AT&TBell實驗室研究小組在1963年提出的一種新的非常有潛力的分類技術，SVM是一種基于統(tǒng)計學習理論的模式識別方法，主要應用于模式識別領域。由于當時這些研究尚不十分完善，在解決模式識別問題中往往趨于保守，且數(shù)學上比較艱澀，這些研究一直沒有得到充分的重視。直到90年代，統(tǒng)計學習理論的實現(xiàn)和由于神經(jīng)網(wǎng)絡等較新興的機器學習方法的研究遇到一些重要的困難，比如如何確定網(wǎng)絡結構的問題、過學習與

9、欠學習問題、局部極小點問題等，使得SVM迅速發(fā)展和完善，在解決小樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應用到函數(shù)擬合等其他機器學習問題中。 共軛梯度法在以上的優(yōu)化方法中都得到了應用，例如，有學者就應用共軛梯度法對網(wǎng)絡的權值和閡值進行優(yōu)化計算，完成神經(jīng)網(wǎng)絡訓練的方法；還有學者在支持向量機方法中應用共軛梯度法，便得到了一種更有效的光滑支持向量機方法。三、畢業(yè)論文的主要內(nèi)容1了解共軛梯度法的背景和意義。2建立一個求解無約束最優(yōu)化問題的共軛梯度算法。3闡述該算法的具體實現(xiàn)步驟并分析該算法的全局收斂性。4通過MATLAB編程實現(xiàn)得到的數(shù)值實驗結果來驗證算法是否有效。四、所采用的

10、方法、手段以及步驟 通過網(wǎng)絡、書籍和一些參考資料，查詢相關信息，理解什么是共軛梯度法，以及如何應用共軛梯度法完成最優(yōu)化設計。將從以下幾個內(nèi)容考慮：1. 建立一個求解無約束最優(yōu)化問題的共軛梯度算法：通過實例，結合參考資料以及自己所掌握的知識，建立一個求解該實例的共軛梯度算法。2. 分析算法的全局收斂性：運用所學知識，并借鑒一些學者的文獻證明該算法在指定的搜索方向下具有全局收斂性。3. 通過數(shù)值實驗結果來驗證算法是否有效：通過MATLAB編程，代入實例中的相關數(shù)據(jù)得到一些相關的數(shù)值結果，最后對數(shù)據(jù)進行分析驗證，判斷該算法是否有效。五、階段進度計劃第1-2周：在老師的指導下,搜索與共軛梯度法相關的資

11、料，按照規(guī)定做相應的外文翻譯，并了解其背景、應用及意義，弄懂該方法的基本思想。第3-4周：查閱相關參考資料，完成開題報告和外文翻譯，并通過老師的審查第5-6周：對畢業(yè)設計的具體內(nèi)容做詳細的了解，分析研究共軛梯度法，并完成論文的引言部分。第7-9周：建立一個求解實際問題的共軛梯度算法，闡述該算法的具體實現(xiàn)步驟并分析該算法的全局收斂性，完成論文的核心部分。第9-10周：通過MATLAB編程對算法進行檢驗并對算法是否有效進行解釋，并完成論文最后的結束語部分。第11-12周：整合以上各個階段的成果，總結所做的工作，并完成論文的初稿。第13-15周：將論文初稿交予指導老師審閱，根據(jù)老師的意見修改并完善論

12、文。第16周：請評閱老師評閱論文，最后進行畢業(yè)論文的答辯。六、參考文獻1 袁亞湘，孫文瑜.最優(yōu)化理論與算法M.北京：科學出版社,1997. 2 蔣金山,何春雄,潘少華.最優(yōu)化計算方法M.廣東：華南理工大學出版社,2008.3 張秀軍，徐安農(nóng).htm%09%09%09%09%09%09%09%09%09%09%09%09%09 t _blank 一種新的非線性共軛梯度法的全局收斂性J.廣西科學報，2005，5(04)：87-96.4 時貞軍. HYPERLINK :/www ki /Article/CJFDTOTAL-SXWX200406004.htm%09%09%09%09%09%09%09%

13、09%09%09%09%09%09 t _blank 精確搜索下的非線性共軛梯度法J.數(shù)學物理學報，2004，21（06）：55-58.5 云天銓. HYPERLINK :/www ki /Article/CJFDTOTAL-HZLG198003003.htm%09%09%09%09%09%09%09%09%09%09%09%09%09 t _blank 二維無約束優(yōu)化問題的最優(yōu)方向搜索法J.華中科技大學學報(自然科學版)，1980，22（03）：73-85.6 張秀軍,徐安農(nóng),李安坤,蔣利華. HYPERLINK :/www ki /Article/CJFDTOTAL-GLDZ2005060

14、16.htm%09%09%09%09%09%09%09%09%09%09%09%09%09 t _blank 改進的共軛梯度法及其收斂性J.桂林電子工業(yè)學院學報，2005，13（06）：5-8.7 孟江,王耀才,洪留榮.%09%09%09%09%09%09%09 t _blank 共軛梯度與牛頓混雜算法及在神經(jīng)網(wǎng)絡的應用J.計算機工程與應用，2004，25(35)：31-37.8 陳紅霞,袁業(yè)立,劉娜,曲媛媛. HYPERLINK :/www ki /Article/CJFDTOTAL-SEAC200306004.htm%09%09%09%09%09%09%09%09%09%09%09%09%

15、09 t _blank 非線性共軛梯度法在東海黑潮流計算中的應用J.海洋學報(中文版)，2003，18(06)：131-139.9 王磊.支持向量機學習算法的若干問題研究.成都：電子科技大學博士學位論文，2007.10袁玉波，嚴杰，徐成賢.多項式光滑的支持向量機.計算機學報，2005，28(1)：9-17. 指導教師意見：指導教師簽字：年 月 日系(教研室)意見：主任簽字：年 月 日共軛梯度算法的設計與實現(xiàn)摘要：共軛梯度法是最優(yōu)化方法中一種重要的方法.它是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導數(shù)信息，克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆

16、的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化問題最有效的算法之一.近年來，隨著計算機的飛速發(fā)展和實際問題中大規(guī)模優(yōu)化問題的涌現(xiàn)，尋找快速有效的共軛梯度法成為了學者們研究的熱門方向之一.本文主要研究求解無約束最優(yōu)化問題的共軛梯度法.具體從以下方面著手，介紹所選課題的研究背景、意義和研究現(xiàn)狀；闡述共軛梯度法理論，包括共軛梯度法的一些基本概念，計算公式和迭代步驟；引入一些實際問題，建立共軛梯度算法；根據(jù)已有學者的研究結果，分析算法的收斂性；運用MATLAB編程，代入實例中的相關數(shù)據(jù)得到一些相關的數(shù)值結果；最后對數(shù)據(jù)進行分析驗證，判斷該算法的有效性.關鍵詞：無約束

17、最優(yōu)化；共軛梯度法；迭代；全局收斂性Conjugate Gradient Algorithm Design and ImplementationAbstract：Conjugate gradient method is one of the important optimization methods. It is between the steepest descent method and Newton method, which only requires the first order derivative. It not only overcomes the shortcomings

18、 of slow convergence of steepest descent method, but also avoids the shortcomings of storing and calculating the inverse Hesse 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 also is one of the most effe

19、ctive algorithms to solve a large nonlinear optimization problem.In recent years, with the rapid development of computer 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 direction

20、s of scholars. This paper mainly discusses 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 conjugate gradient method, which includes som

21、e of the basic concepts, formulas and iterative steps; introduce some practical problems, establish the conjugate gradient algorithm; based on the existing academic research results, analyze the convergence of the algorithm; use the MATLAB programming, behalf of the relevant data into the instances

22、to get some relevant numerical results; finally, analyze the data and determine the effectiveness of the algorithm. Key words：Unconstrained optimization；Conjugate gradient method；Iteration；Global convergence目 錄 TOC o 1-3 h z u HYPERLINK l _Toc263421787 第一章 緒論 PAGEREF _Toc263421787 h 1 HYPERLINK l _T

23、oc263421788 1.1 研究背景和意義 PAGEREF _Toc263421788 h 1 HYPERLINK l _Toc263421789 1.2 共軛梯度法的研究現(xiàn)狀 PAGEREF _Toc263421789 h 1 HYPERLINK l _Toc263421790 1.2.1 理論研究 PAGEREF _Toc263421790 h 1 HYPERLINK l _Toc263421791 1.2.2 應用研究 PAGEREF _Toc263421791 h 3 HYPERLINK l _Toc263421792 1.3 本文工作和結構安排 PAGEREF _Toc26342

24、1792 h 4 HYPERLINK l _Toc263421793 第二章 共軛梯度法 PAGEREF _Toc263421793 h 5 HYPERLINK l _Toc263421794 2.1 最優(yōu)化方法 PAGEREF _Toc263421794 h 5 HYPERLINK l _Toc263421795 2.2 共軛梯度法理論 PAGEREF _Toc263421795 h 5 HYPERLINK l _Toc263421796 2.2.1 共軛梯度法的概念 PAGEREF _Toc263421796 h 5 HYPERLINK l _Toc263421797 2.2.2 共軛方向

25、及性質(zhì) PAGEREF _Toc263421797 h 6 HYPERLINK l _Toc263421798 2.2.3 共軛梯度法的公式結構 PAGEREF _Toc263421798 h 7 HYPERLINK l _Toc263421799 2.2.4 共軛梯度法的算法步驟 PAGEREF _Toc263421799 h 11 HYPERLINK l _Toc263421800 2.2.5 共軛梯度法的優(yōu)點 PAGEREF _Toc263421800 h 11 HYPERLINK l _Toc263421801 2.3 算法實例 PAGEREF _Toc263421801 h 12 H

26、YPERLINK l _Toc263421802 第三章 算法的收斂性 PAGEREF _Toc263421802 h 15 HYPERLINK l _Toc263421803 3.1 共軛梯度法的性質(zhì)與收斂性定理 PAGEREF _Toc263421803 h 15 HYPERLINK l _Toc263421804 3.1.1 共軛梯度法的性質(zhì) PAGEREF _Toc263421804 h 15 HYPERLINK l _Toc263421805 3.1.2 共軛梯度法的收斂性定理 PAGEREF _Toc263421805 h 17 HYPERLINK l _Toc263421806

27、3.2 戴彧虹-袁亞湘共軛梯度法 PAGEREF _Toc263421806 h 19 HYPERLINK l _Toc263421807 第四章 算法編程 PAGEREF _Toc263421807 h 24 HYPERLINK l _Toc263421808 4.1 MATLAB的發(fā)展歷程和影響 PAGEREF _Toc263421808 h 24 HYPERLINK l _Toc263421809 4.2 共軛梯度法的MATLAB程序 PAGEREF _Toc263421809 h 24 HYPERLINK l _Toc263421810 第五章 結論 PAGEREF _Toc26342

28、1810 h 30 HYPERLINK l _Toc263421811 參考文獻 PAGEREF _Toc263421811 h 31 HYPERLINK l _Toc263421812 致 謝 PAGEREF _Toc263421812 h 33第一章 緒論本章首先闡明了所選課題的研究背景和意義；然后對最優(yōu)化方法下的共軛梯度方法的產(chǎn)生、主要研究內(nèi)容以及國內(nèi)外的研究現(xiàn)狀進行闡述；最后給出了本論文的主要研究工作和結構安排.1.1 研究背景和意義 最優(yōu)化方法是近幾十年形成的，它主要運用數(shù)學方法研究各種系統(tǒng)的優(yōu)化途徑及方案，為決策者提供科學決策的依據(jù).最優(yōu)化方法的目的在于針對所研究的系統(tǒng)，求得一個合

29、理運用人力、物力和財力的最佳方案，發(fā)揮和提高系統(tǒng)的效率及效益，最終達到系統(tǒng)的最優(yōu)目標.實踐表明，隨著科學技術的日益進步和生產(chǎn)經(jīng)營的日益發(fā)展，最優(yōu)化方法已成為現(xiàn)代管理科學的重要理論基礎和不可缺少的方法，被人們廣泛地應用到公共管理、經(jīng)濟管理、國防等各個領域，發(fā)揮著越來越重要的作用.最優(yōu)化方法又可分為無約束最優(yōu)化方法和約束最優(yōu)化方法，其中無約束最優(yōu)化方法包括最速下降法，牛頓法，共軛方向法，以及共軛梯度法和變尺度法，約束優(yōu)化方法包括單純形法，解線性規(guī)劃的圖解法，等式約束的罰函數(shù)法，以及Rosen梯度投影法.其中最優(yōu)化方法下的共軛梯度法，具有較快的收斂速度和二次終止性等優(yōu)點，得到許多學者們的青睞，使得尋

30、找快速有效的共軛梯度法成為了學者們研究的熱門方向.因此研究所選課題的意義非常重大.1.2 共軛梯度法的研究現(xiàn)狀共軛梯度法最早是由Hestenes和Stiefle(1952)提出來的，用于解正定系數(shù)矩陣的線性方程組，在這個基礎上，F(xiàn)letcher和Reeves(1964)首先提出了解非線性最優(yōu)化問題的共軛梯度法.共軛梯度法是介于最速下降法與牛頓法之間的一個方法，它僅需利用一階導數(shù)信息，克服了最速下降法收斂慢的缺點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點，共軛梯度法不僅是解決大型線性方程組最有用的方法之一，也是解大型非線性最優(yōu)化最有效的算法之一.共軛梯度法又是一個典型的共軛方向法，

31、它的每一個搜索方向是互相共軛的，而這些搜索方向僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，存儲量少，計算方便.由于共軛梯度法不需要矩陣存儲，且有較快的收斂速度和二次終止性等優(yōu)點，現(xiàn)在共軛梯度法已經(jīng)廣泛地應用到實際問題中.1.2.1 理論研究目前，國內(nèi)外對共軛梯度法的研究已經(jīng)相當完善，更有一套幾乎完美的共軛梯度法理論，并且廣泛的應用到實際問題中，為其應用研究奠定了堅實的基礎.在此簡單給出共軛梯度法的一些理論，內(nèi)容主要如下：1.1 共軛方向的概念與性質(zhì) 在優(yōu)化方法中，共軛方向有著重要的意義.一些有效的無約束優(yōu)化算法大多是以共軛方向作為搜索方向的.共軛梯度法就是共軛方向法的一種.若要使第二個

32、迭代點成為該正定二元二次函數(shù)的極小點，只要使兩次一維搜索的搜索方向和關于函數(shù)的二階導數(shù)矩陣為共軛就可以了.對于一般函數(shù)，共軛方向具有以下性質(zhì)：(1)若 (1，2，)是以共軛的個向量，則對于正定二次函數(shù)從任意初始點出發(fā)，依次沿這個方向進行一維搜索，最多次即可達到極小點.(2)從任意兩個點和出發(fā)，分別沿同一方向進行一維搜索，得到兩個一維極小點和，則連接此兩點構成的向量=-，與原方向關于該函數(shù)的二階導數(shù)矩陣相共軛.2 共軛梯度法的計算公式 共軛梯度法是在每一迭代步利用當前點處的最速下降方向來生成二次函數(shù)的Hesse矩陣的共軛方向，并建立求在上的極小點的方法.根據(jù)這個思想，下面簡單給出共軛梯度法的一些

33、計算公式.設 ，其中，為階對稱正定矩陣，為維常量，為實數(shù)，的梯度向量為 .詳細求解過程在第二章中給出.于此同時我們還能給出計算步長的算式.設是上的一組線性無關的向量，則從任意指定的出發(fā)，按以下迭代產(chǎn)生的序列：取，； ：計算，?。?計算，得出； 如此進行下去，直到第步； ：計算，?。挥嬎?，得出 顯然：1.2.2 應用研究近年來，隨著模糊理論、神經(jīng)網(wǎng)絡等智能技術和計算機技術的發(fā)展，智能式的優(yōu)化方法越來越受重視.現(xiàn)今，國內(nèi)外主要研究的方法有：(1)神經(jīng)網(wǎng)絡優(yōu)化方法7%BD%91%E7%BB%9C o 人工神經(jīng)網(wǎng)絡 人工神經(jīng)網(wǎng)絡的研究起源于1943年和 HYPERLINK :/wiki.mbalib

34、/w/index.php?title=Mc_Culloch&action=edit o Mc Culloch Mc Culloch和 HYPERLINK :/wiki.mbalib /w/index.php?title=Pitts&action=edit o Pitts Pitts的工作.在優(yōu)化方面，1982年 HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield&action=edit o Hopfield Hopfield首先引入Lyapuov能量函數(shù)用于5判斷網(wǎng)絡的穩(wěn)定性，提出 HYPERLINK :/wiki.mbalib /w/ind

35、ex.php?title=Hopfield%E5%8D%95%E5%B1%82%E7%A6%BB%E6%95%A3%E6%A8%A1%E5%9E%8B&action=edit o Hopfield單層離散模型 Hopfield單層離散模型； HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield&action=edit o Hopfield Hopfield和ion=edit o Tank Tank又發(fā)展了 HYPERLINK :/wiki.mbalib /w/index.php?title=Hopfield%E5%8D%95%E5%B1%82%

36、E8%BF%9E%E7%BB%AD%E6%A8%A1%E5%9E%8B&action=edit o Hopfield單層連續(xù)模型 Hopfield單層連續(xù)模型.1986年，Hopfield和Tank將電子電路與Hopfield模型直接對應，實現(xiàn)了硬件模擬； HYPERLINK :/wiki.mbalib /w/index.php?title=Kennedy&action=edit o Kennedy Kennedy和 HYPERLINK :/wiki.mbalib /w/index.php?title=Chua&action=edit o Chua Chua基于非線性電路理論提出了模擬電路模型

37、，并使用系統(tǒng)微分方程的Lyapuov函數(shù)研究了電子電路的穩(wěn)定性.這些工作都有力地促進了對神經(jīng)網(wǎng)絡優(yōu)化方法的研究.(2)模糊優(yōu)化方法最優(yōu)化問題一直都是模糊理論應用最為廣泛的領域之一.自從 HYPERLINK :/wiki.mbalib /w/index.php?title=Bellman&action=edit o Bellman Bellman和 HYPERLINK :/wiki.mbalib /wiki/L.A.zadeh o L.A.zadeh L.A.zadeh在70年代初期對這一研究作出開創(chuàng)性工作以來，其主要研究集中在一般意義下的理論研究、 HYPERLINK :/wiki.mbali

38、b /wiki/%E6%A8%A1%E7%B3%8A%E7%BA%BF%E6%80%A7%E8%A7%84%E5%88%92 o 模糊線性規(guī)劃 模糊線性規(guī)劃、 HYPERLINK :/wiki.mbalib /w/index.php?title=%E5%A4%9A%E7%9B%AE%E6%A0%87%E6%A8%A1%E7%B3%8A%E8%A7%84%E5%88%92&action=edit o 多目標模糊規(guī)劃 多目標模糊規(guī)劃、以及模糊規(guī)劃理論在 HYPERLINK :/wiki.mbalib /wiki/%E9%9A%8F%E6%9C%BA%E8%A7%84%E5%88%92 o 隨機規(guī)劃

39、 隨機規(guī)劃及許多實際問題中的應用.主要的研究方法是利用模糊集的截集或確定模糊集的隸屬函數(shù)將模糊規(guī)劃問題轉化為經(jīng)典的規(guī)劃問題來解決. (3)支持向量機方法支持向量機是由Vapnik領導的AT&TBell實驗室研究小組在1963年提出的一種新的非常有潛力的分類技術，SVM是一種基于統(tǒng)計學習理論的模式識別方法，主要應用于模式識別領域.由于當時這些研究尚不十分完善，在解決模式識別問題中往往趨于保守，且數(shù)學上比較艱澀，這些研究一直沒有得到充分的重視.直到90年代，統(tǒng)計學習理論的實現(xiàn)和由于神經(jīng)網(wǎng)絡等較新興的機器學習方法的研究遇到一些重要的困難，比如如何確定網(wǎng)絡結構的問題、過學習與欠學習問題、局部極小點問題

40、等，使得SVM迅速發(fā)展和完善，在解決小樣本、非線性及高維模式識別問題中表現(xiàn)出許多特有的優(yōu)勢，并能夠推廣應用到函數(shù)擬合等其他機器學習問題中.共軛梯度法在以上的優(yōu)化方法中都得到了應用，例如，有學者就應用共軛梯度法對網(wǎng)絡的權值和閡值進行優(yōu)化計算，完成神經(jīng)網(wǎng)絡訓練的方法；還有學者在支持向量機方法中應用共軛梯度法，得到了一種更有效的光滑支持向量機方法.除此之外，共軛梯度法還被應用于其他一些優(yōu)化方法，由于本文對應用領域不做專門研究，其他應用共軛梯度法的優(yōu)化方法不再詳細列舉.1.3 本文工作和結構安排本文研究的課題主要圍繞無約束最優(yōu)化方法下的共軛梯度法進行.通過一個具體的實際問題，結合參考資料已經(jīng)自己所了解

41、的知識，建立一個求解該問題的共軛梯度算法；針對該算法，運用所學知識和一些學者的研究結果，對該算法在指定的搜索方向下的全局收斂性，進行討論分析；基于以上的步驟實現(xiàn)后，通過MATLAB編程，代入實例中的相關數(shù)據(jù)得到一些相關的數(shù)值結果，最后對數(shù)據(jù)進行分析驗證，判斷該算法是否有效.具體內(nèi)容安排如下：第一章為緒論.首先闡明了所選課題的研究背景和意義；然后介紹了共軛梯度法的研究現(xiàn)狀；最后是全文的內(nèi)容和結構安排.第二章引入共軛梯度法理論.簡單的介紹最優(yōu)化方法；然后詳細的闡述共軛梯度法，并引入共軛梯度法的一些基本概念，計算公式和迭代步驟；引入一個實際問題，建立共軛梯度算法，為以后各章的研究奠定了基礎.第三章分

42、析算法的全局收斂性.該章主要分兩部分，第一部分先給出共軛梯度法的一些性質(zhì)和收斂性定理；然后第二部分則是分析算法的全局收斂性，通過總結已有學者的研究結果，證明該算法在一定條件下具有全局收斂性.第四章驗證算法的有效性.也是論文的關鍵部分，主要思想就是通過MATLAB編程，代入實例中的相關數(shù)據(jù)得到一些相關的數(shù)值結果，最后對數(shù)據(jù)進行分析驗證，判斷該算法是否有效.最后是結論.系統(tǒng)的總結了本文的研究工作，不僅指出了一些有待解決的問題，還展望了共軛梯度法未來的研究方向.第二章 共軛梯度法本章先簡單的介紹最優(yōu)化方法；然后詳細的闡述共軛梯度法，并引入共軛梯度法的一些基本概念，迭代公式和迭代步驟；最后引入一個實際

43、問題，建立共軛梯度算法，為以后各章的研究奠定了基礎. 最優(yōu)化方法最優(yōu)化方法大體可分為無約束最優(yōu)化方法和約束最優(yōu)化方法，而無約束最優(yōu)化方法就是求元函數(shù)的極值的方法，它包括最速下降法，擬牛頓法，以及共軛梯度法和信賴域方法.其中最速下降法是以負梯度方向作為下降方向的極小化算法，又稱梯度法，是1874年法國科學家Cauchy提出的，該方法是無約束最優(yōu)化中最簡單的方法；擬牛頓法是目前為止最為行之有效的一種算法，具有收斂速度快、算法穩(wěn)定性強、編寫程序容易等優(yōu)點，在現(xiàn)今的大型計算程序中有著廣泛的應用.我們知道約束優(yōu)化問題是在自變量滿足約束條件的情況下目標函數(shù)最小化的問題，其中約束條件既可以是等式約束也可以是

44、不等式約束,而約束最優(yōu)化方法就是用來求解這一類問題的方法，它包括單純形法，解線性規(guī)劃的圖解法，等式約束的罰函數(shù)法，以及Rosen梯度投影法.其中單純形法是由美國數(shù)學家G.B.丹齊克于1947年首先提出來的，其理論根據(jù)是：線性規(guī)劃問題的可行域是維向量空間中的多面凸集，其最優(yōu)值如果存在，必在該凸集的某頂點處達到，而頂點所對應的可行解稱為基本可行解.以上是最優(yōu)化方法的一些基本介紹，接下來本文將討論最優(yōu)化方法下的共軛梯度法. 共軛梯度法理論 共軛梯度法的概念共軛梯度法是在每一迭代步利用當前點處的最速下降方向來生成二次函數(shù)的Hesse矩陣的共軛方向，并建立求在上的極小點的方法.這一方法早年稱為共軛斜量法

45、，于1952年由Hestenes和Stiefle提出來，用于解正定系數(shù)矩陣的線性方程組.后經(jīng)Fletcher和Reeves等人研究并應用于優(yōu)化問題，取得了豐富的成果，共軛梯度法也成為當前最優(yōu)化方法的重要算法類.共軛梯度法是利用目標函數(shù)的梯度逐步產(chǎn)生共軛方向并將其作為搜索方向的方法.本節(jié)先引進共軛方向的概念，討論目標函數(shù)是二次函數(shù)產(chǎn)生共軛方向的方法，由此得到無約束二次規(guī)劃問題的共軛梯度法，然后將該算法推廣到求解一般的無約束非線性規(guī)劃問題. 共軛方向及性質(zhì)在第一章我們已經(jīng)給出共軛方向的一些基本概念和性質(zhì)，在此我們再次詳細的介紹一下該概念，為后面建立共軛梯度算法做鋪墊.定義 設是對稱正定陣.若對非零

46、向量，有 (2-1)則稱向量，對共軛. 例如=，則 ，所以向量，對共軛. 當時，(2-1)變?yōu)椋磁c互相正交，由此可見，“共軛”概念是“正交”概念的推廣.定義 若對非零向量組中任意兩個向量對共軛，即 ， ，成立，則稱為的共軛向量組.定理 是共軛向量組，必是線性無關向量組.定理2.4 假設為連續(xù)可微的嚴格凸函數(shù)，且存在極小點，為一組線性無關的向量，則 (2-2)是在通過點由向量生成的維超平面上的唯一極小點的充要條件是： ， . (2-3) 證明 設，則，的表達式代入，令 =， .可證在上的極小點就是，則它應滿足 ， . (2-4)將解出代入式(2-2)得，由式(2-4)既得式(2-3)成立.定理

47、2.5 設，正定，是關于為初始點順次沿方向采用精確搜索進行迭代，則是在時，就是在上的最小點.這個定理說明，若能得到的個共軛方向，則從任一初始點出發(fā)，順次沿方向采用精確搜索求步長進行迭代，則步迭代后得到的點是上的最小點，步迭代后，其最后一點即為在上的最小點.這一定理又稱為擴張子空間定理.2.2.3 共軛梯度法的公式結構共軛梯度法是在每一迭代步利用當前點處的最速下降方向來生成二次函數(shù)的Hesse矩陣的共軛方向，并建立求在上的極小點的方法.根據(jù)這個思想，可以給出共軛梯度法的公式結構.設 ，其中，為階對稱正定矩陣，為維常量，為實數(shù)，的梯度向量為 . (2-5) 我們?nèi)〉谝粋€方向為初始點處的負梯度方向，

48、即 =，從出發(fā)沿做精確一維搜索求的步長，得點 ，由定理2.4可得滿足條件 . (2-6)在處，我們可以用的負梯度方向與的組合來生成方向，即令 =+ (2-7)選取一個系數(shù)使得與關于共軛，即令 (2-8)通過這個式子我們可以確定系數(shù)將式(2-7)代入式(2-8)可得 . (2-9)由式(2-5)得 ， (2-10)因此 . 又由式(2-6)可知，上式可簡化為 ， (2-11)一經(jīng)求出，出發(fā)沿方向的步長為，有 ， 則令方向 ， (2-12)選取待定系數(shù)與，使?jié)M足共軛條件 ， (2-13)即要求方向與，共軛. 將式(2-12)代入式(2-13)并解出 ， ， (2-14) 代回式(2-12)便可得.

49、由式(2-7)和(2-10)知，是與即與的線性組合，而是與的線性組合，由定理2.5，即擴張子空間定理，可知與，從而 =0. (2-15) 類似地，可得 . (2-16)從而式(2-12)中的方向僅由兩項組合而成.我們要證明這一性質(zhì)對一般情形也成立，下面給出證明.一般地，若已得及，則令 ， (2-17)為使與共軛，選擇，滿足共軛條件 ， ， (2-18)將式(2-17)代入式(2-18)并利用共軛性，可得 . (2-19)在式(2-17)中，令，并且寫成，由定理2.4可知 ， . (2-20)接下來我們要證明，在式(2-19)中 ， (2-21)與 成立，即對任一均有式(2-12)的只含兩項的簡

50、單結構.類似式(2-10)和式(2-16)，我們有 及 . (2-22)由此可得 ，由式(2-20)及上式，便可得到 ，. 這一重要性質(zhì)，使得我們在求各時避免了式(2-17)中的繁復計算，每次產(chǎn)生的共軛方向只由處的與兩項組成，從而得到了結構簡單的共軛梯度法.下面給出組合系數(shù)的另一種公式表示.由于，所以 .在式(2-17)中，應用的表達式，即 再由定理2.4，可得 ， 從而得到公式(2-21) (2-23)又由式(2-20)，這樣便可得到由Fletcher-Reeves給出的公式(簡稱FR公式) (2-24)如上，采用FR公式的共軛梯度法，稱為Fletcher-Reeves共軛梯度法. 共軛梯度

51、法的算法步驟根據(jù)不同的函數(shù)結構，我們會得出不同的共軛梯度算法，而利用共軛梯度法求解二次凸函數(shù)的最小點，在我們的理論學習中最常見而且應用相當熟練.下面我們給出共軛梯度法求二次凸函數(shù)的最小點的算法步驟.步驟1 任取初始點，令 ，轉步驟3.步驟2 對，計算及， ， (2-25)步驟3 線性搜索求步長： .令.步驟4 若，則計算結束，.否則轉步驟5.步驟5 令，轉回步驟2. 共軛梯度法的優(yōu)點近年來，隨著計算機的飛速發(fā)展和實際問題中大規(guī)模優(yōu)化問題的涌現(xiàn)，再加上共軛梯度法具有相當多的優(yōu)點，使得尋找快速有效的共軛梯度法成為了學者們研究的熱門方向之一.主要優(yōu)點有：(1)共軛梯度法不僅克服了最速下降法收斂慢的缺

52、點，又避免了牛頓法需要存儲和計算Hesse矩陣并求逆的缺點，使得共軛梯度法已成為解大型非線性最優(yōu)化最有效的算法之一.(2)共軛梯度法是一個典型的共軛方向法，它的每一個搜索方向是互相共軛的，而這些搜索方向d僅僅是負梯度方向與上一次迭代的搜索方向的組合，因此，共軛梯度法具有存儲量少、計算方便的優(yōu)點.(3)共軛梯度法不需要矩陣存儲，所以它具有較快的收斂速度和二次終止性等優(yōu)點.2.3 算法實例我們知道，共軛梯度法是在每一迭代步利用當前點處的最速下降方向來生成二次函數(shù)的Hesse矩陣的共軛方向，并建立求在上的極小點的方法.所以我們要先生成共軛方向，再建立求解方法.例1 ，為，求共軛方向，.解 由題可知，

53、取初始點，由，得，.然后求從出發(fā)沿方向的線性最優(yōu)步長： .令，因而 .由定理2.5可知，解得.所以有 .計算處的和，有 ， .因而.由上可知共軛方向，.從上面的例子中，我們可以很容易的得到二元二次方程共軛方向的求解過程，而對于三次以上的方程，由于計算復雜，在此不列出詳細求解過程.接下來我們都將討論二元二次方程的求解過程，從簡單的求解過程當中理解什么是共軛梯度法，以及如何熟練的應用共軛梯度法求解，這些即是本文的主要目的.下面給出的例子，詳細給出了共軛梯度法的全部求解過程，并最終求得方程的最小解.而且這個例子將被用在第四章，作為MATLAB編程的算法實例.例2 用共軛梯度法求的最小解.解 取初始點

54、，由，得 ，.然后求從出發(fā)沿方向的線性最優(yōu)步長： .令，因而 .由定理2.5可知，解得.所以有 .計算處的和，有 ， .因而 .求從出發(fā)沿方向的線性最優(yōu)步長.令 ， (2-26)將的表達式代入中，得 =.同樣的有 ，解得 .再將的值代入式（2-26），可得 .以代入中，得， .值得注意的是，在共軛梯度法中，初始方向應取最速下降方向，否則產(chǎn)生的方向不一定是共軛方向.例3 用共軛梯度法求的最小點.解 取初始點，由題可知，取初始方向，令，則.從方程中，解出沿的步長.因而 ，.由于，可得.接下來驗證.取，因而可得 .這說明與對不共軛，從出發(fā)沿方向求解也得不到的最小點.這個例子充分解釋了，在選取初始方向

55、時，應取最速下降方向，否則產(chǎn)生的方向不一定是共軛方向.第三章 算法的收斂性本章主要分兩部分，第一部分先給出共軛梯度法的一些性質(zhì)和收斂性定理；然后第二部分則是分析算法的收斂性，通過總結已有學者的研究結果，證明該算法在一定條件下具有全局收斂性. 共軛梯度法的性質(zhì)與收斂性定理 共軛梯度法的性質(zhì)定理 對于二次凸函數(shù)，若用共軛梯度法求解且采用線性最優(yōu)步長，則算法對任一迭代步，有下述關系式成立： ， ， (3-1) ， ， (3-2) ， (3-3)且算法最多步便可求得的最小點. 證明 利用歸納法.由共軛梯度法的計算公式，若初始點為，則取初始方向，又由步長采用精確線性搜索求得，因而步長滿足關系即.由，的選

56、擇使，即式(3-1)的定義，當時式(3-3)時式(3-1)，(3-2)，(3-3)均成立.現(xiàn)設對于任一迭代步，式(3-1)式(3-3)均成立，要證時，它們也成立.由式(2-5)可得 ， . (3-4)下面證明式(3-1)和式(3-2)當(3-4)和式(2-25)，可得 (3-5)又由的定義，以及在式(3-4)中，令，可得 . (3-6) 由歸納假設，式(3-1)式(3-3)，當時成立，因而式(3-5)與式(3-6)的右端都為零，即 , ,， (3-7)成立，亦即式(3-1)和式(3-2)當時對也成立.當時，式(3-5)可寫成 .對于，我們在式(3-4)中兩邊乘，注意到，將解出，利用式(3-3)

57、的歸納假設，可得的另一個表達式 . (3-8)將此式代入上式，可得 (3-9)成立，即式(3-2)對成立.對于式(3-1)，當時，式(3-6)變?yōu)?，利用式(3-8)以及的FR公式，可知 (3-10)成立，亦即式(3-1)成立.對于式(3-3)，當時，由的定義及精確搜索，可得. (3-11)因而上述式(3-9)式(3-11)當時也成立，這就充分證明了式(3-1)式(3-3)當時也成立. 共軛梯度法的收斂性定理前面我們已經(jīng)簡要給出了FR共軛梯度法，下面我們簡述一下FR共軛梯度法應用于極小化非二次函數(shù)時，在精確一維搜索與非精確強Wolfe搜索下的收斂性問題.因此，現(xiàn)在我們要引用一維搜索與強Wolf

58、e搜索的基本概念.在迭代算法求步長的計算中，要有充分下降性要求，否則當移動步長很小時，點與點很接近，函數(shù)值與的有效方法.令 ，若使的方法，稱為一維搜索方法. 一維搜索方法有多種，下面介紹兩種常用的方法.(1)線性最優(yōu)步長 在式()中求()的最小點或第一個極小點對于的步長.這種方法是理論上的，常在理論論證中使用，稱為精確線性搜索.而且在上章的算法實例中都使用了該方法求線性最優(yōu)步長.(2)Wolfe方法給定數(shù)，.求使下列兩個不等式 ， (3-12) (3-13)(3-13)有時也可用更強的條件 (3-14)(3-12)和條件(3-14)則稱為強Wolfe充分小，則式(3-14)就變成了近似精確線性

59、搜索.接下來是給出共軛梯度法的一些收斂性定理，同樣是針對FR共軛梯度法.對于FR共軛梯度法，對于當前點，令 ， ， (3-15)其中的組合系數(shù) ，. (3-16)作一維搜索求，令 ， (3-17)重復上述計算.算法停止規(guī)則，可取.定理 （FR共軛梯度法的收斂性定理）設連續(xù)可微，水平集有界，則當FR算法采用一維精確搜索應用于極小化時，若產(chǎn)生的迭代點列為，則有以下結論：(1)若為有窮點列，則其最后一點為的穩(wěn)定點.(2)若為無窮點列，則其任一極限點是的穩(wěn)定點. 證明 (1)當為有限點列時，由停止規(guī)則可知，點列的最后一點有，因而為的穩(wěn)定點或近似穩(wěn)定點.(2)若為無窮點列，則有與.由式(3-15)及一維

60、搜索性質(zhì)可得 ，是在處的一個下降方向，因而 ，是單調(diào)下降序列且點列.由水平集合有界，可知為有界序列且必有極限點存在.設極限點為，則存在的子列，使得 .因為，所以.由的連續(xù)性,可知對于，有 .同理，也是有界點列，因而有極限點及子列，當時， ， . 于是，我們得到 . (3-18)接下來證明.用反證法，設，并令，則在處，對于充分小的，有 成立.由一維精確搜索， ，因而，對，當時，由上面的結果可得 ，此式與式(3-18)矛盾，即.從而證明了極限點為穩(wěn)定點.當FR方法采用強Wolfe非精確搜索時，又有如下的收斂性定理.定理3.3 設二階連續(xù)可微，水平集有界，步長采用強Wolfe非精確搜索，且，則對FR