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

1、2011年度本科生畢業(yè)論文(設(shè)計(jì))一種新的全局收斂的共軛梯度算法院 系： 數(shù)學(xué)學(xué)院 專(zhuān) 業(yè)： 信息與計(jì)算科學(xué) 年 級(jí)： 2007級(jí) 學(xué)生姓名： 肖文真 學(xué) 號(hào)： 200705050318 導(dǎo)師及職稱(chēng)：曹香蓮（助教）何斌（教授） 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è)計(jì)）原創(chuàng)性聲明本人所呈交的畢業(yè)論文（設(shè)計(jì)）是我在導(dǎo)師的指導(dǎo)下進(jìn)行的研究工作及取得的研究成果。據(jù)我所知，除文中已經(jīng)注明引用的內(nèi)容外，本論文（設(shè)計(jì)）不包含其他個(gè)人已經(jīng)發(fā)表或撰寫(xiě)過(guò)的研究成果。對(duì)本論文（設(shè)計(jì)）的研究做出重要貢獻(xiàn)的個(gè)人和集體，均已在文中作了明確說(shuō)明并表示謝意

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

4、蓮 助 教紅河學(xué)院數(shù)學(xué)學(xué)院紅河學(xué)院本科畢業(yè)論文 (設(shè)計(jì))摘 要本文給出了一種新的求解非線性無(wú)約束優(yōu)化問(wèn)題的共軛梯度算法該算法允許初始點(diǎn)任意，在推廣的強(qiáng)Wolfe線搜索下具有下降性，并且在適當(dāng)?shù)臈l件下具有全局收斂性關(guān)鍵詞：無(wú)約束最優(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é)束語(yǔ)9參考文獻(xiàn)10致謝12紅河學(xué)院本科畢業(yè)論文 (設(shè)計(jì))第一章 引言 本文主要考慮無(wú)約束最優(yōu)化問(wèn)題 (1-1)其中為上的連續(xù)可微函數(shù)共軛梯度算法是用來(lái)求解無(wú)約束優(yōu)化問(wèn)題(1-1)的一種方法，其迭代格式是 (1-2) (1-3)其中，為搜索方向，為的梯度，為某種參數(shù)共軛梯度法最早是1952年由計(jì)算數(shù)學(xué)家 Hestenes和幾何學(xué)家Stiefel為求解線性方程組，時(shí)提出的由于解線性方程組等價(jià)于求解極小化的正定二次函數(shù)，因此，他們提出的方法也可視為求二次函數(shù)極小值的共軛梯度法1964年，F(xiàn)letcher和Reeves將此方法推廣到非線性?xún)?yōu)化，得到了求解一般函數(shù)極小值的共軛梯度算法共軛梯度

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

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

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

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

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

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

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

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

18、的共軛梯度法的全局收斂性J運(yùn)籌與管理, 2008, 2(1):38-4115 陳巖, 陳忠. 無(wú)約束優(yōu)化問(wèn)題的一種新共軛梯度法的全局收斂性J自然科學(xué)報(bào), 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é)報(bào)(自然科學(xué)版),2006,27(3):1-4致謝 畢業(yè)論文暫告收尾, 這也意味著我在紅河學(xué)院四年的學(xué)習(xí)生活既將結(jié)束. 回首既往，自己一生最寶貴的時(shí)光能于這樣的校園之中,能在眾