一個具有充分下降性的共軛梯度法及其全局收斂性

李倩

【摘要】本文通過構造含有雙參數的公式βk，提出了一個新的共軛梯度算法.該法具有充分下降性，與所選用的搜索準則及目標函數f凸性均無關，在強Wolfe線搜索下給出該算法具有全局收斂性.

【關鍵詞】無約束優化;共軛梯度法;全局收斂性

【分類號】AMS（1991）49M，90C45

【中圖分類號】O221.1 【文獻標識碼】A

1.引 言

考慮無約束優化問題：

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

構造迭代算法 xk+1=xk+αkdk，其中dk為搜索方向，αk為搜索步長.對αk和dk的不同選擇就構成了不同的算法.60年代Fletecher等人提出一種共軛梯度算法，其基本結構是：dk=-gk+βkdk-1，當βk選擇不同的公式時就得到不同的共軛梯度算法.幾個代表性的公式是：

β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）.

這些公式分別在文獻[1-3]給出，這些方法的收斂性在文獻[1-2，4-6]中已經給出.

共軛梯度法適于求解大規模無約束優化問題.

2.算法與性質

本文總假設目標函數滿足以下假設：

假設（a）水平集L1=x∈Rnf（x）≤f（x0）有下界，其中x0為初始點;

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

本文步長αk由強Wolfe準則得到：

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

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

其中0<δ<σ<1.

求解無約束優化問題的共軛梯度算法：

Step 1 選一個初始點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 設序列gk，dk 由以上算法產生，步長αk由強Wolfe準則得到，設λ1<σ1-σ，0≤λ2<12σ，σ<12，目標函數f滿足假設（a）和假設（b），則對算法產生的迭代點列有：limk→∞inf‖gk‖=0.

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

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

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

用反證法，假設定理2不成立，那么存在一個常數γ>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.

【參考文獻】

[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.