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

1、擬牛頓法的研究現(xiàn)狀文獻(xiàn)綜述姓名:孟媛媛 學(xué)號：112111215 指導(dǎo)老師：肖偉前言求解非線性方程組的方法有很多，最速下降法具有結(jié)構(gòu)簡單，計算量小的優(yōu)點，但是它的收斂速度較慢；牛頓法及其改進(jìn)牛頓法，雖然收斂速度快，但在迭代過程中的每一步構(gòu)造搜索方向時，首先要計算目標(biāo)函數(shù)的Hessian矩陣，然后需要解一個線性方程組，計算工作量很大，這就抵消了牛頓法收斂速度快的優(yōu)點。為了克服牛頓法的缺點，人們提出了擬牛頓法，擬牛頓法在構(gòu)造搜索方向時，只需要利用目標(biāo)函數(shù)及其一階導(dǎo)數(shù)的信息，避免了Hessian矩陣的計算，減少了計算量，并且具有超線性收斂的優(yōu)點，經(jīng)理論證明和實踐檢驗，擬牛頓法已經(jīng)成為一類公認(rèn)的比較有

2、效的算法. 擬牛頓法一、 求解非線性方程組的擬牛頓法設(shè)是連續(xù)可微映射考慮下面的非線性方程組： 牛頓法是求解方程組的經(jīng)典的方法之一，其迭代格式為：，其中是在處的Jacobian陣.牛頓法的一個顯著優(yōu)點就是具有局部的超線性甚至二階收斂速度，由于牛頓法這一優(yōu)點，使其成為頗受歡迎的算法之一，然而，當(dāng)Jacobian矩陣奇異時，牛頓方向可能不存在克服牛頓法的這一缺陷的一個主要途徑就是采用擬牛頓法，其基本思想是利用某個矩陣作為的近似取代.擬牛頓法的一般格式為： ， ， 其中是步長，通常由某種線性搜索確定. 是的近似，它滿足下面的擬牛頓方程：， 其中.注意到，因此，與沿方向很接近.擬牛頓矩陣的不同的校正公式

3、導(dǎo)致不同的擬牛頓法.著名的擬牛頓校正公式有Broyden秩一校正公式，對稱秩一校正公式，DFP校正公式，BFGS校正公式，PSB校正公式等，它們分別由下面這些公式定義： 容易看到，DFP，PSB，BFGS，SR1校正公式都是對稱的，他們適合求解對稱問題，而Broyden R1校正公式是不對稱的，因此它常被用來求非對稱問題.如果，則DFP和BFGS公式保持迭代矩陣的對稱正定性，而其它幾種方法不具有這種性質(zhì). PSB校正公式在非線性最小二乘問題中經(jīng)常被采用. BFGS公式是頗受歡迎的擬牛頓公式，它具有DFP校正所具有的各種性質(zhì).此外，當(dāng)采用Wolfe線性搜索時，BFGS算法對凸極小化問題具有全局收

4、斂性質(zhì)，這個性質(zhì)對于DFP方法是否成立尚不清楚.大量的數(shù)據(jù)結(jié)果表明，BFGS方法的數(shù)值效果優(yōu)于其它的擬牛頓方法. 擬牛頓法不需要明顯計算Jacobian陣，同時保持牛頓法的快速收斂速度.自20世紀(jì)60年代Broyden第一次提出求解非線性方程組的擬牛頓法后，因其深邃豐富的理論知識和實際計算中的有效性，很快受到最優(yōu)化工作者和計算數(shù)學(xué)家的特別青睞.特別是擬牛頓法的局部收斂性得到了廣泛的研究. 此外，人們對擬牛頓法求解無約束問題的全局收斂性分析進(jìn)行了相當(dāng)?shù)呐Σ⑶胰〉昧司薮筮M(jìn)展盡管擬牛頓法的局部收斂性結(jié)果十分豐富，但是其求解非線性方程組的全局收斂性結(jié)果卻很少全局化方法需要采用某種搜索計算步，但是此時

5、擬牛頓方向一般不再是某個度量函數(shù)的下降方向，從而使得線性搜索難以實現(xiàn)或考說缺少一種有效的線性搜索. Griewank在1986年研究了解非線性方程組的Broyden秩一方法的全局收斂性，并在文獻(xiàn)2中提出了一種無導(dǎo)數(shù)的線性搜索，同時證明了Broyden方法在該搜索下的全局收斂性Li和Fukushima在文獻(xiàn)3中構(gòu)造了一個反例表明Griewank在文獻(xiàn)2中的線性搜索在計算中可能會產(chǎn)生某些困難，即該搜索不是適定的.為克服此缺陷，Li和Fukushima提出了一種非單調(diào)搜索技術(shù)：求步長使得 其中是常數(shù)，在適當(dāng)條件下，文獻(xiàn)3證明了求解非線性方程組的Broyden方法的全局收斂性. 關(guān)于BFGS方法求解非

6、線性方程組的第一個全局收斂性結(jié)果屬于Li和Fukushima，1999年，他們在文獻(xiàn)4中提出了一種新的近似范數(shù)下降的BFGS方法，稱之為GaussNewton型BFGS方法，其擬牛頓方向由下面的方程決定：，其中由下面的BFGS公式校正：其中. 這種Gauss-Newton型BFGS公式不同于標(biāo)準(zhǔn)的BFGS公式，盡管它仍滿足擬牛頓方程.注意到，因此，相應(yīng)的方法稱之為Gauss-Newton型BFGS方法.2003年，GU等人引入了一種范數(shù)下降的線性搜索，并利用Li和Fukushima求解無約束優(yōu)化問題的CBFGS和MBFGS方法的思想,提出了求解對稱非線性方程組的范數(shù)下降的保守的和修正的Gaus

7、sNewton型BFGS方法，并且證明了這兩種方法全局收斂. 盡管牛頓法和擬牛頓法都是非常有效的算法，但是它們都需要計算和存儲矩陣，這難以用于求解大型問題最近，Cruz和Raydan在文獻(xiàn)5提出了一種求解一般的非線性方程組的非單調(diào)的譜梯度方法并證明了其全局收斂性Zhang和Zhou在文獻(xiàn)6提出了一種求解單調(diào)非線性方程組的譜梯度投影方?jīng)逊ń⒘巳质諗啃越Y(jié)果.這兩種譜梯度方法都適合求大規(guī)模問題，察實上，這兩種譜梯度方法是求解無約束優(yōu)化問題的譜梯度方法在非線性方程組中的推廣 前面討論的都是擬牛頓法求解光滑非線性方程組的已有結(jié)果。對擬牛頓法求解非光滑方程組的結(jié)果目前并不多見，而且大多數(shù)研究集中在局部

8、收斂性分析上. 通過光滑技術(shù)，Li和Fukushima將文獻(xiàn)3 Broyden方法求解光滑方程組的全局收斂性結(jié)果推廣到了一般的半光滑方程組8.二、求解無約束優(yōu)化問題的擬牛頓法設(shè)：連續(xù)可微，為在點處的梯度，求解無約束優(yōu)化問題 min 的擬牛頓法的迭代與其求解非線性方程的格式相同，只需要將中中的定義改為 ，其中是的簡寫.擬牛頓法求解無約束優(yōu)化問題不僅局部收斂性分析取得豐碩的成果，而且全局收斂性分析也取得了巨大進(jìn)展Powell和Dixon證明了Broyden族方法在精確搜索下求解凸極小化問題時的全局收斂性所謂的精確搜索，即求使得滿足 .Byrd等人在文獻(xiàn)8中證明了除DFP方法外的Broyden族方法

9、在Wolfe線性搜索下求解凸極小化問題的全局收斂性這里的wolfe搜索，指的是求使得其滿足，其中Byrd和Nocedal證明了BFGS方法在Armijo線性搜索下求解凸極小化問題的全局收斂性所謂的Armijo搜索，即求滿足，其中為常數(shù)為了研究擬牛頓法求解非凸問題的全局收斂性，Li和Fukushima修正了標(biāo)準(zhǔn)的BFGS公式，提出了CBFGS方法和MBFGS方法并證明了這兩種方法在Armijo和Wolfe線性搜索下對非凸極小化問題全局收斂.前面都是關(guān)于單調(diào)的擬牛頓法求解無約束問題的工作，所謂的單調(diào)方法就是算法產(chǎn)生的函數(shù)值序列單調(diào)遞減，即使得成立.非單調(diào)方法則不一定要求.最早提出非單調(diào)線性搜索技術(shù)

10、的是Grippo，Lampariello和Lucidi1986年，他們在文獻(xiàn)7中考慮了如下一般格式的非單調(diào)線性搜索技術(shù)：給定常數(shù)及非負(fù)整數(shù)，尋找步長因子使得. 當(dāng)時，上面的非單調(diào)線性搜索變?yōu)闃?biāo)準(zhǔn)的Armijo線性搜索.非單調(diào)技術(shù)的一個好處就是不要求函數(shù)值減少，從而使步長因子的選取更具有彈性，即使得步長盡可能的大此外，Panier和Tits在文獻(xiàn)10中證明了非單調(diào)搜索技術(shù)能避免Maratos效應(yīng)大量的數(shù)值結(jié)果表明，非單調(diào)搜索比單調(diào)搜索數(shù)值表現(xiàn)要好得多，特別是非單調(diào)方法能求一些比較困難的問題，此外，其數(shù)值計算也比較穩(wěn)定.三、 多步擬牛頓法 一般的擬牛頓方法在每一步的迭代中，僅利用上一步產(chǎn)生的梯度信

11、息，建立個擬牛頓方程，進(jìn)而求得目標(biāo)函數(shù)Hesse陣的近似。如果將前步的梯度值都納入到計算過程中，是否會取得更好的效果？基于這樣的想法Ford和Moghrabi于1993年提出了多步擬牛頓法。 多步擬牛頓法的基本思想如下： 記為中的一條可微路徑。 對向量應(yīng)用鏈?zhǔn)椒▌t，在曲線上對應(yīng)點處，滿足牛頓等式 ， 利用上式來建立擬牛頓方程. 記.視為一條通過和兩迭代點的直線.即 ， 則由式有，并且 . 由于很難精確求得Hesse陣，用向后差分來近似 , 由式可估算導(dǎo)數(shù)在處的值 . 將和代入中取可得 . 標(biāo)準(zhǔn)擬牛頓打用近似值來代替Hesse陣，由上試滿足 . 這就是標(biāo)準(zhǔn)的擬牛頓方程. 多步擬牛頓法是上述單步牛

12、頓法的推廣，其多步擬牛頓方程的推導(dǎo)過程與相類似. 假設(shè)已知前個迭代點以及相應(yīng)的梯度值信息。同樣記為中的一條可微路徑，但此時不是一條直線，可以定義為一個m次的插值多項式，其插值基點為 的取值不同，將得到不同的插值函數(shù).由前面討論的擬牛頓方程,的一個很自然的取法是選擇等距的值,即取 當(dāng)然除這種取法外,值還有很多其他的有效取法.標(biāo)準(zhǔn)的擬牛頓方程是取及，得到的.構(gòu)造的Lagrange插值多項式 , 這里的是基于集合的標(biāo)準(zhǔn)的次拉格朗日多項式的第項，即 將視為的函數(shù)，由標(biāo)準(zhǔn)擬牛頓方程的推導(dǎo)過程及式，可用Lagrange插值多項式來近似 . 由于對應(yīng)于，在中令，接下來計算和的值.對式求導(dǎo)得 ， 對式求導(dǎo)得,

13、 這里 ， . 由此，可類似推出多步擬牛頓法的擬牛頓方程 , 其中是的近似. 對式和式進(jìn)行重新整理，和可以分別用和的線性組合來表示，即 ， 在多步法中，使用（例如）“DFP型”等校正公式得到新Hesse陣逆近似，這里分別以和來代替和， . 根據(jù)變量的取值不同，可得到不同的插值函數(shù)，由此可得不同的算法。如單空間法、累積法、不動點法等.下面給出多步擬牛頓算法的步驟.步0. 選取為問題所能容忍的值.設(shè),;計算和.步1. 如果，則停止.步2. 計算搜索方向.如果(為的維數(shù))并且則.步3. 利用從 出發(fā)沿方向的線搜索，計算滿足條件的.步4.如果僅迭代一步，則設(shè),; 否則按照和計算 和.步5.如果并且，則

14、取 .步6.校正迭代矩陣.根據(jù)計算.轉(zhuǎn)步1.總結(jié) 擬牛頓法是無約束最優(yōu)化方法中最有效的一類算法,其理論分析與算法改進(jìn)研究已有很多成果.它有許多的優(yōu)點，比如，迭代中僅需一階導(dǎo)數(shù)，不必計算Hessian矩陣，當(dāng)使正定時，算法產(chǎn)生的方向均為下降方向，并且這類算法具有二次終止性，對于一般情形，具有超線性收斂速率，而且還具有步二階收斂速率,可見，擬牛頓法集中了許多算法的長處.擬牛頓法的缺點是所需存儲量較大，對于大型問題，可能遇到存儲方面的困難。雖然擬牛頓法的收斂速度快且相應(yīng)的全局收斂性研究也非常成熟，但對于求解非線性方程組問題的全局收斂性研究卻很少.參考文獻(xiàn)：1徐成賢，陳志平，李乃成.近代優(yōu)化方法.北京

15、： 科學(xué)出版社， 2002.2 Griewank A，The'global convergence of Broyden-likemethods with a suitable line searchJournal Australian Mathematical Society,1986，28(1)：75-923 Li D H，F(xiàn)ukushima MA derivative-free line search and global convergence of BroydenS-like method for nonlinear equationsOptimization Methods

16、 and Software，2000，13(3)：1812014 Li D H，F(xiàn)ukushima MA globally and supertinear convergent Ganss-Newton-based BFGS methods for syalmetric nonlinear equationsSIAM Journal on Numerical Analysis，1999，37(1)：152-1725Cruz W，Raydan MNonmonotone spectral methodsfor large scale nonlinear systermsOptimization M

17、ethods and Software，2003，18(5)：583-5896Zhang L，Zhou W JSpectral gradient projection method for solving nonlinear monotoneequationsJournal of Computational and Applied Mathematics(to appear)7 Grippo L，Lampariello F，Lucidi SA nonmonotone linesearch techniquefor Newton-s methodSIAM Journal on Numerical Analysis，1986，23(4)：707-7168 Li D H，F(xiàn)ukushima MA modified BFGS method and its global convergence in nonconvex minimizationJournal of Computationa land Applied Mathem