擬牛頓法的研究現(xiàn)狀文獻(xiàn)綜述

擬牛頓法的研究現(xiàn)狀文獻(xiàn)綜述姓名:孟媛媛學(xué)號(hào)：112111215指導(dǎo)老師：肖偉前言求解非線性方程組的方法有很多，最速下降法具有結(jié)構(gòu)簡(jiǎn)單，計(jì)算量小的優(yōu)點(diǎn)，但是它的收斂速度較慢；牛頓法及其改良牛頓法，雖然收斂速度快，但在迭代過(guò)程中的每一步構(gòu)造搜索方向時(shí)，首先要計(jì)算目標(biāo)函數(shù)的Hessian矩陣，然后需要解一個(gè)線性方程組，計(jì)算工作量很大，這就抵消了牛頓法收斂速度快的優(yōu)點(diǎn)。為了克服牛頓法的缺點(diǎn)，人們提出了擬牛頓法，擬牛頓法在構(gòu)造搜索方向時(shí)，只需要利用目標(biāo)函數(shù)及其一階導(dǎo)數(shù)的信息，防止了Hessian矩陣的計(jì)算，減少了計(jì)算量，并且具有超線性收斂的優(yōu)點(diǎn)，經(jīng)理論證明和實(shí)踐檢驗(yàn)，擬牛頓法已經(jīng)成為一類公認(rèn)的比擬有效的算法.擬牛頓法求解非線性方程組的擬牛頓法設(shè)是連續(xù)可微映射．考慮下面的非線性方程組：牛頓法是求解方程組的經(jīng)典的方法之一，其迭代格式為：，，其中是在處的Jacobian陣.牛頓法的一個(gè)顯著優(yōu)點(diǎn)就是具有局部的超線性甚至二階收斂速度，由于牛頓法這一優(yōu)點(diǎn)，使其成為頗受歡送的算法之一，然而，當(dāng)Jacobian矩陣奇異時(shí)，牛頓方向可能不存在．克服牛頓法的這一缺陷的一個(gè)主要途徑就是采用擬牛頓法，其根本思想是利用某個(gè)矩陣作為的近似取代.擬牛頓法的一般格式為：，，其中是步長(zhǎng)，通常由某種線性搜索確定.是的近似，它滿足下面的擬牛頓方程：，其中.注意到，因此，與沿方向很接近.擬牛頓矩陣的不同的校正公式導(dǎo)致不同的擬牛頓法.著名的擬牛頓校正公式有Broyden秩一校正公式，對(duì)稱秩一校正公式，DFP校正公式，BFGS校正公式，PSB校正公式等，它們分別由下面這些公式定義：容易看到，DFP，PSB，BFGS，SR1校正公式都是對(duì)稱的，他們適合求解對(duì)稱問(wèn)題，而BroydenR1校正公式是不對(duì)稱的，因此它常被用來(lái)求非對(duì)稱問(wèn)題.如果，那么DFP和BFGS公式保持迭代矩陣的對(duì)稱正定性，而其它幾種方法不具有這種性質(zhì).PSB校正公式在非線性最小二乘問(wèn)題中經(jīng)常被采用.BFGS公式是頗受歡送的擬牛頓公式，它具有DFP校正所具有的各種性質(zhì).此外，當(dāng)采用Wolfe線性搜索時(shí)，BFGS算法對(duì)凸極小化問(wèn)題具有全局收斂性質(zhì)，這個(gè)性質(zhì)對(duì)于DFP方法是否成立尚不清楚.大量的數(shù)據(jù)結(jié)果說(shuō)明，BFGS方法的數(shù)值效果優(yōu)于其它的擬牛頓方法.擬牛頓法不需要明顯計(jì)算Jacobian陣，同時(shí)保持牛頓法的快速收斂速度.自20世紀(jì)60年代Broyden第一次提出求解非線性方程組的擬牛頓法后，因其深邃豐富的理論知識(shí)和實(shí)際計(jì)算中的有效性，很快受到最優(yōu)化工作者和計(jì)算數(shù)學(xué)家的特別青睞.特別是擬牛頓法的局部收斂性得到了廣泛的研究.此外，人們對(duì)擬牛頓法求解無(wú)約束問(wèn)題的全局收斂性分析進(jìn)行了相當(dāng)?shù)呐Σ⑶胰〉昧司薮筮M(jìn)展．盡管擬牛頓法的局部收斂性結(jié)果十分豐富，但是其求解非線性方程組的全局收斂性結(jié)果卻很少．全局化方法需要采用某種搜索計(jì)算步，但是此時(shí)擬牛頓方向一般不再是某個(gè)度量函數(shù)的下降方向，從而使得線性搜索難以實(shí)現(xiàn)或考說(shuō)缺少一種有效的線性搜索.Griewank在1986年研究了解非線性方程組的Broyden秩一方法的全局收斂性，并在文獻(xiàn)[2]中提出了一種無(wú)導(dǎo)數(shù)的線性搜索，同時(shí)證明了Broyden方法在該搜索下的全局收斂性．Li和Fukushima在文獻(xiàn)[3]中構(gòu)造了一個(gè)反例說(shuō)明Griewank在文獻(xiàn)[2]中的線性搜索在計(jì)算中可能會(huì)產(chǎn)生某些困難，即該搜索不是適定的.為克服此缺陷，Li和Fukushima提出了一種非單調(diào)搜索技術(shù)：求步長(zhǎng)使得其中是常數(shù)，在適當(dāng)條件下，文獻(xiàn)[3]證明了求解非線性方程組的Broyden方法的全局收斂性.關(guān)于BFGS方法求解非線性方程組的第一個(gè)全局收斂性結(jié)果屬于Li和Fukushima，1999年，他們?cè)谖墨I(xiàn)[4]中提出了一種新的近似范數(shù)下降的BFGS方法，稱之為Gauss—Newton型BFGS方法，其擬牛頓方向由下面的方程決定：，其中由下面的BFGS公式校正：其中.這種Gauss-Newton型BFGS公式不同于標(biāo)準(zhǔn)的BFGS公式，盡管它仍滿足擬牛頓方程.注意到，因此，相應(yīng)的方法稱之為Gauss-Newton型BFGS方法.2003年，GU等人引入了一種范數(shù)下降的線性搜索，并利用Li和Fukushima求解無(wú)約束優(yōu)化問(wèn)題的CBFGS和MBFGS方法的思想,提出了求解對(duì)稱非線性方程組的范數(shù)下降的保守的和修正的Gauss—Newton型BFGS方法，并且證明了這兩種方法全局收斂.盡管牛頓法和擬牛頓法都是非常有效的算法，但是它們都需要計(jì)算和存儲(chǔ)矩陣，這難以用于求解大型問(wèn)題．最近，Cruz和Raydan在文獻(xiàn)[5]提出了一種求解一般的非線性方程組的非單調(diào)的譜梯度方法并證明了其全局收斂性．Zhang和Zhou在文獻(xiàn)[6]提出了一種求解單調(diào)非線性方程組的譜梯度投影方?jīng)逊ń⒘巳质諗啃越Y(jié)果.這兩種譜梯度方法都適合求大規(guī)模問(wèn)題，察實(shí)上，這兩種譜梯度方法是求解無(wú)約束優(yōu)化問(wèn)題的譜梯度方法在非線性方程組中的推廣．前面討論的都是擬牛頓法求解光滑非線性方程組的已有結(jié)果。對(duì)擬牛頓法求解非光滑方程組的結(jié)果目前并不多見，而且大多數(shù)研究集中在局部收斂性分析上.通過(guò)光滑技術(shù)，Li和Fukushima將文獻(xiàn)[3]Broyden方法求解光滑方程組的全局收斂性結(jié)果推廣到了一般的半光滑方程組[8].二、求解無(wú)約束優(yōu)化問(wèn)題的擬牛頓法設(shè)：連續(xù)可微，為在點(diǎn)處的梯度，求解無(wú)約束優(yōu)化問(wèn)題min的擬牛頓法的迭代與其求解非線性方程的格式相同，只需要將中中的定義改為，其中是的簡(jiǎn)寫.擬牛頓法求解無(wú)約束優(yōu)化問(wèn)題不僅局部收斂性分析取得豐碩的成果，而且全局收斂性分析也取得了巨大進(jìn)展．Powell和Dixon證明了Broyden族方法在精確搜索下求解凸極小化問(wèn)題時(shí)的全局收斂性．所謂的精確搜索，即求使得滿足.Byrd等人在文獻(xiàn)[8]中證明了除DFP方法外的Broyden族方法在Wolfe線性搜索下求解凸極小化問(wèn)題的全局收斂性．這里的wolfe搜索，指的是求使得其滿足，，其中．Byrd和Nocedal證明了BFGS方法在Armijo線性搜索下求解凸極小化問(wèn)題的全局收斂性．所謂的Armijo搜索，即求滿足，其中為常數(shù)．為了研究擬牛頓法求解非凸問(wèn)題的全局收斂性，Li和Fukushima修正了標(biāo)準(zhǔn)的BFGS公式，提出了CBFGS方法和MBFGS方法并證明了這兩種方法在Armijo和Wolfe線性搜索下對(duì)非凸極小化問(wèn)題全局收斂.前面都是關(guān)于單調(diào)的擬牛頓法求解無(wú)約束問(wèn)題的工作，所謂的單調(diào)方法就是算法產(chǎn)生的函數(shù)值序列單調(diào)遞減，即使得成立.非單調(diào)方法那么不一定要求.最早提出非單調(diào)線性搜索技術(shù)的是Grippo，Lampariello和Lucidi．1986年，他們?cè)谖墨I(xiàn)[7]中考慮了如下一般格式的非單調(diào)線性搜索技術(shù)：給定常數(shù)及非負(fù)整數(shù)，尋找步長(zhǎng)因子使得.當(dāng)時(shí)，上面的非單調(diào)線性搜索變?yōu)闃?biāo)準(zhǔn)的Armijo線性搜索.非單調(diào)技術(shù)的一個(gè)好處就是不要求函數(shù)值減少，從而使步長(zhǎng)因子的選取更具有彈性，即使得步長(zhǎng)盡可能的大．此外，Panier和Tits在文獻(xiàn)[10]中證明了非單調(diào)搜索技術(shù)能防止Maratos效應(yīng)．大量的數(shù)值結(jié)果說(shuō)明，非單調(diào)搜索比單調(diào)搜索數(shù)值表現(xiàn)要好得多，特別是非單調(diào)方法能求一些比擬困難的問(wèn)題，此外，其數(shù)值計(jì)算也比擬穩(wěn)定.多步擬牛頓法一般的擬牛頓方法在每一步的迭代中，僅利用上一步產(chǎn)生的梯度信息，建立—個(gè)擬牛頓方程，進(jìn)而求得目標(biāo)函數(shù)Hesse陣的近似。如果將前步的梯度值都納入到計(jì)算過(guò)程中，是否會(huì)取得更好的效果？基于這樣的想法Ford和Moghrabi于1993年提出了多步擬牛頓法。多步擬牛頓法的根本思想如下：記為中的一條可微路徑。對(duì)向量應(yīng)用鏈?zhǔn)椒敲?，在曲線上對(duì)應(yīng)點(diǎn)處，滿足牛頓等式，利用上式來(lái)建立擬牛頓方程.記.視為一條通過(guò)和兩迭代點(diǎn)的直線.即，那么由式有，，并且.由于很難精確求得Hesse陣，用向后差分來(lái)近似,由式可估算導(dǎo)數(shù)在處的值.將和代入中取可得.標(biāo)準(zhǔn)擬牛頓打用近似值來(lái)代替Hesse陣，由上試滿足.這就是標(biāo)準(zhǔn)的擬牛頓方程.多步擬牛頓法是上述單步牛頓法的推廣，其多步擬牛頓方程的推導(dǎo)過(guò)程與相類似.假設(shè)前個(gè)迭代點(diǎn)以及相應(yīng)的梯度值信息。同樣記為中的一條可微路徑，但此時(shí)不是一條直線，可以定義為一個(gè)m次的插值多項(xiàng)式，其插值基點(diǎn)為的取值不同，將得到不同的插值函數(shù).由前面討論的擬牛頓方程,的一個(gè)很自然的取法是選擇等距的值,即取當(dāng)然除這種取法外,值還有很多其他的有效取法.標(biāo)準(zhǔn)的擬牛頓方程是取及，得到的.構(gòu)造的Lagrange插值多項(xiàng)式,這里的是基于集合的標(biāo)準(zhǔn)的次拉格朗日多項(xiàng)式的第項(xiàng)，即將視為的函數(shù)，由標(biāo)準(zhǔn)擬牛頓方程的推導(dǎo)過(guò)程及式，可用Lagrange插值多項(xiàng)式來(lái)近似.由于對(duì)應(yīng)于，在中令，接下來(lái)計(jì)算和的值.對(duì)式求導(dǎo)得，對(duì)式求導(dǎo)得,這里，.由此，可類似推出多步擬牛頓法的擬牛頓方程,其中是的近似.對(duì)式和式進(jìn)行重新整理，和可以分別用和的線性組合來(lái)表示，即，在多步法中，使用〔例如〕“DFP型”等校正公式得到新Hesse陣逆近似，這里分別以和來(lái)代替和，.根據(jù)變量的取值不同，可得到不同的插值函數(shù)，由此可得不同的算法。如單空間法、累積法、不動(dòng)點(diǎn)法等.下面給出多步擬牛頓算法的步驟.步0.選取為問(wèn)題所能容忍的值.設(shè),;計(jì)算和.步1.如果，那么停止.步2.計(jì)算搜索方向.如果(為的維數(shù))并且那么.步3.利用從出發(fā)沿方向的線搜索，計(jì)算滿足條件的.步4.如果僅迭代一步，那么設(shè),;否那么按照和計(jì)算和.步5.如果并且，那么取.步6.校正迭代矩陣.根據(jù)計(jì)算..轉(zhuǎn)步1.總結(jié)擬牛頓法是無(wú)約束最優(yōu)化方法中最有效的一類算法,其理論分析與算法改良研究已有很多成果.它有許多的優(yōu)點(diǎn)，比方，迭代中僅需一階導(dǎo)數(shù)，不必計(jì)算Hessian矩陣，當(dāng)使正定時(shí)，算法產(chǎn)生的方向均為下降方向，并且這類算法具有二次終止性，對(duì)于一般情形，具有超線性收斂速率，而且還具有步二階收斂速率,可見，擬牛頓法集中了許多算法的長(zhǎng)處.擬牛頓法的缺點(diǎn)是所需存儲(chǔ)量較大，對(duì)于大型問(wèn)題，可能遇到存儲(chǔ)方面的困難。雖然擬牛頓法的收斂速度快且相應(yīng)的全局收斂性研究也非常成熟，但對(duì)于求解非線性方程組問(wèn)題的全局收斂性研究卻很少.參考文獻(xiàn)：[1]徐成賢，陳志平，李乃成.近代優(yōu)化方法.北京：科學(xué)出版社，2002.[2]GriewankA，The'global’convergenceofBroyden-likemethodswithasuitablelinesearch．JournalAustralianMathematicalSociety,1986，28(1)：75-92[3]LiDH，F(xiàn)ukushimaM．Aderivative-freelinesearchandglobalconvergenceofBroyden’S-likemethodfornonlinearequations．OptimizationMethodsandSoftware，2000，13(3)：181—201[4]LiDH，F(xiàn)ukushimaM．AgloballyandsupertinearconvergentGanss-Newton-basedBFGSmethodsforsyalmetricnonlinearequations．SIAMJournalonNumericalAnalysis，1999，37(1)：152-172[5]CruzW，RaydanM．Nonmonotonespectralmethodsforlargescalenonlinearsysterms．OptimizationMethodsandSoftware，2003，18(5)：583-589[6]ZhangL，ZhouWJ．Spectralgradientprojectionmethodforsolvingnonlinearmo