肖畢業(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: Info

2、rmation 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ìn)行的研究工作及取得的研究成果。據(jù)我所知，除文中已經(jīng)注明引用的內(nèi)容外，本論文（設(shè)計）不包含其他個人已經(jīng)發(fā)表或撰寫過的研究成果。對本論文（設(shè)計）的研究做出重要貢獻(xiàn)的個人和集體，均已在文中作了明

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è)計）進(jìn)入學(xué)校圖書館被查閱。學(xué)?？梢怨颊撐模ㄔO(shè)計）的全部或部分內(nèi)容。保密的論文（設(shè)計）在解密后適用本規(guī)定。 作者簽名： 指導(dǎo)教師簽名：日期： 日期： 推薦精選肖文真 畢業(yè)論文（設(shè)計）答辯委員會(答辯小組)成員名單姓名職稱單位備注副教授紅河學(xué)院數(shù)學(xué)學(xué)院主席（組長）副教授紅河學(xué)院數(shù)學(xué)學(xué)院馮祖針助 教紅河學(xué)院數(shù)學(xué)學(xué)院李 燦助 教紅河學(xué)院數(shù)

4、學(xué)學(xué)院曹香蓮 助 教紅河學(xué)院數(shù)學(xué)學(xué)院推薦精選推薦精選摘 要本文給出了一種新的求解非線性無約束優(yōu)化問題的共軛梯度算法該算法允許初始點(diǎn)任意，在推廣的強(qiáng)Wolfe線搜索下具有下降性，并且在適當(dāng)?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,

5、the method 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第三章 下降條件

6、5第四章 全局收斂性7第五章 結(jié)束語9參考文獻(xiàn)10致謝12推薦精選推薦精選推薦精選第一章 引言 本文主要考慮無約束最優(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)點(diǎn)，十分適合大規(guī)模優(yōu)化問題石油勘探、大氣模擬、航天航空等領(lǐng)域出現(xiàn)的特大規(guī)模的優(yōu)化問題常常利用共軛梯度算法求解符號說明：表示上的歐式范數(shù)，是f的梯度函數(shù)在點(diǎn)的值是由算法產(chǎn)生的點(diǎn)列若為當(dāng)前的迭代點(diǎn)，則記為非線性共軛梯度算法的基本步驟4(1) 給出初始值；(2) 如果,則停;否則利用某種搜索方法求;令；(3) 利用某種公式計算參數(shù),z轉(zhuǎn)步(2)； 可由精確線搜索求得但在實(shí)際計算中精確線搜索要求準(zhǔn)確度高，計算量較大，故實(shí)際計算中常常進(jìn)行非精確線搜索推薦精選 在應(yīng)用中可由非精確線搜索求得： (1) 弱Wolfe-powell

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

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

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

11、(2-3)具有下降性的共軛梯度算法如下：(1)，令，若，則停；否則，轉(zhuǎn)(2)；(2) 令，滿足(2-1)和(2-3)；(3) 計算，若，則停；否則令，轉(zhuǎn)(4)；(4) 令，其中滿足(1-6)，轉(zhuǎn)(2)注：文獻(xiàn)13中非精確線搜索條件保證的存在性 推薦精選推薦精選第3章 下降條件 定理3.1 在假設(shè)成立的條件下，考慮共軛梯度法式(1-1)、(1-2)、(1-3)如果步長滿足條件(2-1)和(2-2)，當(dāng)取(1-6)式時，則算法對所有的k1，有下降性質(zhì) 證明：當(dāng)時，即，有假設(shè)當(dāng)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é)論成立.推薦精選第4章 全局收斂性定理 4.1 假設(shè)成立的條件下，考慮共軛梯度法式(1-1)、(1-2)和(1-3) ，如果步長滿足條件(2-1)和(2-3)，參數(shù)取值滿足，則算法產(chǎn)生的迭代點(diǎn)列或?qū)δ硞€有下式成立： 證明：用反證法，若定理不成立，即存在c0，使,k=1,2由 (4-1)將(4-1)式兩邊取模平方，得 (4-2)又由(3-1)式得 由(2-3)知,所以所以 得將代入(4-2)式得兩邊同除以可得：推薦精選

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

14、11(4):323-3342 Stiefel E. Uber einige methoden der relaxationsrechnungJ. Zeitschrift fr 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. Itertive method for solving linear e

15、quation,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 optimization: vol. 2: Constrained

16、 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é)武. 一類新共軛下降算法的全局收斂性J數(shù)學(xué)的實(shí)踐與認(rèn)識, 2002, 32 (1):1

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

18、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 G.H,zhao Y.L.and Wei Z.X.A desc

19、ent 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é)束. 回首既往，自己一生最寶貴的時光能于這樣的校園之中,能在眾多學(xué)富五車、才華橫溢的老師們的熏陶下度過，實(shí)是榮幸之極.在這四年的時