共軛梯度法和最速下降法的混合算法

1、 收稿日期:1998-10-15第一作者:男,1970年生,碩士,講師共軛梯度法和最速下降法的混合算法歐志英嚴(yán)克明王柏巖(甘肅工業(yè)大學(xué)基礎(chǔ)科學(xué)系,蘭州730050摘要將共軛梯度法與最速下降法有機(jī)地結(jié)合起來,構(gòu)造了一種共軛梯度法和最速下降法的混合算法,并證明了該算法的全局收斂.混合算法既提高了共軛梯度算法的收斂速度,又解決了目標(biāo)函數(shù)“性態(tài)不優(yōu)”時(shí),最速下降法難以求解的問題.同時(shí)也可以看到共軛梯度法與最速下降法僅僅是混合算法的特例.關(guān)鍵詞混合算法共軛梯度法最速下降法全局收斂分類號(hào)O224FR 算法是Fletcher 和Reev s 共同提出的一種共軛梯度算法1.由于FR 算法具有二次終止性,內(nèi)存需

2、要量小,主要存儲(chǔ)四個(gè)n 維向量(x k ,g k ,g k -1,p k -1,程序簡(jiǎn)單,具有較快的收斂速度,因此它是解決無約束優(yōu)化問題,特別是大規(guī)模問題的一個(gè)重要方法.但是FR 算法的計(jì)算效果總不如人意,當(dāng) f (x k 較小時(shí),FR 算法收斂較慢.最速下降法具有較高的局部收斂速度,但在有的情況下全局收斂速度不高,如目標(biāo)函數(shù)“性態(tài)不優(yōu)”時(shí),其收斂速度就較慢.本文給出一種將共軛梯度法與最速下降法有機(jī)地結(jié)合起來的新算法混合算法,在保證相同的計(jì)算量前提下,它將進(jìn)一步提高FR 算法的計(jì)算效果.1算法混合算法的步驟如下:1取初始點(diǎn)x 0R n ,T >0,U >0,置k =1;2計(jì)算g k

3、 =g (x k = f (x k ;3若g k =0,則停止計(jì)算,否則置:p k =-g k +U k -1p k -1其中,U k -1=0(k =1g k 2g k -12(k >1;4若 f (x k 較大,取U 12,1;否則,取U 0,12;5若d 1(d 為目標(biāo)函數(shù)f (x 的Hessian 陣的條件數(shù),取T 0,12;否則,取T 12,1;6p k =-T g k +U p k ;第25卷第1期7一維搜索,求k ,使得f (x k +k p k =min f (x k +p k |>0;8置x k +1=x k +k p k ,k =k +1,返回步驟2.對(duì)于上述算

4、法,給出以下幾點(diǎn)注釋:1p 1,p 2,p k ,是共軛方向.從文1中已知FR 算法得到的p 1,p 2,p k ,是共軛方向,滿足:(p i ,p j G =0(j i 因而可得知:(p i ,p j G =0(j i 即p 1,p 2,p k ,是共軛方向.2p 1,p 2,p k ,是目標(biāo)函數(shù)的下降方向.(-g k ,p k =(-g k ,-T g k +U p k =(-g k ,T g k +(-g k ,U p k =T g k 2+U (-g k ,-g k +k -1j =1U jp j =g k 2>02混合算法的全局收斂引理1設(shè)函數(shù)f (x 二階連續(xù)可微, f (x

5、 滿足Lipschitz 條件,且k =1cos 2d k ,-g k <+,其中d k 為搜索方向.則利用共軛梯度法和精確線性搜索所得到的點(diǎn)列x k 必有限終止,或者下面兩極限必有一為真2:lim k f (x k =-lim k inf f (x k =0由引理1可知,只要夾角d k ,-g k 不為2,則共軛梯度算法在滿足引理1的條件下是全局收斂的.定理1混合算法在滿足引理1的條件下是全局收斂的.證明由于(-g k ,p k g k 2,因此,co s -g k ,p k 0,則-g k ,p k 不為2.從引理1知定理1成立.3混合算法的計(jì)算效果分析從算法中可知,混合算法和FR

6、算法的計(jì)算量大致相同,但計(jì)算效果卻有不小的差異.一般來說前者優(yōu)于后者,為說明這個(gè)問題,舉例如下3:考慮min x R 2f (x ,其中在圓域D 內(nèi)f (x =12(x 21+x 22,在D 的邊界是連續(xù)可微函數(shù),在D 的邊界上是光滑聯(lián)接的.設(shè)想從D 的邊界外某一點(diǎn)出發(fā),經(jīng)過若干次迭代后達(dá)到D 內(nèi)某點(diǎn)x k ,并且已經(jīng)確定了共軛方向p k ,現(xiàn)從x k 出發(fā),分別用FR 算法和混合算法進(jìn)行計(jì)算,并對(duì)它們的進(jìn)展情況作出比較.p k g k co s k =(p k ,-g k =g k 2sec k =p k g k ·90·甘肅工業(yè)大學(xué)學(xué)報(bào)第25卷g k p k co s

7、k =(p k ,-g k =(T +U g k 2sec k =-T g k +U p k (T +U g k 1g k <p k g k =sec k 因此,k >k ,并且可以證明k =k +1.這說明了對(duì)于FR 算法來說,即使對(duì)于性態(tài)很好的目標(biāo)函數(shù),倘若某次搜索方向很不理想,仍會(huì)使得以后的每次迭代都只能取得很小的進(jìn)展.但是對(duì)于混合算法則不一樣,它具有朝最速下降方向靠攏的性質(zhì).由此可見,混合算法要比FR 算法的計(jì)算效果優(yōu).同時(shí)還可看到:T =0時(shí),混合算法就是FR 算法;U =0時(shí),混合算法就是最速下降法.4結(jié)論1最速下降法和FR 算法僅是混合算法的特例.2混合算法的搜索方向

8、是關(guān)于目標(biāo)函數(shù)f (x 的Hessian 陣共軛.3混合算法的計(jì)算效果要比FR 算法的計(jì)算效果優(yōu),且全局收斂;但是否具有比FR 算法更高的Q 收斂速度,還需要進(jìn)一步探討.參考文獻(xiàn)A mixed method of conjugate gradient methodand steepest descent methodOu Zhiying ,Yan Keming ,Wang Baiyan(Dept.o f Basic Sciences,Ga nsu U niv.of T ech.,Lanzh ou 730050Abstract The co njugate g radient method an

9、d the steepest descent method a re combined ,and a mix ed method o f conjug ate g radient m ethod and steepest descent is created ,and its g lobal conv ergence is prov ed.The mixed m ethod raise the co nv erg ent rate o f the co njugate g radient method,and solve the problem which the steepest descent method can no t solv e in the conditio n with badly cha racteristics for the o bjectiv e function .In the m eantime ,it can be seen that the co njuga te g radient m ethod o r steepest descent metho d is a special case o f t