（運(yùn)籌學(xué)與控制論專(zhuān)業(yè)論文）混合非線性共軛梯度算法研究.pdf

大連理工大學(xué)碩士學(xué)位論文：混合非線性共軛梯度算法研究 摘要 非線性共軛梯度算法是最優(yōu)化方法的一個(gè)重要的組成部分在自然科學(xué)，生產(chǎn)實(shí)際， 工程設(shè)計(jì)和現(xiàn)代化管理中有著重要的實(shí)用價(jià)值 本文對(duì)近年來(lái)受關(guān)注的混合非線性共軛梯度算法的理論性質(zhì)進(jìn)行了研究，主要研究 結(jié)果歸納如下： 1 第二章給出了一個(gè)非線性共軛梯度算法在w o l f e 線搜索下全局收斂性的判別準(zhǔn)則 2 第二章還提出了一類(lèi)三參數(shù)共軛梯度法簇，并利用給出的判別準(zhǔn)則證明了此類(lèi)三參 數(shù)共軛梯度法簇和d y 方法一個(gè)變形的混合共軛梯度算法在w o l f e 線搜索下或修正 的w o l f e 線搜索下的全局收斂性 3 第三章對(duì)兩篇文獻(xiàn)中給出的收斂性結(jié)果在w o l f e 線搜索下或廣義、v o l f e 線搜索下進(jìn) 行了拓展 關(guān)鍵詞： 非線性共軛梯度算法，最優(yōu)化，全局收斂性，三參數(shù)共軛梯度法簇，d y 方 法，w o l f e 線搜索 大連理工大學(xué)碩士學(xué)位論文：混合非線性共軛梯度算法研究 a b s t r a c t n o n l i n e a rc o n j u g a t eg r a d i e n ta l g o r i t h m ( n c g ) i sa ni m p o r t a n tc o m p o n e n to fo p t i n f i z a t i o nm e t h o d s ，w h i c hc a nb ea p p l i e dt on a t u r a ls c i e n c e ，p r a c t i c a lm a n u f a c t i o n ，e n g i n e e r i n gd e s i g n ，m o d e r nm a n a g e m e n ta n de t c t h i sp a p e rm a i n l ys t u d i e st h et h e o r i t i c a l p r o p r i t i e so fn o n l i n e a rc o n j u g a t eg r a d i e n tm e t h o d t h em a i nr e s u l t so b t a i n e di n t h i s d i s s e r t a t i o nm a yb es u m m a r i z e da sf o l l o w s ： 1 c h a p t e r2p r e s e n t sac r i t e r i o no fg l o b a lc o n v e r g e n c eo ft h en o n l i n e a rc o n j u g a t eg r a d i e n t m e t h o du n d e rt h e ，0 l f el i n es e a r c hc o n d i t i o n 2 c h a p t e r2a l s og i v e saf a m i l yo ft h r e ep a r a m e t e rc o n j u g a t eg r a d i e n tm e t h o d t h e g l o b a lc o n v e r g e n c ep r o p e r t yo ft h ef a m i l ya n dac h a n g ef o r mo ft h ed ym e t h o da r e p r o v e du n d e rt h e ，o l f el i l l es e a r c hc o n d i t i o no rm o d i f i e d ，0 f i el i n es e a r c hc o n d i t i o n v i at h ec r i t e r i o nw eh a v ep r e s e n t e d 3 c h a p t e r3e x t e n d st h er e s u l t so ft w or e f e r e n c e su n d e rt h e ，0 l f el i n es e a r c hc o n d i t o n o rt h eg e n e r l i z e d ，o l f el i n es e a r c hc o n d i t o n k e yw o r d s ： n o n l i n e a rc o n j u g a t eg r a d i e n t m e t h o d ，o p t i m i z a t i o n ，g l o b a l c o n v e r g e n c e ，af a m i l yo ft h r e ep a r a m e t e rc o n j u g a t eg r a d i e n tm e d h o d ，d y m e t h o d ，o l f el i n es e a r c hc o n d i t i o n l l 大連理工大學(xué)碩士學(xué)位論文：混合非線性共軛梯度算法研究 獨(dú)創(chuàng)性說(shuō)明 作者鄭重聲明：本碩士學(xué)位論文是我個(gè)人在導(dǎo)師指導(dǎo)下進(jìn)行的研究工作 及取得研究成果。盡我所知，除了文中特別加以標(biāo)注和致謝的地方外，論文 中不包含其他人已經(jīng)發(fā)表或撰寫(xiě)的研究成果，也不包含為獲得大連理工大學(xué) 或其他單位的學(xué)位或證書(shū)所使用過(guò)的材料。與我一同工作的同志對(duì)本研究所 做的貢獻(xiàn)均已在論文中做了明確的說(shuō)明并表示了謝意。 作者簽名：堂宣垂 日期：2 0 0 5 年6 月 1 緒論 這一章首先介紹非線性共軛梯度算法的產(chǎn)生背景及其發(fā)展?fàn)顩r，并著 重介紹了幾種經(jīng)典的共軛梯度算法的理論和數(shù)值特點(diǎn)之后，介紹了混合 共軛梯度算法的產(chǎn)生及其在求解非線性無(wú)約束優(yōu)化問(wèn)題方面的研究進(jìn)展 并介紹了了本文的主要工作 1 1 引言 最優(yōu)化理論及方法的起源可以追溯到微積分誕生的年代然而，直到本世紀(jì)三四十 年代，由于軍事和工業(yè)生產(chǎn)等方面的迫切需要，才使得最優(yōu)化技術(shù)得到了蓬勃發(fā)展后 來(lái)，又由于電子計(jì)算機(jī)的問(wèn)世使得進(jìn)行優(yōu)化計(jì)算的費(fèi)用大幅度下降，于是各種優(yōu)化模型 ( 如線性規(guī)劃，二次規(guī)劃，非線性規(guī)劃，多目標(biāo)規(guī)劃等) 以及相應(yīng)的各種數(shù)值優(yōu)化算法( 如 單純形法，共軛梯度法，變尺度法，罰函數(shù)法，目標(biāo)規(guī)劃法等) 得以在經(jīng)濟(jì)計(jì)劃，工程設(shè) 計(jì)，生產(chǎn)管理，交通運(yùn)輸?shù)阮I(lǐng)域得到了廣泛的應(yīng)用【勰】【4 9 】 共軛梯度法是最優(yōu)化中最常用的方法之一它具有算法簡(jiǎn)單，存儲(chǔ)需求小，易于實(shí) 現(xiàn)等優(yōu)點(diǎn)，十分適合于大規(guī)模優(yōu)化問(wèn)題在石油勘探，大氣模擬，航天航空等領(lǐng)域出現(xiàn)的 優(yōu)化問(wèn)題常常是利用共軛梯度法求解的【5 0 】 本文的內(nèi)容屬于方法研究，對(duì)近年來(lái)備受關(guān)注的最優(yōu)化方法中的共軛梯度算法的理 論性質(zhì)進(jìn)行了研究 1 2 非線性共軛梯度算法研究進(jìn)展 非線性共軛梯度算法已有五十多年的歷史它最早是由h e s t e n e s 和s t i e f e l 于1 9 5 2 年在求解線性方程組時(shí)提出的口q ，并由f l e t c h e r 和r e e v e s 于1 9 6 4 年推廣到非線性優(yōu)化 領(lǐng)域【1 6 j 隨后，b e a l e ，f l e t c h e r ” ，p o w e l l 2 q 等著名優(yōu)化專(zhuān)家對(duì)非線性共軛梯度算法進(jìn) 行了深入研究，取得了十分優(yōu)秀的成果但幾乎同時(shí)問(wèn)世的擬牛頓方法由于其良好的計(jì) 算表現(xiàn)以及豐富的收斂性分析很快受到了青睞，從而在很長(zhǎng)一段時(shí)間里共軛梯度算法被 研究者所忽視近年來(lái)，隨著計(jì)算機(jī)的飛速發(fā)展以及實(shí)際問(wèn)題的需要，大規(guī)模優(yōu)化問(wèn)題 越來(lái)越受到重視而共軛梯度算法正是求解大規(guī)模問(wèn)題的一種主要方法，這屜因?yàn)楣曹?梯度法具有算法簡(jiǎn)單，易于編程以及需要存儲(chǔ)空聞小等優(yōu)點(diǎn)于是共軛梯度算法的理論 大連理工大學(xué)碩士學(xué)位論文：混合非線性共軛梯度算法研究 研究和應(yīng)用研究又受到了人們的關(guān)注 共軛梯度算法是用于求解大規(guī)模無(wú)約束非線性規(guī)劃的一類(lèi)有效算法在所有需要計(jì) 算梯度的優(yōu)化方法中，最速下降法是最簡(jiǎn)單的，但在實(shí)際計(jì)算中收斂速度慢，易出現(xiàn)鋸 齒現(xiàn)象擬牛頓法收斂速度很快，被廣泛認(rèn)為是非線性規(guī)劃的最有效的方法但擬牛頓 法需要存儲(chǔ)矩陣以及通過(guò)求解線性方程組來(lái)計(jì)算搜索方向，這對(duì)于求解大規(guī)模問(wèn)題幾乎 足不大可能辦到的共軛梯度算法在算法的簡(jiǎn)便性，所需存儲(chǔ)量等方面均與最速下降法 差別不大，而收斂速度比最速下降法要快因此在處理大規(guī)模非線性優(yōu)化問(wèn)題時(shí)許多實(shí) 際部門(mén)的工程師十分喜歡應(yīng)用共軛梯度算法 共軛梯度算法有很好的理論性質(zhì)，對(duì)于二次函數(shù)，在精確線搜索下共軛梯度算法可 以經(jīng)過(guò)n 步迭帶后求到最優(yōu)解共軛梯度算法的基本原理足利用產(chǎn)生的共軛方向?qū)⒁粋€(gè) 1 3 維的優(yōu)化問(wèn)題轉(zhuǎn)化為等價(jià)的1 1 個(gè)一維問(wèn)題 共軛梯度算法對(duì)于非二次函數(shù)有許多不同形式著名的共軛梯度算法有h e s t e n e s - s t i e m ( h s ) 方法f l e t c h e r - r e e v e s ( f r ) 方法 1 6 】，p o l a k - r i b i e r e 3 1 】- p l o y a k 3 ( p r p ) 方 法，共軛下降方法( c d ) 【1 1 和d a i y u a n ( d y ) 方法【4 等關(guān)于這些方法的收斂性以及計(jì) 算比較一直是人們關(guān)心的問(wèn)題h e s t e n e s 詳細(xì)討論了各種共軛梯度算法在求解優(yōu)化問(wèn)題 時(shí)的計(jì)算表現(xiàn)并且給出了計(jì)算實(shí)例f 2 3 ，近年來(lái)，n o c e d a 【2 5 1 ，g i l b e r t t q ，n a z a r e t h r 7 1 ，a i b a a l i 2 1 ，s t o r e y 2 4 1 等學(xué)者在算法的收斂性方面得到不少新結(jié)果，使得共軛梯度算法的收 斂性分析再次引起科研人員的關(guān)注可喜的是，我國(guó)學(xué)者也在共軛梯度算法的理論研究 中取得了一定的成績(jī)例如，中國(guó)科學(xué)院數(shù)學(xué)與系統(tǒng)科學(xué)研究院袁亞湘研究員課題組以 及韓繼業(yè)研究員課題組的工作就十分突出戴或虹博士和袁亞湘研究員在其2 0 0 0 年出 版的非線性共軛梯度法一書(shū)中系統(tǒng)的給出了無(wú)約束優(yōu)化問(wèn)題的共軛梯度算法的收斂 性理論，是國(guó)內(nèi)致力于討論共軛梯度算法的第一本專(zhuān)著f 洲 f r 方法是最早的非線性共軛梯度算法，早期對(duì)f r 方法的分析是基于精確線搜索 m 1 由于精確線搜索非常昂貴，在實(shí)際計(jì)算中人們通常使用非精確線搜索。而不使用 精確線搜索在非線性共軛梯度算法中，第一個(gè)非精確線搜索下的全局收斂性結(jié)果是由 a i b a m i 在1 9 8 5 年給出的，他證明了使用參數(shù)口 2 = l( 2 1 6 ) 其中0 是步長(zhǎng)，它滿足某些線搜索條件、這里g k 代表，在點(diǎn)的梯度，風(fēng)是 共軛梯度參數(shù)參數(shù)風(fēng)的形式有多種，著名的有： = 穢婚( f 池c 脅，r e e v e s 1 9 6 4 ) ， = 鑊驀( p 砒女r i b i a 隅p 。l y 。南，1 9 6 9 ) = 一老囂( 打e s t e n e s ，s t i e ，e f ，1 9 5 2 ) ， 一d k 蛆_ l g i i 。二- i ( f t e 把h e r ，1 9 s 7 ) = 老告( ，) n i ，y u 一，1 9 9 5 ) 其中d y 方法由戴或虹與袁亞湘【4 】給出這里弧，= g k g k _ l 當(dāng)f ( x ) 為二次函數(shù) 時(shí)，以上幾種參數(shù)風(fēng)的計(jì)算公式是等價(jià)的，當(dāng)( x ) 為一般非線性函數(shù)時(shí)，這些計(jì)算公 式的性質(zhì)可能大相徑庭 步長(zhǎng)因子的計(jì)算對(duì)于無(wú)約束選代算法也至關(guān)重要顯然最好的點(diǎn)是在方向d k 函 數(shù)值達(dá)到極小的點(diǎn)，但是這需要求一個(gè)單變量函數(shù)的極小值，計(jì)算量較大，故再實(shí)際計(jì) 7 r p 占 d y 硝儼鰭犁船 大連理工大學(xué)碩士學(xué)位論文：混合非線性共軛梯度算法研究 算中往往采用非精確線搜索其中w o l f e 線搜索就是一種，它要求步長(zhǎng)n k 滿足下述條 件： 、v o l f e 線搜索條件 “一f k d - “k 9 t d ，( 2 2 a ) 矗l d k 口蠢d k ， ( 2 2 b ) 其中0 5 口 l 第一個(gè)不等式要求函數(shù)有充分的下降，第二個(gè)不等式防止步長(zhǎng)o 過(guò)小，因而保證目標(biāo)函 數(shù)的足夠下降 本文還采用下述修正的w o l f e 線搜索： 修正的w j l f e 線搜索條件 ，( z 女+ o d k ) 一，( z ) d n 9 女t d k ， 口g 吾d k 9 扣k + a k d ) t d 0 ， 其中0 占 礦 0 使得 1 1 9 ( x ) 一g ( y ) | | l l l z 一憶v 。，y ( 2 3 ) 下面的引理給出一個(gè)一般性的結(jié)果 引理l ( z o u t e n 曬條件p 彰，聲可，膨聊設(shè)函數(shù)，( z ) 滿足假設(shè)j ，序列 z ) 是由償j 矽 生成的迭帶點(diǎn)列，且對(duì)每一個(gè)k ，有鯁t 氐 0 ，n 0 滿足w o 拈線搜索條件，則有 8 群 隨 第2 章非線性共軛梯度算法的全局收斂性分析 證明：由( 2 2 b ) 知 【g k + 1 9 】7 d k ( 口一1 ) 9 d 另一方面，由l i p s c h i t z 條件( 2 3 ) 有 和用以上兩式得 g k + l g k 7 d k ( l i i d f f 2 一口一1 9 女t d 。痧t 赫 ( 24 ) ( 2 2 a ) 和( 2 4 ) 表明 蠡一“c 讎7 2 ， 其中c = d ( 1 一一) l 對(duì)上式從= 1 ，2 ，求和，并注意，( z ) 下方有界，即知引理結(jié)論 成立 2 2 一個(gè)共軛梯度算法全局收斂性判別準(zhǔn)則 受d y 算法的啟發(fā)，下面的定理給出了共軛梯度方法全局收斂性的一個(gè)判別準(zhǔn)則 定理1 r 收斂性判別準(zhǔn)則j 設(shè)函數(shù)，( z ) 滿足假設(shè)， 是由共軛梯度法償糾生成 的迭帶點(diǎn)列，如果對(duì)每一個(gè)也有甄t 如 0 使得i 協(xié)| | ，對(duì)所有的k 成立，則由( 2 6 ) 我們有 嘰- - 0 則當(dāng)t 一c d 時(shí)，p ( t 1 是單調(diào)增加的， 如粟 b c a d o ， k l 1 妒女= ( 1 一p 一“氌) + ( ( 1 一a + p + “) 一p k ) 7 一1 0 如果弘= 0 ， 。女1 成立如果觸0 ，由引理2 ，將“看作k 的函數(shù)，是單調(diào)增加的， 從而結(jié)合兩種情況知n ( k ) r k ( 0 ) = 1 總之，引理的結(jié)論對(duì)于成立 引理4 序列( 礬) 是由共軛梯度法印j j 生成的迭帶點(diǎn)列，仇按俾圳計(jì)算，a k 由修 正的w o t f e 線搜索得到，則 惻罌 大連理工大學(xué)碩士學(xué)位論文! 混合非線性共軛梯度算法研究 證明：由( 2 ，l b ) 和( 28 ) ，當(dāng)k 2 時(shí)，直接計(jì)算可得 覷：垂生 聯(lián)一l d 一1 下面我們建立下述不等式 叢! 二型 ； ( f k ( 1 一a ) # k ) l k + ( 1 一p 一u ) ( r 矗l 一1 ) + 2 a 肛k + u k 1 ( 29 ) 得到 2 十( 1 一k u k ) ( r 芒l 一1 ) 一a k 1 + p + w k a k 1 又因?yàn)閒 k 0 ，從而 靠1 。3 卜氏) 機(jī)。至i 輔) d “- i k ) 訛如 = l + ( p 一1 ) l k 結(jié)合上述不等式可以得到 0 女( 1 一a k ) 曼( ( 1 一a k ) 一p 女) k + ( 1 一，“一u ) ( ，芒1 1 ) 十2 一a k 和 ( & ( 1 一a k ) 一# k ) l k4 - ( 1 一t z , k u k ) ( r 乏1 1 ) + 2 一a k 0 ， 因此( 2 9 ) 式成立顯然的有l(wèi) 仇| ( 9 。t d t 一1 e l k 一1 ) 定理2 設(shè)函數(shù)f ( x ) 滿足假設(shè)，共軛梯度法俾j j 中參數(shù)鳳按俾砂計(jì)算，步長(zhǎng)由修正 的w o f ，e 線搜索條件取得，則算法是在侶剴的意義下全局收斂的 證明：由定理l 和引理4 知定理的結(jié)論是顯然的 2 4 d y 方法一個(gè)變形的全局收斂性 在這一節(jié)，考慮d y 方法的一個(gè)變形，即滿足l 鼠i i 鱷。i 的反確定的共軛梯度算法。 首先定義i k = ( 靠t 如一1t 一1 d k 一1 ) ，則下述定理成立 定理3 設(shè)函數(shù)，( 。) 滿足假設(shè)， 。k 是由共軛梯度法俾，生成的迭代點(diǎn)列，仇按如 下形式計(jì)算： 擻= r p ，( 2 1 0 ) 1 2 【 一 。扯 一 由 由 第2 章非線性共軛梯度算法的全局收斂性分析 兵甲“【- 1 ，步長(zhǎng)n k 滿足w o 驢e 線搜索條件，如果 k 嵩，“- 1 , o ) 靠d m 0 ，v k ， 0 2 ，我們有 = 一i i g k l l 2 + ? k g t d k l = 一i t a k l l 2 + r k 老磐9 融一z = 阼1 + 籍碧) = i l g k l l 2 ( 盟絮竽) h | j 礎(chǔ)m = 器( ( ，一) 9 t d t1 + 9 砷一) - 由( 2 1 0 ) ，上面的關(guān)系式可被重寫(xiě)成 艨= t k ( 1 t 鯫1 1 2 ) ( d l 。鯫一) = “( 9 吾血) ( ( ，一1 ) 露也一14 - 9 & l d k 一1 ) = 矗( t “k ，八tl d k 一1 ) ， ( 2 1 1 ) 其中 ，r h 2 瓦= 麗 因?yàn)閛 ：k 滿足w o l f e 線搜索條件，得到： 如果“( o1 】，貝k o - 1 ，因此n 一( n 一1 ) k 一1 = ( r 一1 ) ( k 一1 ) 0 ，即i 矗i 1 如果r _ 1 ，o ，則靠 班l(xiāng) - r k ，因此1 。l 一( r 1 ) k 一1 一7 女一( r 一1 ) ；圭巽一1 = 0 ： 即慨l l 總之l 矗l l ，于是， 慨怪蘭t 1 1 ( 2 1 2 ) 鳙口k 一 。 1 3 大連理工大學(xué)碩士學(xué)位論文：混合非線性共軛梯度算法研究 接下來(lái)考慮 兩邊同時(shí)取平方，得到 兩邊同除以( 磋如) 2 ，得 蟊+ g k = 鳳d k 一1 f i d y l l 2 = 一i i g 1 1 2 + 鏷l l d 一。臚一2 9 d l 恢| 1 2 ( 9 吾如) 2 1 1 9 * 臚 ( 靠t 出) 2 吼= k q * - i + 廝1 ( 瓦2 一夸 其中 囅= 器“= 一麗g t d k 由于j 1 ，得 啦 0 ，因此 擊c 毒一番驀赤c 瓣， 因此 毒一委蔞等c ，一c 卻2 ，摹c ， 則 ( 去一1 ) 2 1 薯( 女一1 ) 乏1 一，+ 摹( m 一，) 三三店+ 1 2 2 狐 t k77 令d 3 = - y 2 彳，以= d 3 7 2 ，南= 醒7 2 ，并注意到一鳙t 氐= i i 鯫i | 2 t k 和i i d k lj l b k l l t ，則得到 1 4 第2 章 非線性共軛梯度算法的全局收斂性分析 推論1 設(shè)函數(shù)f ( x ) 滿足假設(shè)，序列 z 是由共軛梯度法俾j 生成的迭代點(diǎn)列，仇按 俾叫計(jì)算，其中 f k 1 1 】，n 滿足w o 拈線搜索條件，如果k 滿足償j jj ，g 手呶 0 對(duì)所有自成立，則算港在償糾的意義下全局收斂 證明由定理1 和式( 蓬蚵推論的結(jié)論是顯然的 在文獻(xiàn) 1 3 中，戴和袁限制了“的界以得到下降算法，并建立了其全局收斂性，文 獻(xiàn) 1 3 中的數(shù)值試驗(yàn)表明方法是有效的可以將文獻(xiàn) 1 3 中的全局收斂性定理2 3 視為 推論1 的特殊情形，將其收斂性定理重寫(xiě)如下： 定理4 設(shè)函數(shù)i 廠滿足假設(shè)，序列 z 女) 是由共軛梯度法償，生成的迭代點(diǎn)列，o 滿 足w o 拈線搜索條件，仇按償j 叫計(jì)算，其中 而 - - 0 ，1 】 則如果鱖0 對(duì)所有1 成立，算法在償剴的意義下全局收斂 證明：如果 吼【一而1 - - 0 ，吼 我們有 1 。 1 + 嶄2 南， 即 因此 。 0v k 1 ，使得 8 蚓1 7 因此 蜒一去+ 丟6 圳 ( 3 a ) 如一面i + 2 。n ( 3 _ 4 ) z = 1 “砉 ( 3 5 ) 長(zhǎng)胤 一 q 等h 一 n 互。瑚 葉褂 大連理工大學(xué)碩士學(xué)位論文：混合非線性共軛梯度算法研究 在另一方面，因?yàn)閠 k 0 和( 3 4 ) ，我們有 白圳熹 ( 3 e ) ；= 1 使用引理5 和( 3 5 ) ，( 3 6 ) ，我們得到 吾鼯蒂2 善墨2 。! ；。鐳蒂2 o 。 憊| 2 憊t e 。，缸。1 2 這是一個(gè)矛盾定理證完 3 2 一類(lèi)共軛梯度算法的全局收斂性 在文獻(xiàn) 4 6 中，作者令共軛梯度法( 2 1 ) 中紈屬于一個(gè)區(qū)間，證明r 其在廣義a r m i j o 線搜索下的全局收斂性，文獻(xiàn)給出的數(shù)值試驗(yàn)表明其是有效的，下面的定理給出了其在 w o l f e 線搜索下的全局收斂性為此，首先證明一個(gè)引理 引理7 假設(shè)函數(shù)，( z ) 滿足假設(shè)j ，在共軛梯度法償糾中 傀【- 再壬麗端，再再1 。硼1 1 9 i 川i 。 ( 37 。) 其中 ，。 o c 。s 目* 2 2 尚 ( 3 7 b ) 如果| | 肌l f 0 我們有 l 恢| | ( 1 + 1 ) 1 1 9 k 憶 g 融一麗i + a 惻1 2 證明；，對(duì)于k = 1 ，結(jié)論是顯然的 對(duì)于2 ，由( 2 i b ) 和( 3 6 ) ，我們有 l l 如i i = s s 注意到1 9 蠆氐1 = 一娠t 則還可得到： g t d k = 0 使得i m f f 7 對(duì)所有的自成立 由引理7 ，我們有 熱t(yī) 9 。1 1 墨一菩2 a ，9 吾昧o l 2 二 上 ，k “r 、。 則 麗t d k 、2 糕2 ( 3 s ) 恢| | 42 ( + ) 2 。 p o 仍由引理7 ，我們有： j j 或臚( 1 + ) 2 恢峨 則 燃端 。， 由( 3 8 ) 和( 39 ) ，得到 ( g t d k ) 2 ：t d k 2 業(yè)墮止 ! ! 壘蘭i 也劍： l l 血l i 2 i 舊一1 1 4 l 如1 1 2 二( 2 + ) 2 ( 1 + 去) z 由l | | 7 對(duì)所有七成立，因此 妻锘：慨 魯1 2 “ 這與z o u t e n d i j k 條件相矛盾證畢 2 1 4 結(jié)論 本文對(duì)非線性共軛梯度算法，尤其是混合非線性共軛梯度算法的理論性質(zhì)進(jìn)行了研 究 2 2 節(jié)給出了一個(gè)非線性共軛梯度算法在w o l f e 線搜索下全局收斂性的判別準(zhǔn)則 2 3 節(jié)和2 4 節(jié)利用該判別準(zhǔn)則分別證明了一類(lèi)三參數(shù)共軛梯度法簇和d y 方法的一個(gè) 變形的全局收斂性通過(guò)證明我們看到，該判別準(zhǔn)則使用起來(lái)是很方便的 第三章證明了兩篇文獻(xiàn)中提到的兩類(lèi)混合非線性共軛梯度算法在w o l f e 線搜索下或 廣義w o l f e 線搜索下的全局收斂性，其中3 1 節(jié)給出的結(jié)果在一定程度上回答了文獻(xiàn)2 0 1 在文末提出的問(wèn)題 5 參考文獻(xiàn) 1 1 a i b a a l im 。d e s c e n tp r o p e r 妙a n d 創(chuàng)o b a lc o n v e r g e n c eo ft h ef l e t c h e r - r e e v e sm e t h o d 州地 i n e x a c tl i n es e a r c h ，t m aj n u m e r a n 甜1 9 8 5 ，5 ：1 2 1 - 1 2 4 【2 】a i b a a l im ，f l e t c h e rro nt h eo r d e r o fc o n v e r g e n c eo f p r e c m l d i t i o n e dn o n l m e a r rc o n j 一 g a t eg r a d i e n tm e t h o d ，s i a mj s c i c o m p u t ，1 9 9 6 ，v b l1 7 ，n o3 ：6 5 8 6 6 5 3 ib e a i eem lad e r i v a t i v eo f c o n j u g a t e g r a d i e n t s ji n ：l o o t s m afa ，e d n u m e r i c a lm e t h o d s f o rn o n l i n e a xo p t i m i z a t i o n 、l o n d o n ：a c a d e m i cp r e s s ，1 9 7 2 3 9 4 3 4 1 yhd a i yy u a n an o n l i n e a rc o n j u g a t eg r a d i e n tm e t h o dw i t hn i c eg l o b mp r o b e r - t i e s r e s e a x c hr e p o r ti c m 一9 5 0 3 8 ，i n s t i t u t eo fc o m p u t a t i o n a lm a t h e m a t i e sa n ds c i e n t 訊c e n g i l l e e r i n gc o m p u t i n g ，c h i n e s ea c a d e m y o fs c i e n c e s ，1 9 9 5 【5 】d a iyh ，y u a ny c o n v e r g e n c ep r o p e r t i e so t t h e f l e t c h e r - r e e v e sn m t h o d ji m aj n u m e r a n a l 1 9 9 6 ，1 6 ( 2 ) ：1 5 5 1 6 4 f6 1d a i y h ，y u a nyc o n v e r g e n e eo ft h ef l e t c h e r - r e e v e sm e t h o du n d e 2 8g e n e r a l i z e dw o l f e s e a r c hj o u r n a lc o m p u t a t i o n a lm a t h e m a t i c so fc h i n e s eu n i v e r s i t i e s ，n o 2 ( 1 9 9 6 ) ：1 4 2 1 4 8 【7 1 7 d a iy h ，a n a l y s i so fc o n u g a t eg r a d i e n tm e t h o d s ，p h dt h s i s ，i n s t i t u t eo fc o m p u t i t i o n a t m a t h e m a t i c s a n ds c i e n c e e n g i n e e r i n gc o m p u t i n g ，c h i n e s ea c a d e m yo fs c i e n c e ( i nc h i - n e s e ) ，1 9 9 7 f 8 1 d a iy h ，y u a nys o m ep r o p e r t i e so f a 玎e h ，c o 可u g a t eg r a d i e n tm e t h o d ji n ：1 l z l l a l ly ，e d a d v a a e e si nn o n l i n e a rp r o g r a m m i n g ，b o s t o n ：k l u w e r ，1 9 9 8 ，2 5 1 2 6 2 【9 】d a iyi i ，y u a ny ac l a s so fg l o h a l b , c o n v e r g e n tc 0 n d u g a t eg r a d i e n tm e t h o d s ，r e s e a r c h r e p o r ti c m 一9 8 0 3 0 ，i n s t i t u t eo fc o m p u t a t i o n a lm a t h e n m t i c sa n ds c i e n t i f i c e n g i n s e r i n g c o m p u t i u g ，c h i n e s ea c a d e m y o fs c i e n c e s ，1 9 9 8 1 0 1d a iyh ，y u a n y e x t r a o no f ac l a s so f n o n l i n e a r c o n j u g a t eg r a d i e n tm e t h o d s ，r e s e a r d l r e p o r ti c m 一9 8 0 4 9 ，i n s t i t u t eo fc o m p u t a t i o n a lm a t h e m a t i c sa n ds c i e n t i f i c e n g i n e e r i n g c o m p u t i n g ，c h i n e s ea c a d e m y o fs c i e n c e s ，1 9 9 8 1 1 】d a iyh ，y u a ny at h r e e - p a r a m e t e rf a m i 妙o fn o n l i n e a rc o n j u g a t eg r a d i e n t l n e t h o d s r e s e a r c hr e p o r ti c m 9 8 0 5 0 i n s t i t u t eo fc o m p u t a t i o n a tm a t h e m a t i c sa n ds c i o n ， t i 6 c e n g i l l e e r i n gc o m p u t i n g ，c h i n e s ea c a d e m y o fs c i e n c e ，1 9 9 8 1 2 】d a iyh ，y x y u a n an o n l i n e a rc o n j u g a t eg r a d i e n tw i t has t r o n gg l o b a lc o n v e r g e n c e p r o p e r t y ，s i a mj o u r n “o fo p t i m i z a t i o n ，2 0 0 0 ，1 0 ：1 7 7 - 1 8 2 1 3 1d a iyh y x ，y a a n a ne f f i c i e n th y b r i dc o n j u g a t eg r a d i e n tm e t h o df o ru n c o n s t r a i n e - d o p t i m i z a t i o n ，a n n a l so fo p e r a t i o n sr e s e m c h1 0 3 ( 2 0 0 1 ) ：3 3 - 4 7 大連理工大學(xué)碩士學(xué)位論文：混合非線性共軛梯度算法研究 1 4 d a iy h ，h a njy ，l i ugh ，s u ndf ，y i nhx ，y n a ny c o n v e r g e n c ep r