一個修改的HS共軛梯度算法及其收斂性

吳 慶 軍

(玉林師范學院, 數學與信息科學學院, 廣西 玉林 537000)

?

一個修改的HS共軛梯度算法及其收斂性

吳 慶 軍*

(玉林師范學院, 數學與信息科學學院, 廣西 玉林 537000)

給出一個修改的HS共軛梯度方法,該方法能保證參數βk非負且搜索方向在不需要任何線搜索下具有充分下降性.在適當條件下證明此方法對一般目標函數具有全局收斂性,同時給出數值檢驗結果.

共軛梯度; 充分下降; 全局收斂性

求解問題

minf(x),x∈Rn,

(1)

其中,f(x)連續(xù)可微.共軛梯度法首先由Hestence和Stiefel[1]提出用來求解線性方程組問題,后來被推廣到用于求解非線性問題,此類方法因具有結構簡單且求解效果較好等優(yōu)點而被廣泛應用.該方法的迭代公式是

xk+1=xk+αkdk,k=0, 1, 2, …

xk是第k次迭代點,αk>0是步長,dk是具有下面定義形式的搜索方向

(2)

其中,βk∈R是參數,根據βk的選取不同而稱為不同的共軛梯度法.下面給出著名的PRP和HS共軛梯度方法中βk的定義:

其中,gk=f(xk)和gk+1=f(xk+1),分別表示函數f(x)在xk和xk+1的梯度值,‖.‖是歐氏向量范數.PRP和HS的數值表現比較優(yōu)越但收斂性不理想,PRP方法的數值表現更為理想,常常被人們用于實際問題求解.許多學者都希望找到數值表現可與PRP相媲美同時性質又比其好的方法(見文獻[4 -14] 等).Yuan[11]給出了一個修改的PRP公式:

(3)

Wei等[10]也給出一個新的共軛梯度公式:

(4)

此公式能克服原PRP公式參數可能為負數的缺陷.結合上面兩個公式,給出一個新的共軛梯度公式:

(5)

1算法

算法1(修改的HS共軛梯度算法)

步驟0 給定x0∈Rn,δ∈(0, 1/2),σ∈(δ, 1) 和終止參數ε>0.令d0=-g0=-f(x0),置k∶=0.

步驟1 若‖gk‖ ≤ε,停止.

步驟2 利用下面的WWP線搜索技術尋找步長αk:

(6)

和

(7)

步驟3 令xk+1=xk+αkdk.如果‖gk+1‖ ≤ε,停止.

步驟4 利用下面公式計算搜索方向

(8)

步驟5 置k∶=k+1,轉步驟2.

2收斂性分析

下面的引理指出修改的HS方向具有充分下降性.

引理1對k≥ 0,滿足下式

(9)

其中,c> 0是常數.

(10)

假設條件(A): (i) 水平集Ω={x∈Rn:f(x)≤f(x0)}有界;

(ii)f在Ω上有下界且連續(xù)可微,梯度g滿足Lipschitz條件,即存在常數L> 0滿足下式

‖g(x)-g(y)‖ ≤L‖x-y‖, ?x,y∈Ω.

(11)

如果算法1非全局收斂,即存在常數γ> 0滿足

‖gk‖ ≥γ, ?k≥0，

(12)

則有如下結論.

引理2假設條件(A) 滿足,序列 {gk} 和 {dk} 由算法1產生.如果不等式 (12) 成立,則dk≠ 0且

證明 利用 (7)式和Lipschitz條件(11)式,得

αkL‖dk‖2,

利用(9)式,有

代入(6)式,利用函數f有下界,則

(13)

根據(5)式,當k ≥ 1,有

uk+1=rk+1+σkuk,

再由‖uk+1‖=‖ uk‖=1,則

‖rk+1‖=‖uk+1-σkuk‖=‖σkuk+1-uk‖.

(14)

‖uk+1-uk‖ ≤

‖(1+σk)uk+1-(1+σk)uk‖≤

‖uk+1-σkuk‖+‖σkuk+1-uk‖=

2‖rk+1‖.

(15)

又由(9)式和(13)式,得

利用(12)式,則

聯(lián)立此不等式和(15)式,引理2得證.

下面的性質(PP) 由Gilbert和Nocedal[5]給出,具體為:

性質 (PP):考慮(2)的方法,如果

0<γ1≤ ‖gk‖ ≤γ2.

(16)

引理3假設條件(A) 滿足,序列 {gk} 和 {dk} 由算法1產生,若存在常數M> 0滿足

‖sk‖ ≤M1.

(17)

(18)

和

所以修改的HS方法滿足性質 (PP).證畢.

利用假設(A),引理 1～引理3,與文獻 [5] 中的定理3.2的證明類似,不難證得算法1的全局收斂性,下面即可給出本文定理1.

3數值結果

為驗證算法1的有效性,本文給出數值檢驗結果,檢驗的問題是在工程中常用的Benchmark問題:

Benchmark問題:

1) Sphere函數

x*=(0, 0, …, 0), fSph(x*)=0.

2) Schwefel’s函數

xi∈[-65.536, 65.536],

x*=(0, 0, …, 0), fSchDS(x*)=0.

3) Rastrigin函數

xi∈[-5.12, 5.12],

x*=(0, 0, …, 0), fRas(x*)=0.

4) Griewank函數

xi∈[-600, 600],

x*=(0, 0, …, 0), fGri(x*)=0.

這些問題數值結果的終止條件是，‖g(xk)‖ ≤ε或‖g(xk)‖ ≤ε(1+|f(xk)|), ε=10-4.

參數取值:δ=0.1,σ=0.9和μ=0.5.數值結果Tab.1中的各參數含義為:

表1 修改的HS共軛梯度算法實驗結果Tab.1 Modified HS conjugate gradient algorithm experimental results

從上述結果可以看出,算法1的表現比較理想,隨著初始點的不同,迭代次數并沒有太大改變.另外最終函數值也非常接近最優(yōu)值,可以說算法1對求解上述問題是很有效的.

[1] Hestenes 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, Ribiere G. Note sur la xonvergence de directions conjugees[J]. Rev Francaise informat Recherche Operatinelle, 1969, 16:35-43.

[3] Polyak B T. The conjugate gradient method in extreme problems[J]. USSR Comp Math Math Phys, 1969, 9:94-112.

[4] Dai Y, Liao L Z. New conjugacy conditions and related nonlinear conjugate methods[J]. Appl Math Optim, 2001, 43:87 -101.

[5] Hager W W, Zhang H. A new conjugate gradient method with guaranteed descent and an efficient line search[J]. SIAM Journal on Optimization, 2005, 16:170-192.

[6] Hager W W, Zhang H. Algorithm 851: CGDESCENT, A conjugate gradient method with guaranteed descent[J]. ACM Transactions on Mathematical Software, 2006, 32: 113-137.

[7] Li G, Tang C, Wei Z. New conjugacy condition and related new conjugate gradient methods for unconstrained optimization problems[J]. Journal of Computational and Applied Mathemathics, 2007, 202:532-539.

[8] Wei Z, Li G, Qi L. New nonlinear conjuagate formulas for large -scale unconstrained optimization problems[J]. Applied Mathematics and Computation, 2006, 179:407-430.

[9] Wei Z, Li G, Qi L. Global convergence of the PRP conjugates gradient methods with inexact line search for nonconvex unconstrained optimization problems[J]. Mathematics of Computation, 2008, 77:2173-2193.

[10] Wei Z, Yao S, Liu L. The convergence properties of some new conjugate gradient methods[J]. Applied Mathematics and Computation, 2006, 183:1341-1350.

[11] Yuan G L. Modified nonlinear conjugate gradient methods with sufficient descent property for large-scale optimization problems[J]. Optimization Letters, 2009, 3: 11-21.

[12] Yuan G L, Lu X W. A modified PRP conjugate gradient method[J]. Annals of Operations Research, 2009, 166:73-90.

[13] Yuan G L, Lu X W, Wei Z X. A conjugate gradient method with descent direction for unconstrained optimization[J]. Journal of Computational and Applied Mathematics, 2009, 233:519-530.

[14] 趙許培, 楊英芝, 袁功林. 一個新的修正共軛梯度算法[J]. 廣西科學,2012,19(2):104 -107.

A modified HS conjugate gradient algorithms and its convergence

WU Qingjun

(School of Mathematics and Information Science, Yulin Normal University, Yulin, Guangxi 537000)

A modified HS conjugate gradient method is proposed in this paper. The method can ensure that the parameterβkis nonnegative and the search direction possesses the sufficient descent property without any line search. Under suitable conditions， the global convergence of the method for the general function is established. Numerical results are presented to show the efficiency of the proposed scheme．

conjugate gradient; sufficient descent; global convergence

2013-12-16.

廣西自然科學基金項目(2012GXNSFAA053014).

1000-1190(2014)04-0474-05

O242.23

A

*E-mail: wqj600@aliyun.com.