APP下载

一种改进的DY共轭梯度法及其全局收敛性

2013-12-01王安平长江大学工程技术学院基础教学部湖北荆州434020

长江大学学报(自科版) 2013年19期
关键词:共轭收敛性常数

王安平 (长江大学工程技术学院基础教学部,湖北 荆州434020)

马 烁 (荆州理工职业学院基础课部,湖北 荆州434000)

考虑无约束优化问题:

式中,f:Rn→R连续可微。共轭梯度法是求解该问题的一类有效算法。一般的共轭梯度法迭代公式为:

式中,x1为初始点;dk为搜索方向;αk是由某种线性搜索或由特定公式计算出的步长因子;βk为标量;g(x)= ▽f(x),gk= ▽f(xk)。共轭梯度法的关键是选取αk和βk,不同的αk和βk决定了不同的共轭梯度算法。常用选取αk的线搜索是标准Wolfe线搜索,即选取αk>0满足:

式中,δ和σ是满足0<δ<σ<1的常数。而βk的选取公式常用的有:

对应的共轭梯度法依次为FR方法[1]、PRP方法[2]、HS方法[3]、CD方法[4]、LS方法[5]和 DY 方法[6]。

在众多共轭梯度法中,为了保证下降方向,许多学者都做了深入的研究。文献 [7]提出了一种改进的DY共轭梯度法,参数βk的计算公式为:

受文献[7]的启发,笔者在MDY方法的基础上,给出了一个新的参数βk的取法,即:

1 改进的DY算法及其充分下降性

改进的DY算法如下:

步1 给定初始点x1∈Rn,ε>0,d1=-g1,令k=1;

步2 若‖gk‖≤ε,则停止迭代;否则转入步3;

步3 由式(3)求得αk;

步4 计算xx+1=xk+αkdk,若 ‖gk+1‖ ≤ε,则算法停止,否则转步5;

步5 利用式(4)计算βk+1。计算dk+1=-gk+1+βk+1dk,置k=k+1,转步2。

定理1 设迭代方向由:

证明 当k=0时,dT0g0=-‖g0‖2,结论成立。

当k≥0时,dk=-gk+βNMDYkdk-1两边与gk做内积:

2 算法的全局收敛性

下面笔者将在一定的假设条件下证明NMDY算法的全局收敛性。假设条件(A)如下:

(1)水平集L1= {x∈Rn|f(x)≤f(x1)}有界,其中x1为初始点;

(2)在水平集L1的一个邻域U内,f(x)是连续可微的,其梯度g(x)是lipschitz连续的,即存在常数L>0使:

‖g(x)-g(y)‖ ≤L‖x-y‖ ∀x,y∈U引理1 设目标函数f(x)满足假设A,序列{xk}由式(2)产生,其中βk由(4)计算,αk满足式(3),则。此关系式称为Zoutendijk条件。

证明 由定理1及式(3),则有:

则式(6)说明了函数列{fk}有界。再由定理1及式(3)和假设条件(A)中的第2个条件,则有:

再联合式(3)可以得到:

又因为函数列{fk}有界,所以有:

定理2 设目标函数f(x)满足假设条件A,序列{xk}由式(2)产生,其中βk由式(4)计算,αk由式(3)确定。假设存在一个正数α*,满足αk≥α*,则有:

证明 由假设A中的(1),则存在一个常数M>0使得:

由式(8)和αk≥α*,可以得到:

由式(9)及引理1和定理1的结论,可以得到式(7),即定理2得证。

猜你喜欢

共轭收敛性常数
一个带重启步的改进PRP型谱共轭梯度法
一个改进的WYL型三项共轭梯度法
关于Landau常数和Euler-Mascheroni常数的渐近展开式以及Stirling级数的系数
Lp-混合阵列的Lr收敛性
巧用共轭妙解题
一种自适应Dai-Liao共轭梯度法
WOD随机变量序列的完全收敛性和矩完全收敛性
END随机变量序列Sung型加权和的矩完全收敛性
万有引力常数的测量
松弛型二级多分裂法的上松弛收敛性