一个修改的HS共轭梯度算法及其收敛性

吴 庆 军

(玉林师范学院, 数学与信息科学学院, 广西 玉林 537000)



一个修改的HS共轭梯度算法及其收敛性

吴 庆 军*

(玉林师范学院, 数学与信息科学学院, 广西 玉林 537000)

给出一个修改的HS共轭梯度方法,该方法能保证参数βk非负且搜索方向在不需要任何线搜索下具有充分下降性.在适当条件下证明此方法对一般目标函数具有全局收敛性,同时给出数值检验结果.

共轭梯度; 充分下降; 全局收敛性

求解问题

minf(x),x∈Rn,

(1)

其中,f(x)连续可微.共轭梯度法首先由Hestence和Stiefel[1]提出用来求解线性方程组问题,后来被推广到用于求解非线性问题,此类方法因具有结构简单且求解效果较好等优点而被广泛应用.该方法的迭代公式是

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的数值表现比较优越但收敛性不理想,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在Ω上有下界且连续可微,梯度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)式,则

联立此不等式和(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的表现比较理想,随着初始点的不同,迭代次数并没有太大改变.另外最终函数值也非常接近最优值,可以说算法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.