一个带有干扰因子修正PRP共轭梯度法的全局收敛性*

2015-09-16 10:08陈洪敏重庆师范大学数学学院重庆401331
关键词:共轭收敛性全局

陈洪敏(重庆师范大学数学学院,重庆401331)

一个带有干扰因子修正PRP共轭梯度法的全局收敛性*

陈洪敏
(重庆师范大学数学学院,重庆401331)

非线性共轭梯度法是解决大规模优化问题的一种非常有效的方法,提出了一个修正的PRP方法,该参数带有干扰因子,并证明了这一新的参数具有非负性,且在适当条件下,采用Wolfe线搜索,证明该算法具有全局收敛性.

共轭梯度法;强Wolfe条件;Wolfe条件;干扰因子;全局收敛性

1 基础知识

考虑如下的无约束极小化问题:

其中,f:Rn→R是连续可微函数,且其梯度可获得.

非线性共轭梯度法是求解此类问题的一种常用的有效方法,具有算法简便、存储需求小等优点,适用于求解大规模无约束优化问题.共轭梯度法的迭代格式为

其中dk为搜索方向,▽f(xk)简记为gk,βk是一个参数,不同的βk对应着不同的共轭梯度法,αk是通过适当的线搜索获得的步长,通常使用Wolfe线搜索、强Wolfe线搜索.

Wolfe线搜索条件为

强Wolfe线搜索条件为

其中0<δ<σ<1.

传统共轭梯度法的参数公式βk的计算公式有Hestenes-Stiefel(HS)[1],Fletcher-Reeves(FR)[2],Polak-Ribiere(PRP)[3],Dai-Yuan(DY)[4],它们的表达式分别为

这种方法在适当条件下,分别证明算法在Wolfe和Grippo-Lucidi线搜索下是全局收敛的.文献[6]通过对参数βk加入干扰因子得到两个新的βk,公式如式(8):

文献[7]分析了PRP方法,认为限制其参数βk的非负性不仅对方法的全局收敛性起到至关重要的作用,而且能够很容易地保证算法的下降性;文献[8]证明了在充分下降条件被满足,且步长αk满足Wolfe线搜索条件的前提下,算法具有全局收敛性.在接下来的引理中证明了的非负性.

假设目标函数满足下面的假设:

2)目标函数f在Ω的某个领域N是连续可微的,且梯度函数是Lipschitz连续的,即存在常数L>0使得

对任意的x∈N.

证明记θk为gk和gk-1的夹角,即

因为ν≥1,故

引理2(性质*)考虑形如式(2)(3)的方法,并且假设对任意的,则存在常数b>1,λ>0,使得对任意的k≥1都有

在共轭梯度法中,充分下降条件非常重要,其中假设new算法满足式(12).

引理3[8](zoutendijik条件)若假设1)2)成立,考虑形如式(2)(3)的方法,dk是下降方向,αk满足式(5)(6),则

引理4[8]若假设1)2)成立,考虑形如式(2)(3)的方法,αk满足式(5)(6),且满足充分下降条件式(12),若βk满足性质(*)且成立,则存在λ1>0,使得对任意的Δ∈N*和下标k0,都存在指,则

因为ν≥1,故标k≥k0,满足,其中表示的个数.

引理5[8]若假设1)2)成立,考虑形如式(2)(3)的方法,满足下面3个条件:(i)对任意的k≥1,都有βk≥0;(ii)算法采用Wolfe-power线搜索,满足zoutendijik条件,满足充分下降条件式(12);(iii)满足性质

定理1若假设1)2)成立,考虑形如式(2)(3)的方法,充分下降条件式(12)成立,αk满足式(5)(6),βk取.即new算法具有全局收敛性.

[1]HESTENESM R,STIEFEL E L.Method of Conjugate Gradient for Solving Linear Systems[J].Res Natl Bur Stand,1952(49): 409-436

[2]FLETCHER R,REEVESC.Function Minimization by Conjugate Gradients[J].Comput,1964(7):149-154

[3]POLAK B,RIBIEREG.Note Surla Convergence Des Meethodes de Directions Conjugees[J].Rev Fr Inf Rech Oper,1964,3(1): 35-43

[4]DAIY H,YUAN Y X.A Nonlinear Conjugate GradientMethod with a Strong Global Convergence Property[J].SIAM Optim,1999 (10):177-182

[5]黎勇.一类修正PRP共轭梯度法的全局收敛性及其数值试验结果[J].西南大学学报:自然科学版,2011,33(11):23-28

[6]JIANG X Z,JIAN J B.Two Modified Nonlinear Conjugate Gradient Methods with Disturbance Factors for Unconstrained Optimization[J].Nonlinear Dynamics,2014,77(1-2):387-394

[7]POWELLM JD.NonconVex Minimization Calculations and the Conjugate Method[J].Lecture Notes in Mathematics,1984,10 (66):122-141

[8]GLIBERT JC,NOCEDAL J.Global Convergence Properties of Conjugate GradientMethod for Optimization[J].SIAM Optim,1992 (2):21-42

Global Convergence Property of a Modified PRP Conjugate Gradient Method with Disturbance Factor

CHEN Hong-m in
(School of Mathematical Sciences,Chongqing Normal University,Chongqing 401331,China)

The nonlinear conjugate gradientmethod is a very effective iterativemethod for solving large-scale optimal problems.In this paper,amodified PRP conjugate gradientmethod with disturbance factor is proposed and non-negative property of the formula is proved.Under suitable conditions,the global convergence of the algorithm with theWolfe line search is discussed.

conjugate gradient method;strong Wolfe condition;Wolfe condition;disturbance factor; global convergence

O224

A

1672-058X(2015)09-0001-04

10.16055/j.issn.1672-058X.2015.0009.001

2014-12-11;

2015-02-24.

国家自然科学基金(10771003).

陈洪敏(1988-),女,安徽阜阳人,硕士研究生,从事最优化理论与算法研究.

猜你喜欢
共轭收敛性全局
Cahn-Hilliard-Brinkman系统的全局吸引子
量子Navier-Stokes方程弱解的全局存在性
一个带重启步的改进PRP型谱共轭梯度法
一个改进的WYL型三项共轭梯度法
强Wolfe线搜索下的修正PRP和HS共轭梯度法
Lp-混合阵列的Lr收敛性
巧用共轭妙解题
WOD随机变量序列的完全收敛性和矩完全收敛性
落子山东,意在全局
END随机变量序列Sung型加权和的矩完全收敛性