肖畢業(yè)論文(改)

1、2011年度本科生畢業(yè)論文(設(shè)計)一種新的全局收斂的共軛梯度算法院 系： 數(shù)學(xué)學(xué)院 專 業(yè)： 信息與計算科學(xué) 年 級： 2007級 學(xué)生姓名： 肖文真 學(xué) 號： 200705050318 導(dǎo)師及職稱：曹香蓮（助教）何斌（教授） 2011年5月2011Annual Graduation Thesis (Project) of the College Undergraduate Global Convergence of A New Kind of Conjugate Gradient MethodDepartment: College of Mathematics Major: Informat

2、ion and Computation Science Grade: 2007Students Name: Xiao WenzhenStudent No.: 200705050318Tutor: Cao Xianglian（Assistant）He Bin（Professor） Finished by May, 2011畢業(yè)論文（設(shè)計）原創(chuàng)性聲明本人所呈交的畢業(yè)論文（設(shè)計）是我在導(dǎo)師的指導(dǎo)下進行的研究工作及取得的研究成果。據(jù)我所知，除文中已經(jīng)注明引用的內(nèi)容外，本論文（設(shè)計）不包含其他個人已經(jīng)發(fā)表或撰寫過的研究成果。對本論文（設(shè)計）的研究做出重要貢獻的個人和集體，均已在文中作了明確說明并表示謝意

3、。 作者簽名： 日期： 畢業(yè)論文（設(shè)計）授權(quán)使用說明本論文（設(shè)計）作者完全了解紅河學(xué)院有關(guān)保留、使用畢業(yè)論文（設(shè)計）的規(guī)定，學(xué)校有權(quán)保留論文（設(shè)計）并向相關(guān)部門送交論文（設(shè)計）的電子版和紙質(zhì)版。有權(quán)將論文（設(shè)計）用于非贏利目的的少量復(fù)制并允許論文（設(shè)計）進入學(xué)校圖書館被查閱。學(xué)校可以公布論文（設(shè)計）的全部或部分內(nèi)容。保密的論文（設(shè)計）在解密后適用本規(guī)定。   作者簽名： 指導(dǎo)教師簽名：日期： 日期： 肖文真 畢業(yè)論文（設(shè)計）答辯委員會(答辯小組)成員名單姓名職稱單位備注副教授紅河學(xué)院數(shù)學(xué)學(xué)院主席（組長）副教授紅河學(xué)院數(shù)學(xué)學(xué)院馮祖針助 教紅河學(xué)院數(shù)學(xué)學(xué)院李 燦助 教紅河學(xué)院數(shù)學(xué)學(xué)院曹香

4、蓮 助 教紅河學(xué)院數(shù)學(xué)學(xué)院紅河學(xué)院本科畢業(yè)論文 (設(shè)計)摘 要本文給出了一種新的求解非線性無約束優(yōu)化問題的共軛梯度算法該算法允許初始點任意，在推廣的強Wolfe線搜索下具有下降性，并且在適當?shù)臈l件下具有全局收斂性關(guān)鍵詞：無約束最優(yōu)化；共軛梯度法；下降性；線搜索；全局收斂性ABSTRACT A new nonlinear conjugate gradient type formula for unconstrained optimization problems is presentedThe algorithm allows initial point is at random, the me

5、thod satisfies the descent condition in the condition of generalized strong wolfe steplength，and it has global convergence under the suitable conditionsKeywords：unconstrained optimization；conjugate gradient method；descent property；line search；global convergence目 錄第一章 引言1第二章 共軛梯度算法4第三章 下降條件5第四章 全局收斂性

6、7第五章 結(jié)束語9參考文獻10致謝12紅河學(xué)院本科畢業(yè)論文 (設(shè)計)第一章 引言 本文主要考慮無約束最優(yōu)化問題 (1-1)其中為上的連續(xù)可微函數(shù)共軛梯度算法是用來求解無約束優(yōu)化問題(1-1)的一種方法，其迭代格式是 (1-2) (1-3)其中，為搜索方向，為的梯度，為某種參數(shù)共軛梯度法最早是1952年由計算數(shù)學(xué)家 Hestenes和幾何學(xué)家Stiefel為求解線性方程組，時提出的由于解線性方程組等價于求解極小化的正定二次函數(shù)，因此，他們提出的方法也可視為求二次函數(shù)極小值的共軛梯度法1964年，F(xiàn)letcher和Reeves將此方法推廣到非線性優(yōu)化，得到了求解一般函數(shù)極小值的共軛梯度算法共軛梯度

7、算法是最優(yōu)化理論中最常用的方法之一，它具有算法簡單，存儲需求小等優(yōu)點，十分適合大規(guī)模優(yōu)化問題石油勘探、大氣模擬、航天航空等領(lǐng)域出現(xiàn)的特大規(guī)模的優(yōu)化問題常常利用共軛梯度算法求解符號說明：表示上的歐式范數(shù)，是f的梯度函數(shù)在點的值是由算法產(chǎn)生的點列若為當前的迭代點，則記為非線性共軛梯度算法的基本步驟4(1) 給出初始值；(2) 如果,則停;否則利用某種搜索方法求;令；(3) 利用某種公式計算參數(shù),z轉(zhuǎn)步(2)； 可由精確線搜索求得但在實際計算中精確線搜索要求準確度高，計算量較大，故實際計算中常常進行非精確線搜索 在應(yīng)用中可由非精確線搜索求得： (1) 弱Wolfe-powell規(guī)則 尋找一個，滿足

8、， ， (2) 強Wolfe-powell規(guī)則 尋找一個，滿足， (1-4) ， (1-5) (3) Armijo規(guī)則尋找一個，其中，是最小的正整數(shù)，滿足，.(4) Armijo-Goldstein規(guī)則尋找一個，滿足， (5) 推廣的Wolfe準則 尋找一個，滿足，上式中，為常數(shù)，且不同的對應(yīng)不同的共軛梯度算法著名的共軛梯度法有：, FR方法在計算方面的表現(xiàn)并不十分理想，但采用精確先搜索時可是證明FR方法對一般的非凸函數(shù)總是收斂的.而采用強Wolfe線搜索的FR方法只要每一步的搜索方向下降，則此方法可以在適當?shù)暮瘮?shù)假定下全局收斂.PRP方法是目前認為數(shù)值表現(xiàn)最好的共軛梯度算法之一，當算法產(chǎn)生一

9、個小步長時，由PRP方法定義的搜索方向自動靠近負梯度方向，從而較為有效地避免了FR方法可能連續(xù)產(chǎn)生小步長的缺點.CD方法的一個很重要的一個性質(zhì)是：只要強Wolfe條件(1-4)和(1-5)條件中的參數(shù)方法在每次迭代均產(chǎn)生一個下降方向，而這時FR方法和PRP方法對一致凸函數(shù)都有可能產(chǎn)生上升搜索方向.雖然CD方法在Wolfe線搜索時能夠保證每個搜索方向都下降，但全局收斂性不好，Dai和Yuan在文獻5中嚴格證明了采用強Wolfe線搜索的DY方法在每一步產(chǎn)生一個下降方向，并且證明了該方法的全局收斂性.文獻6對共軛下降法的收斂性做了進一步的分析；文獻7-10對共軛下降法的作了改進，得到了包含共軛下降法

10、的一類無約束優(yōu)化方法，并證明了全局收斂性；文獻11-20對FR方法的作了改進，得到了一類新的共軛梯度法并證明了全局收斂性鑒于上述文獻及其他相關(guān)文獻的思路，本文給出了一個新的： (1-6) 其中 當?shù)玫搅诵碌墓曹椞荻确?，并證明了其在適當條件下的全局收斂性1 第一章 引言第二章 共軛梯度算法第2章 共軛梯度算法本文對目標函數(shù)作如下假設(shè)：(1)在上連續(xù)可微有界；(2)的梯度函數(shù)是Lipschitz連續(xù)的，即存在，使得： 采用推廣的Wolfe準則確定步長，即要求滿足： (2-1) (2-2)式(2-1)和(2-2)中，為常數(shù)，且取，即： (2-3) 本文收斂性采用搜索條件(2-1)和(2-3)具有下降

11、性的共軛梯度算法如下：(1)，令，若，則停；否則，轉(zhuǎn)(2)；(2) 令，滿足(2-1)和(2-3)；(3) 計算，若，則停；否則令，轉(zhuǎn)(4)；(4) 令，其中滿足(1-6)，轉(zhuǎn)(2)注：文獻13中非精確線搜索條件保證的存在性 紅河學(xué)院本科畢業(yè)論文 (設(shè)計)第3章 下降條件 定理3.1 在假設(shè)成立的條件下，考慮共軛梯度法式(1-1)、(1-2)、(1-3)如果步長滿足條件(2-1)和(2-2)，當取(1-6)式時，則算法對所有的k1，有下降性質(zhì) 證明：當時，即，有假設(shè)當k=k-1時，有 (3-1)由于所以有 其中 所以，得證 定理3.2 在假設(shè)成立的條件下，考慮迭代格式(1-2)、(1-3),步

12、長由(2-1)、(2-2)求出，則有 證明: 由，知 ，k=1,2由(2-2)式及Lipschitz條件有， 所以 . (3-2) 其中 由的收斂性及(3-2)式知，結(jié)論成立.3 紅河學(xué)院本科畢業(yè)論文 (設(shè)計)第4章 全局收斂性定理 4.1 假設(shè)成立的條件下，考慮共軛梯度法式(1-1)、(1-2)和(1-3) ，如果步長滿足條件(2-1)和(2-3)，參數(shù)取值滿足，則算法產(chǎn)生的迭代點列或?qū)δ硞€有下式成立： 證明：用反證法，若定理不成立，即存在c>0，使,k=1,2由 (4-1)將(4-1)式兩邊取模平方，得 (4-2)又由(3-1)式得 由(2-3)知,所以所以 得將代入(4-2)式得兩

13、邊同除以可得： 由上式遞推可得即與定理(3-2)矛盾，所以全局收斂性得證紅河學(xué)院本科畢業(yè)論文 (設(shè)計)紅河學(xué)院本科畢業(yè)論文 (設(shè)計)第五章 結(jié)束語本文主要討論了無約束優(yōu)化問題的算法，給出了一個新的，即構(gòu)造了一個新的共軛下降方向，從而得到一類新的共軛梯度算法，且該算法允許初始點任意，并且具有全局收斂性共軛梯度算法是常用的求解無約束優(yōu)化問題的有效方法，進一步對它深入研究能否得到更好的混合算法，這是值得研究的由于時間和本人水平有限，本論文提出的算法沒有給出具體的數(shù)值試驗，這是進一步要做的工作參考文獻1 Hestenes M R. Iterative method for solving linear

14、 equationsJ. JOTA, 1973, 11(4):323-3342 Stiefel E. Uber einige methoden der relaxationsrechnungJ. Zeitschrift für Angewandte Mathematik und Physik , 1952, 1(3): 1-333 Fletcher R, Reeves C M. Function minimization by conjugate gradientsJ. Compute Journal, 1964, 7(2): 149-1544 Hestenes M R. Itert

15、ive method for solving linear equation,NANLReport No 53-9,National Bureau of Standards,Washington D.C. 1973，1:322-3345 Dai Y H,Yuan Y.A nonlinear conjugate gradient method with a strong global convergence property J.SIAM Journal on Optimization,1999，10(1):177-1826 Fletcher R. Practical methods of op

16、timization: vol. 2: Constrained Optimization M, New York: John Wiley & Sons, 19817 Dai Y H, Yuan Y X. Convergence properties of the conjugate descentmethodJAdvances in Mathematics(In Chinese), 1996, 25(6):552-562 8 徐澤水. A class of new conjugate gradient methodsJ. 數(shù)學(xué)志,2002, 5(1):27-309 杜學(xué)武. 一類新共軛

17、下降算法的全局收斂性J數(shù)學(xué)的實踐與認識, 2002, 32 (1):153-15710 焦寶聰, 陳蘭平. 一類新共軛下降算法的全局收斂性J數(shù)學(xué)的實踐與認識,，1998, 28(3):193-19611 杜學(xué)武, 葉留青, 徐成賢包含共軛下降法的一類無約束優(yōu)化方法的全局收斂性J工程數(shù)學(xué)學(xué)報, 2001, 18(2):119-12112 柳娟, 謝鐵軍, 孫玉華. 一類共軛梯度法的全局收斂性J運籌與管理, 2007, 16(2):75-7813 范建芬, 謝鐵軍, 柳娟. 一族新的共軛梯度法的全局收斂性J運籌與管理, 2007, 16(2):65-6814 高麗, 謝鐵軍. Wolfe線搜索下新

18、的共軛梯度法的全局收斂性J運籌與管理, 2008, 2(1):38-4115 陳巖, 陳忠. 無約束優(yōu)化問題的一種新共軛梯度法的全局收斂性J自然科學(xué)報, 2009, 6(2):129-13116 袁亞湘, 孫文瑜. 最優(yōu)化理論與方法M. 北京:科學(xué)出版社,200617 Al-Baali M.Descent property and global convergence of the Flecher-Reeves method with inexact line searchJ.IMA,Journal of Numerical Analysis,1985, 5(1): 121-12418 Yu

19、G.H,zhao Y.L.and Wei Z.X.A descent nonlinear conjugate gradient formulas for large-scale unconstrained optimization problemsJ.Apll.Mput, 2006,179:407-43019 Yu G.H.,zhao Y.L.and Wei Z.X.A descent nonlinear conjugate method for large s- -cale unconstrained optimizationJ.J.Apll.Math.Comput,2007,187:636-64320 陳繼紅，焦寶聰.一種新的非線性共軛梯度算法的全局收斂性J.首都師范 大學(xué)學(xué)報(自然科學(xué)版),2006,27(3):1-4致謝 畢業(yè)論文暫告收尾, 這也意味著我在紅河學(xué)院四年的學(xué)習(xí)生活既將結(jié)束. 回首既往，自己一生最寶貴的時光能于這樣的校園之中,能在眾