非線性共軛梯度法的文獻綜述

非線性共軛梯度法的文獻綜述研究摘要：共軛梯度法最早是由Hestenes和Stiefel于1952年提出來的，用于解正定系數(shù)矩陣的線性方程組，在這個基礎上，F(xiàn)letcher和Reeves于1964年首先提出了解非線性最優(yōu)化問題的共軛梯度法。由于共軛梯度法不需要矩陣存儲，且有較快的收斂速度和二次終止性等優(yōu)點，于是，共軛梯度法的理論研究受到了人們的關注，現(xiàn)在共軛梯度法已經(jīng)廣泛地應用與實際問題中。關鍵詞：共軛梯度法，非線性最優(yōu)化，線性搜索，收斂性共軛梯度法共軛梯度法最早是由計算數(shù)學家Hestenes和幾何學家Stiefel在20世紀50年代初為求解線性方程組Ax=b,xgRn而獨立提出的。他們奠定了共軸梯度法的基礎，他們的文章詳細討論了求解線性方程組的共軸梯度法的性質(zhì)以及它和其他方法的關系。當A對稱正定時，上述線性方程組等價于最優(yōu)化問題1min—xtAx一bTxxGRn2基于此，Hestenes和Stiefel的方法可視為求解二次函數(shù)極小值的共軛梯度法。1964年，F(xiàn)letcher和Reevse將此方法推廣到非線性優(yōu)化，得到了求一般函數(shù)極小值的共軛梯度法。而本書中，戴彧虹和袁亞湘介紹了多種類型的共軛梯度法，各方法的區(qū)分主要在于每次迭代的方向上，并且他們檢驗了每種方法在不同搜索下的全局收斂性。在他們的研究中，目標函數(shù)連續(xù)可微有下界，導數(shù)滿足Lipschitz條件，他們通過對Zoutendijk條件的判斷，通常用反證的方法來考察全局各共軛梯度法的全局收斂性問題。對于無約束優(yōu)化問題minf(x)xeRn一般給出一初值x1，經(jīng)由算法迭代產(chǎn)生x2,P…。在第k次迭代，當前迭代點為x，用一種方法產(chǎn)生一搜索方向dkgRn。然后下一迭代點為：x=x+ad其中，迭代方向dk的不同選取產(chǎn)生了不同的共軸梯度法，以k為步長因子，步長的不同選取產(chǎn)生了不同的搜索準則。而本書著重研究各方法在精確線搜索，Curry原則，強Wolfe線搜索和推廣的Wolfe線搜索下的收斂性。其中：精確線搜索要求每次迭代的步長滿足：f叫+氣叩=骯f(氣+a叩Curry原則要求每次迭代的步長七為一維函數(shù)氣°)={f(氣+a4)：^>0}的第一個極小點。強Wolfe線搜索要求每次迭代的步長滿足：f(x+ad)<f(x)+5adrgkkk k kkkdTg(x+ad)<bdTgkkkk kk其中，0<8<Q<1。推廣的Wolfe線搜索要求每次迭代的步長滿足：f(x+ad)<f(x)+8adTgkkk k kkkbdTg<dTg(x+ad)<-bdTg其中0<8<1,b]G(8,1),b>0而迭代方向一般為：可知迭代方向的不同由Pk產(chǎn)生，故Pk的不同選取產(chǎn)生的各種共軛梯度法，戴彧虹和袁亞湘介紹了如下方法，有：Fletcher和Reeves在1964年求解線性方程組推廣而得的共軛梯度法，簡稱FR方法。Polak和Ribiere和Polyak在1969年獨立提出的一種非線性共軛梯度法，簡稱PRP方法。Hestenes和Stiefel給出的另一種HS方法。Fletcher在1987年引入的共軛下降法，簡稱為CD方法。戴彧虹和袁亞湘在1995年提出的新的共軛梯度法，簡稱為DY方法。本書中給出了各種方法在不同搜索標準下的收斂性條件和全局收斂證明。全局收斂性及條件全局收斂性保證了算法從任何初始點開始都可以找到滿足任意精度的近似解。所以最優(yōu)化方法的收斂性是算法領域最基本的問題之一。本書中，戴彧虹和袁亞湘著重研究了不使用重新開始技術的共軛梯度法的全局收斂性，而他們研究的方法，因為有著不同的修正公式，以及不同的搜索策略，故而有不同的收斂性質(zhì)。下面分別介紹這些方法。2.1FR方法FR方法中，島的選取按公式：3FR=ktk |g」F早期對于FR方法的分析是基于精確線搜索。Powell在精確線搜索下分析了FR方法可能連續(xù)產(chǎn)生小步長的性質(zhì)，而FR方法的這種可能連續(xù)產(chǎn)生許多小步長的性質(zhì)，在很大程度上也解釋了為何FR方法在數(shù)值計算中有時表現(xiàn)得很差。但Zoutendijk證明了采取精確線搜索的FR方法對一般非凸函數(shù)總收斂。由于精確線搜索在每步迭代時的難以操作性，實際計算中通常使用非精確線搜索。1985年，Al-Baali證明了使用參數(shù)c<1/2的強Wolfe線搜索的FR方法必滿足充分下降條件，且全局收斂。Liu、Han、和Yin將Al-Baali的結果推廣到了c=頊2。戴彧虹和袁亞湘通過考慮相鄰兩迭代點列的技巧，發(fā)現(xiàn)只要FR方法的每個搜索方向下降，則任意兩個相鄰迭代點列中至少有一個使得充分下降條件成立，從而證明方法全局收斂。由于°=12的強Wolfe線搜索能保證FR方法在每一迭代點列產(chǎn)生一個下降方向，因此。=12的強Wolfe線搜索下FR全局收斂。但若°>12，戴彧虹和袁亞湘給出了反例，即無法保證FR方法的全局收斂性。此外，戴彧虹和袁亞湘提出了廣義線搜索下的FR方法，并證明了采用廣義Wolfe線搜索或廣義Armijo線搜索的FR方法全局收斂。2.2PRP方法和HS方法PRP方法中，七的選取按公式:gT(g—g)gPRP= __^k—J-k15PRP方法是目前認為數(shù)值表現(xiàn)最好的共軛梯度法之一。當算法產(chǎn)生一個小步長時，由PRP方法定義的搜索方向人自動靠近負梯度方向，從而有效避免了FR方法可能連續(xù)產(chǎn)生小步長的缺陷。由此，Powell證明了當步長，廣七+1一七趨于零時，PRP方法全局收斂，且采用精確線搜索的PRP方法對一致凸函數(shù)全局收斂。但對一般非凸函數(shù)，Powell舉出了三維情況下的反例，表面即使按Curry原則選取步長因子，PRP方法可能在六點附近循環(huán)，且任意一點都不是目標函數(shù)的穩(wěn)定點。當n=2時，Powel證明了采取Curry準則的PRP方法對一般非凸函數(shù)的收斂性。由于當線搜索精確且n=2時，Broyden凸簇擬牛頓法會產(chǎn)生和PRP方法完全相同的點列，戴彧虹利用了Powell提出的二維例子，說明了采取Wolfe非精確線搜索的Broyden凸簇擬牛頓法對一般非凸函數(shù)不必收斂。如果使用非精確線搜索如強Wolfe線搜索，戴彧虹舉出例子表明，即使f(x)一致凸，而且參數(shù)"^①，1)充分小，PRP方法都有可能產(chǎn)生一個上升搜索方向。進而，如果要求每一搜索方向都下降，則采取非精確線搜索的PRP方法對凸函數(shù)收斂。對一般非凸函數(shù)，Powell建議限制PRP方法中的參數(shù)叮"為非負P=max{Pprp,0}避免當K'很大時，相鄰兩搜索方向會趨于相反。Gilbert和Nocedal考慮了Powell的上述建議，并在適當?shù)乃阉鳁l件下，建立了上述修正PRP方法對一般非凸函數(shù)的全局收斂結果。然而，Gilbert和Nocedal也舉出例子表明，即使對于一致凸的目標函數(shù)，叮"也可能為負。于是，Grippo和Lucidi設計了一種Armijo型的線搜索，即每次迭代步長滿足：以=max{人jK*';j=0,1<--}t>0,槌(0,1)』」I2并證明了原始PRP方法在該線搜索下，對一般非凸函數(shù)全局收斂。根據(jù)Armij。型線搜索下的性質(zhì)，可得出存在一個常數(shù)，滿足每次迭代的步長均大于此常數(shù)。由此給出新的性質(zhì)，即取常數(shù)步長因子的PRP方法在每次迭代都產(chǎn)生一個下降方向，并且全局收斂。HS方法中，七的選取按公式：gTyPH=kk1,(y=g-g)

kdTyk-1k k-1kk-1與PRP方法相比，HS方法的一重要性質(zhì)為共軛關系式：dlyk_1=0。不論線性搜索是否精確，總是成立。但HS方法的理論性質(zhì)和計算表現(xiàn)與PRP方法很類似。戚厚鐸等考慮了修正的HS方法：P=max{0,min{Phs,-}}gkll并在無充分下降條件下，建立了方法的全局收斂性。CD方法中，七的選取按公式:=_"kdt.gCD又稱共軛下降法，由Fletcher在1987年引入。CD法一個很重要的性質(zhì)為:只有強Wolfe條件中的參數(shù)。<L方法在每次迭代便產(chǎn)生一個下降搜索方向，這與FR方法和PRP方法不同，因為FR方法和PRP方法在這時對一致凸函數(shù)都有可能產(chǎn)生一個上升搜索方向，如2.1和2.2中所述。采取強Wolfe非精確線搜索的共軛梯度法，只要每個搜索方向下降，即可保證收斂性。故這一結論為CD方法的收斂性分析提供了一個非常有力的工具，不過采取強Wolfe非精確線搜索的CD方法，無法保證其全局收斂性。對于推廣的Wolfe線搜索，若參數(shù)滿足*<"2=0?？傻玫?鄧件V叩。類似于FR方法中的收斂性證明，可以看出，當滿足參數(shù)滿足上述式子時，CD法必全局收斂。相反的，若參數(shù)滿足。1-1，可構造出例子，使做。方法收斂于一個非穩(wěn)定點，表明°1<1是必要的。若參數(shù)滿足°2>0，戴彧虹和袁亞湘發(fā)現(xiàn)，這時可能以指數(shù)級數(shù)增長。由此，他們給出一般性證明，表面對任意正常數(shù)°2，滿足推廣的Wolfe線搜索的CD方法不必收斂。此外，戴彧虹和袁亞湘構造了一個凸二次函數(shù)的反例。表明°2=0是必要的。由上可見，雖然一般參數(shù)的強Wolfe條件即可保證CD方法在每步產(chǎn)生一個下降搜索方向，但CD方法的收斂性質(zhì)并不好。此外，當線搜索精確時，°件三°筍，由2.1已FR方法的若干缺陷可知，CD方法有著和FR方法同樣的數(shù)值缺點，即可能連續(xù)產(chǎn)生許多小步長而不恢復。CD方法在實際的數(shù)值表現(xiàn)中與FR方法相差不大。但對CD方法的研究，找到了一種新的共軛梯度法。2.4。丫方法DY方法中，°k的選取按公式:dry "k-1=gk-gk-1)k-1k-1°k的選取是在CD方法的研究中得到的。CD方法在強Wolfe線搜索時的收斂性質(zhì)不佳。為解決這個問題，即希望每次總能產(chǎn)生一個下降方向。戴彧虹和袁湘江降低了線搜索條件，在Wolfe線搜索下研究了共軛梯度法。由上所述，每次總是產(chǎn)生一個下降方向，故°k的選取需使得dlgk<0滿足，一1|g||2+°gTd<0人c=||g ||2..，° °>0T>gTd由此得11kkk k-1 。令kkk，且約束k。由此得kkk-1。結合Wolfe線搜索條件，得到了上述島選取的形式。當線搜索精確時，DY方法中島的公式等價于FR公式，由此知DY方法是對應著一個新的共軛梯度法。此方法由戴彧虹和袁湘江于1995年提出，且他們嚴格證明了采取Wolfe線搜索的DY方法在每一步均產(chǎn)生一個下降方向，并且方法全局收斂。故DY方法不使用強Wolfed精確線搜索而僅使用Wolfe非精確線搜索也可得到很好的收斂效果，此結果進一步揭示了非線性共軛梯度法不同于線性共軛梯度法的一面。對于DY方法，戴彧虹在不使用任何線搜索的情況下，證明了方法在遠離最優(yōu)點時，充分下降條件必對大部分迭代點列成立。由此性質(zhì)知DY方法在一般的線搜索下全局收斂。一些方法的改進和創(chuàng)新3.1雜交共軛梯度法由上述收斂性部分中可知，關于參數(shù)吧有如下計算公式：gII2 gT(g—g) o2 QTVPFR=kpPRP= ^b—1 DY-gk 什HS-g，y1DDY—kpHSkk—1-kg2 1°II2kdTy k dTyk—1， k—1 ， k—1k—1， k—1k—1其中，ykLk—gk—1。它們對應的共軛梯度法依次為FR、PRP、DY和HS方法。PRP方法是數(shù)值表現(xiàn)最好的非線性共軛梯度法之一，但即使采取精確線搜索也不一定收斂。相反的，雖然FR方法的數(shù)值表現(xiàn)不佳，但其全局收斂性很好。一個結合這兩辦法的想法自然就產(chǎn)生了，為了結合這兩方法的優(yōu)點，TouatiAhmed和Storey考慮結合PRP方法和FR方法，首先引入了雜交共軛梯度法，對Pk的選取滿足如下要求：Pk=max{0,min{PPRP，叩}}這方法確實可以避免FR方法可能連續(xù)產(chǎn)生小步長的缺點。由此，Gilbert和Nocedal進一步研究了雜交方法對P的選取采用了.P—max{—pfr，min{pPRP,PFR}}進步研究J雜交方法，對k的選取采用了：k k kk這種方法的好處在于，允許了參數(shù)Pk取負數(shù)。然而，Gilbert和Nocedal進行了大量數(shù)值實驗，其結果表明，這種方法的數(shù)值表現(xiàn)雖然比FR方法好一些，但仍比PRP方法差很多。另外，戴彧虹和袁亞湘研究了。丫方法和HS方法的雜交共軛梯度法，這種方法比上述FR方法和PRP方法的雜交共軛梯度法好在，它們不要求線搜索滿足強Wolfe條件，而只需線搜索滿足Wolfe條件。他們選取的Pk滿足P—max{0,min{Phs,Pdy}}且他們進行的大量數(shù)值試驗表面DY方法和HS方法的雜交共軛梯度法的計算表現(xiàn)非常好。在對較為困難的問題時，它比PRP方法還要好很多。3.2共軛梯度法簇眾所周知，大部分擬牛頓法可以用統(tǒng)一的表達式表示，并可統(tǒng)一進行研究。較大的擬牛頓法有Huang簇和Wu簇o根據(jù)擬牛頓法的簇類而聯(lián)想到，共軛梯度法是否

存在簇類，由此可以統(tǒng)一對其研究？戴彧虹和袁亞湘研究了單參數(shù)共軛梯度法簇，F(xiàn)R方法和DY方法關于參數(shù)七的計算公式其分子和分母的下標只相差1，于是它們可以形式地表為：k _i。由此取$F=l|gjI2^DY=一gTd此取kk"，k kk。引入?yún)?shù)人，令2以略+（1_X）畛，由此定義了一簇共軛梯度法，它可看作FR方法和DY方法的某種線性組合。由此導出的七滿足=釧g||2+（i—人沖yk_1 k_1k_1在推廣的Wolfe線搜索下，戴彧虹和袁亞湘研究出了如下性質(zhì)。當人>0,氣+b2婦時，每一個搜索方向dk為下降方向且方法在下述意義下收斂：limifg』=0（*）:k當X<0,（匕+七）*2匕_1時，方法在（*）下收斂。由此，對任意的人，參數(shù)滿足*_1-（C1+G2）X-1，則每一個搜索方向均為下降方向，且方法在（*）下收斂。此外，Nazareth視FR方法、PRP方法、HS方法和DY方法為四種主要的共軛梯度法，并提出了兩個參數(shù)的共軛梯度法簇。戴彧虹基于上述四種方法以及CD方法和LS方法等六種形式較為簡單的共軛梯度法，提出了三參數(shù)共軛梯度法簇。3.3最短余量法最短余量法最早由Hestenes在1980年提出，其中的迭代方向與上述方法不同，有d如下形式：k—gd如下形式：k—g+%dk1,0<n1+叩 kk且d1=—g1。此種形式中，若線性搜索精確，不難得出:IglI2 k— idJF。當線搜索精確且目標函數(shù)為嚴格凸二次函數(shù)時，上述方法定義的迭代方向dk是其頂點分別為—g1，…—gk的（k-1）維單純形中的最短向量。最短余量法中的方向d也可寫為如下形式.d=Nr{_g,d}其中Nr{a,b}最短余量法中的方向k也可寫為如下形式：k kk_1，其中滿足網(wǎng){a,b}l=min{%a+（1—入洌:0-x-1}。為了研究當目標函數(shù)為一般非線性

函數(shù)時，最短余量法對應于何種標準的共軛梯度法，并研究其他標準共軛梯度法，Pvfl^k在迭代方向中引入了一個參量P 即考慮.d=Nr{-g,pd}pytiaK在迭代方向中引入了 |參量k，即考慮：k kkk-i函數(shù)時，最短余量法對應于何種標準的共軛梯度法，并研究其他標準共軛梯度法，Pvfl^k在迭代方向中引入了一個參量P 即考慮.d=Nr{-g,pd}pytiaK在迭代方向中引入了 |參量k，即考慮：k kkk-i。與之前的共軛梯度法相比，即迭代方向由吧參數(shù)產(chǎn)生的方法，當線搜索精p=UL_1確時，最短余量法中的參數(shù)pk滿足關系：k低k」F°k，由于。F的選取，更BFRP=^r進一步知： ”k。由此得出結論：如果Bk=叩，則Pk三1。故當線搜索精確時，原始的最短余量法對應于FR方法。稱之為最短余量法的FR格式或FRSR方法。p-JNL令B=B:即，則kgT",當線搜索精確且目標函數(shù)為二次凸函數(shù)時，這種kk， kk—1， ，方法退化為線性共軛梯度法。稱之為最短余量法的PRP格式或PRPSR方法。=±JL\gTykk—1pk此外，考慮方法。且這些方法有統(tǒng)一的算法，如下:，則這種方法被稱為最短余量法的PRP+格式或PRP+SR步1：IG{1,2,3},bG(0,1],bG[0,1),8G[0,1);XGRn,d=-g,k:-1,J:-0.取 1 2 1 1 1」匕C七口REJg<8 /吉 壬11 壬rh 土由 iLA?/~k 。>0X—X+。d步2：如果齡k，停；利用某種線搜索方法求k; k+1 kk步3：測試gTdk-1v"g』dk-』，若不成立，J:-0；若1-2,3，測試gTyk-1>b2HgklI2，若不成立，j:-1；若J:=1;令dk+1=-gk+1，置J:-0,轉步2。步4：步5：若1=1，pk+1=1；若1=2，Pk+1gT+1yk；若1-3，Pk+1=gT+1Xk+1計算||g ||2+PgTd— k+1 k+1_k+1 kllg+PdII2.k+1k+1k’’ ；d=-(1-X)g +Xpd]k+1 k+1k+1 k+1k+1k；K=K+1，轉步2。對于非精確線搜索的情況，戴彧虹和袁亞湘分析了三種線搜索下最短余量法的收斂性。三種線搜索為強Wolfe線搜索（1）,步長因子有界的Wolfe線搜索（2）以及Armijo線搜索（3）,即給定參數(shù)入日。，1）*^。，1），取口廣扁，其中m為使得f亳+扁叩—fk-"虬%成立的最小負整數(shù)。當目標函數(shù)下方有界，導數(shù)滿足Lipschitz連續(xù)時。算法滿足1=1,bi=1,8=0時，三種線搜索下有!iminf'叩=0成立。k。當目標函數(shù)下方有界，導數(shù)滿足Lipschitz連續(xù)時。算法滿足1='b1=】力2=0,8=。時，在（2）和（3）的搜索下有k^1g^'=0成立。當目標函數(shù)二次連續(xù)可微，水平集"={xeRn:f（x）＜f（氣）}有界，并且存在常數(shù)0〈七小2，使得叩圳2VyV2f⑴y＜^J|y||2,W5,ycRn，其中［為］或2，b—1,b=0,8=0. mIgkII。冊1 2 如果線搜索為Wolie線搜索或（3）的搜索，則有sk成立。當目標函數(shù)的水平集1={ERn:f（x）＜f（x1）}有界，導數(shù)Lipschitz連續(xù)，算法滿足I=3,b=1,b=0,8=0.對/1）的線搜索liminf||叩=0成立足1 2 對（1）的線搜索，kT8 k成立。由此分析得，采取精確線搜索的PRPSR算法對一般非凸函數(shù)不一定收斂，但采取（2）或（3）的線搜索的PRPSR算法對一般非凸函數(shù)全局強收斂。采取強Wolfe線搜索的PRPSR算法不一定收斂，但prp+sr算法全局收斂。3.4Beale-Powell重新開始方法如果共軛梯度算法在每口步沿負梯度方向作一重新開始，進一步，如果線搜索精確或漸進精確，則重新開始的共軛梯度算法的收斂速度可從原來的線性提高到n步超線性收斂。可知重新開始的共軛梯度算法無論是在全局收斂性還是在收斂速度方面，都比原來的共軛梯度算法具有更好的性質(zhì)。但這種重新開始策略具有一些缺點，一是它舍去了算法沿前一次搜索方向搜索得到的二階導數(shù)信息，二是重新開始的頻率一般與目標函數(shù)的性質(zhì)有關，而不是簡單地取目標函數(shù)的維數(shù)。故如何設計一種更有效的重新開始方法，引起了不少人的興趣。Bgl°給出了一個方法其中迭代方向d=一g+Bd+Yd 其中-為小于kBeale給口出了|方法，其中迭代力向kkkk-1kt，其中t為小于k的一個整數(shù)。但McGuire和Wolfe就Beale的三項方法作了數(shù)值試驗，數(shù)值結果非常令人失望。之后Powell通過引入一個新的重新開始準則，即如果glgk-J＜司gkF（s（0,1）），不成立，也使方法重新開始，克服了McGuire和Wolfe的困難，且獲得了令人滿意的數(shù)值結果。共軛梯度法還