李倩

【摘要】本文通過構(gòu)造含有雙參數(shù)的公式βk，提出了一個(gè)新的共軛梯度算法.該法具有充分下降性，與所選用的搜索準(zhǔn)則及目標(biāo)函數(shù)f凸性均無關(guān)，在強(qiáng)Wolfe線搜索下給出該算法具有全局收斂性.

【關(guān)鍵詞】無約束優(yōu)化;共軛梯度法;全局收斂性

【分類號(hào)】AMS（1991）49M，90C45

【中圖分類號(hào)】O221.1 【文獻(xiàn)標(biāo)識(shí)碼】A

1.引 言

考慮無約束優(yōu)化問題：

minf（x），x∈Rn，其中f： Rn→R1，f∈C1.

構(gòu)造迭代算法 xk+1=xk+αkdk，其中dk為搜索方向，αk為搜索步長(zhǎng).對(duì)αk和dk的不同選擇就構(gòu)成了不同的算法.60年代Fletecher等人提出一種共軛梯度算法，其基本結(jié)構(gòu)是：dk=-gk+βkdk-1，當(dāng)βk選擇不同的公式時(shí)就得到不同的共軛梯度算法.幾個(gè)代表性的公式是：

βHSk=gTk（gk-gk-1）dTk-1（gk-gk-1），βFRk=‖gk‖2‖gk-1‖2，

βPRk=gTk（gk-gk-1）‖gk-1‖2，

βCDk=-‖gk‖2gTk-1dk-1，

βLSk=-gTk（gk-gk-1）dTk-1gk-1，βDYk=‖gk‖2dTk-1（gk-gk-1）.

這些公式分別在文獻(xiàn)[1-3]給出，這些方法的收斂性在文獻(xiàn)[1-2，4-6]中已經(jīng)給出.

共軛梯度法適于求解大規(guī)模無約束優(yōu)化問題.

2.算法與性質(zhì)

本文總假設(shè)目標(biāo)函數(shù)滿足以下假設(shè)：

假設(shè)（a）水平集L1=x∈Rnf（x）≤f（x0）有下界，其中x0為初始點(diǎn);

（b） 在水平集L1的一個(gè)鄰域U內(nèi)，f連續(xù)可微，其導(dǎo)數(shù)函數(shù)g滿足Lipschitz條件，即存在常數(shù)L>0，使：‖g（x）-g（y）‖≤L‖x-y‖，x，y∈U.

本文步長(zhǎng)αk由強(qiáng)Wolfe準(zhǔn)則得到：

f（xk+αkdk）≤f（xk）+δαkgTkdk，（1）

gTkdk-1≤-σgTk-1dk-1，（2）

其中0<δ<σ<1.

求解無約束優(yōu)化問題的共軛梯度算法：

Step 1 選一個(gè)初始點(diǎn)x0∈Rn，ε∈（0，1），λ1≥0，λ2≥0，置d0=-g0=-

c2=1+λ11-σσ1-λ2σ，有：c1≥0，c2≥0，

則：c1≤-gTkdk‖gk‖2≤c2.（4）

3.全局收斂性證明

定理2 設(shè)序列g(shù)k，dk 由以上算法產(chǎn)生，步長(zhǎng)αk由強(qiáng)Wolfe準(zhǔn)則得到，設(shè)λ1<σ1-σ，0≤λ2<12σ，σ<12，目標(biāo)函數(shù)f滿足假設(shè)（a）和假設(shè)（b），則對(duì)算法產(chǎn)生的迭代點(diǎn)列有：limk→∞inf‖gk‖=0.

證明：由引理1和（4）式，我們有：

∑∞k=0‖gk‖4‖dk‖2<+∞.（5）

令 tk=‖dk‖2‖gk‖4，（5）式可寫為：∑∞k=01tk<+∞.

用反證法，假設(shè)定理2不成立，那么存在一個(gè)常數(shù)γ>0，使

‖gk‖≥γ，由dk=-gk+βkdk-1 兩邊平方取模并除以‖gk‖4得：

‖dk‖2‖gk‖4=1‖gk‖2-2βkgTkdk-1‖gk‖4+（βk‖dk‖）2‖gk‖4，

tk≤1‖gk‖2+2gTkdk-1‖gk‖2‖gk-1‖2+‖dk-1‖2‖gk-1‖4=tk-1+1‖gk‖21+2gTkdk-1‖gk-1‖2≤tk-1+1‖gk‖21+2σgTk-1dk-1‖gk-1‖2≤tk-1+1‖gk‖2（1+2σ·max（c1，c2）），

tk≤1+2σ·max（c1，c2）∑ki=01‖gk‖2≤[1+2σ·max（c1，c2）]k+1γ2，

于是有：∑∞k=01tk=+∞，矛盾.所以有：limk→∞inf‖gk‖=0.

【參考文獻(xiàn)】

[1]Hestenese M R，Stiefel E.Method of conjugate gradient for solving linear equations[J].J Res Nat Bur Stand，1952，49：409-436.

[2]Polak E，Ribigravere G.Note sur la convergence de directions conjug Rev[J].Francaise Informat Recherche Operationelle，1969，16：35-43.

[3]Polyak BT.The conjugate gradient method in extreme problems[J].UUSR Comput Math and Math Phys，1969，9：94-112.

[4]Fletcher R.Practial method of optimization[M].2nd edtition.New York：Wiley，1997.

[5]Liu Y，Storey C.Efficient generalized conjugate gradient algorithms[J].Journal of Optiimization Theory and Appplication，1992，69：129-137.