馬文亞

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

其中f:Rn→R是一個連續(xù)可微的函數(shù).

共軛梯度法是求解問題(1)的具有迭代格式

的一類方法,其中αk是某種線搜索下的步長,dk滿足

其中βk是共軛參數(shù).βk的不同取法對應(yīng)于不同的非線性共軛梯度法.著名的PRP[1,2]、HS[3]、LS[4]方法的參數(shù)βk分別為

其中,‖·‖為歐幾里得范數(shù),yk-1=gk-gk-1.

最近,文獻(xiàn)[5]和[6]提出如下βk公式

在共軛梯度法的許多理論分析和數(shù)值實(shí)現(xiàn)中,常常使用強(qiáng)Wolfe線搜索.其要求αk滿足

和

其中0＜δ≤σ＜1.

共軛梯度法收斂性分析中常用的充分下降性條件為

受文獻(xiàn)[5,6]啟發(fā),本文提出帶雙參數(shù)的新的βk公式

其中參數(shù)μ,μ2,μ1+μ2∈ [0,1].

1 算法

初始步 給定初始點(diǎn)x0∈Rn,μ1,μ2∈[0,1](且滿足μ1+μ2∈[0,1])δ∈(0,1),σ∈(0,1),ε＞0.令d0=-g0,k=0.

步驟1 若‖g0‖≤ε,則停止;

步驟2 由強(qiáng)Wolfe線搜索準(zhǔn)則計算步長αk;

步驟3 令xk+1=xk+αkdk,若‖gk+1‖≤ε,則停止;

步驟4 由式(9)計算βk+1,由式(3)計算dk+1;

步驟5 令k=k+1,轉(zhuǎn)步驟2.

2 算法的收斂性

為了證明新算法的全局收斂性,首先給出兩個假設(shè):

(A)水平集Ω={x∈Rnf( x)≤f( x0)}有下界,其中x0∈Rn為初始點(diǎn).

(B)f在水平集Ω的一個領(lǐng)域Ν內(nèi)連續(xù)可微,且其梯度g滿足Lipschitz連續(xù),即存在常數(shù)L＞0,使得

引理1[7]假設(shè)(A)-(B)成立,設(shè)序列 gk{}和 dk{}由上述算法產(chǎn)生,并設(shè)步長αk由強(qiáng)Wolfe線搜索計算.則

引理2 考慮上述算法生成的序列 gk{}和 dk{},則存在常數(shù)c＞0,使得?k≥1,式(8)成立;?k≥2,有βk≥0.

性質(zhì) (*)[8]考慮由式(2)-(3)構(gòu)成的迭代方法,假設(shè)

如果存在常數(shù)b＞1和λ＞0,使得對所有的k有|βk|≤b,以及成立,則稱該迭代方法具有性質(zhì)(*).

引理3 假設(shè)(A)-(B)成立,考慮上述算法生成的序列 βk{},假定式(12)成立,則 βk{}滿足性質(zhì)(*).

證 設(shè)q=cμ1+cμ2(1-σ)+(1-μ1-μ2),則0＜q＜1.取.由式(6),(7),(9),(12),Cauchy-Schwartz不等式和引理1可得

設(shè) ‖sk-1‖ ≤λ,則

定理 假設(shè)(A)-(B)成立,設(shè)序列 g k{}和 dk{}由上述算法產(chǎn)生,則

證 由引理1、引理2、引理3知,結(jié)論成立.?

參考文獻(xiàn):

[1]Polyak B T.The conjugate gradient method in extreme problems[J].USSR Computational Mathematics and Mathematical Physics,1969,9(4):94-112.

[2]Polak E,Ribiere G.Note sur la convergence de directions conjugues[J].Rev Francaise Informat Recherche Operatinelle,1969,16:35-43.

[3]Hestenes M R,Stiefel E L.Methods of conjugate gradients for solving linear systems[M].Washington,DC:National Bureau of Standards,1952:409-436.

[4]Liu Y L,Storey C S.Efficient generalized conjugate gradient algorithms,Part 1:Theory[J].Journal of Optimization Theory and Applications,1991,69(1):129-137.

[5]Huang H D,Li Y J,Wei Z X.Global Convergence of a Modified PRP Conjugate Gradient Method[J].Journal of Mathematical Research and Exposition,2010,30(1):141-148.

[6]Wei Z X,Huang H D,Tao Y R.A Modified Hestenes-Stiefel Conjugate Gradient Method and Its Convergence[J].Journal of Mathematical Research and Exposition,2010,30(2):297-308.

[7]Zoutendijk G.Nonlinear programming,computational methods[J].Integer and Nonlinear Programming,1970,143(1):37-86.

[8]Gilbert J C,Nocedal J.Global convergence properties of conjugate gradient methods for Optimization[J].SIAM Journal on Optimization,1992,2(1):21-42.