一類混合的DL-WYL共軛梯度法

李 月

(重慶師范大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，重慶 401331)

0 引 言

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

minf(x),x∈Rn

(1)

其中，f:Rn→R是連續(xù)可微的。

共軛梯度法在求解問題式(1)中起著重要的作用，它的一般迭代格式如下:

xk+1=xk+αkdk

(2)

(3)

其中g(shù)k=▽f(xk),βk是共軛參數(shù),αk是步長,本文采用強(qiáng)Wolfe條件式(4)(5)計(jì)算αk:

(4)

(5)

其中0<δ<σ<1,dk表示搜索方向。

βk的不同代表不同的方法，經(jīng)典的共軛梯度法為HS[1]，PRP[2]，DY[3]方法，其βk分別為

則有：

其中常數(shù)t>0，sk-1=xk-xk-1。

2012年,Dai[6]提出了一類修正的WYL共軛梯度法,其共軛參數(shù)βk為

其中μ>2。

其中μ>2。

1 一類修正的LHSDL共軛梯度法

其中t>0，更多類似方法請參見文獻(xiàn)[10-12]。

其中μ>2。

(6)

2 LHSDL算法

第一步計(jì)算步長αk>0,使其滿足式(4)和式(5)。

第四步置k=k+1,轉(zhuǎn)第一步。

3 收斂性

首先做如下兩個(gè)基本假設(shè):

假設(shè)A水平集L={x∈Rn:f(x)≤f(x0)}有界，其中x0為算法的初始點(diǎn)。即存在一個(gè)常數(shù)B>0，使得

(7)

假設(shè)B目標(biāo)函數(shù)f(x)在L的N鄰域內(nèi)連續(xù)可微，且梯度是Lipschitz連續(xù)的，即?x,y∈N，存在

(8)

(9)

下面證明由LHSDL方法產(chǎn)生的搜索方向dk是充分下降的，即

引理1 如下不等式(10)成立

(10)

(11)

證明首先

由Cauchy-Schwarz不等式可得:

綜上可知,式(10)成立，式(11)的詳細(xì)證明請參見文獻(xiàn)[7]。

(12)

證明當(dāng)k=0時(shí)，d0=-g0，則

由強(qiáng)Wolfe條件式(5)可得

意味著

因此

(13)

引理3 假設(shè)A，B成立，考慮形如式(2)(3)和式(6)的LHSDL方法,αk由強(qiáng)Wolfe條件計(jì)算所得，則LHSDL方法具有性質(zhì)1。

證明由式(5)可得，

對于非線性共軛梯度法,Dai等[15]提出了以下一般性結(jié)論。

引理4 假設(shè)A，B成立，考慮形如式(2)(3)的共軛梯度法，其中dk是一個(gè)下降方向,αk由強(qiáng)Wolfe條件計(jì)算所得。若

(14)

則有

則dk≠0且

證明假設(shè)dk≠0，否則充分下降性條件式(12)不成立,故uk的定義是有意義的。此外,由引理4和式(13),有

其中

特別地,定義

(15)

uk=ωk+δkuk-1

(16)

由δk≥0和式(16)，則

根據(jù)強(qiáng)Wolfe條件式(5)可得

(17)

因此

再由vk的定義，式(7)，式(9)和式(17)可得

因此

證畢。

設(shè)N*為正整數(shù)集合,由λ>0以及正整數(shù)Δ，記

具體的證明過程可參考文獻(xiàn)[4]和[14],因此這里省略證明過程。

(18)

(19)

對于這樣的Δ和k0，引理5給出的指標(biāo)k≥k0，使得

(20)

對任意指標(biāo)i∈[k,k+Δ-1]，由Cauchy-Schwarz不等式和式(19)可得：

由式(19)和式(20),其中l(wèi)=k+Δ-1，可得

4 數(shù)值實(shí)驗(yàn)

Dai和Kou[16]在2013年提出一個(gè)共軛參數(shù):

以及截?cái)嘈问?

將LHSDL方法分別與DK+方法和MNVHS方法進(jìn)行數(shù)值結(jié)果比較。在強(qiáng)Wolfe線搜索條件下選取文獻(xiàn)[17]中的87個(gè)測試問題進(jìn)行驗(yàn)證。參數(shù)δ=0.01，σ=0.1,算法的測試環(huán)境為Matlab2012a，聯(lián)想Windows10操作系統(tǒng)，Intel(R)Core(TM)i5-8250U CPU @ 1.60 GHz 1.80 GHz，RAM 4.00 GB內(nèi)存。

數(shù)值結(jié)果見表1，其中Time表示所耗費(fèi)的CPU時(shí)間(單位:s)，NI表示方法的迭代次數(shù)，NF表示方法的函數(shù)計(jì)算次數(shù)，NG表示方法的梯度計(jì)算次數(shù)。

表1 數(shù)值結(jié)果

將DK+方法作為比較標(biāo)準(zhǔn)，數(shù)值越小計(jì)算效果越好。因此由表1可以看出，LHSDL方法略優(yōu)于其他方法。

通過繪制性能曲線圖[18]比較每一種方法的數(shù)值效果。圖1—圖4分別對應(yīng)的是在強(qiáng)Wolfe線搜索下DK+，MNVHS和LHSDL方法的計(jì)算時(shí)間、函數(shù)計(jì)算次數(shù)、梯度計(jì)算次數(shù)以及迭代次數(shù)的性能曲線。曲線越在上方越靠近1，則計(jì)算效率越好。因此，從圖1—圖4中可以看出LHSDL方法優(yōu)于MNVHS方法和DK+方法。

圖1 計(jì)算時(shí)間性能曲線

圖3 函數(shù)計(jì)算次數(shù)性能曲線

圖4 梯度計(jì)算次數(shù)性能曲線

5 結(jié)束語

參考文獻(xiàn)(References):

[1] HESTENES M R，STIEFEL E.Methods of Conjugate Gradients for Solving Linear Systems[J].Journal of Research of the National Bureau of Standards，1952，49(6):99—147

[2] POLYAK B T.The Conjugate Gradient Method in Extremal Problems[J].USSR Computational Mathematics and Mathematical Physics，1969，9(4):94—112

[3] DAI Y H，YUAN Y.A Nonlinear Conjugate Gradient Method with a Strong Global Convergence Property[J].SIAM Journal on Optimization，1999，10(1):177—182

[4] DAI Y H，LIAO L Z.New Conjugacy Conditions and Related Nonlinear Conjugate Gradient Methods[J].Applied Mathematics and Optimization，2001，43(1):87—101

[5] WEI Z X，YAO S W，LIU L Y.The Convergence Properties of Some New Conjugate Gradient Methods[J].Applied Mathematics and Computation，2006，183(2):1341—1350

[6] DAI Z F，WEN F H.Another Improved Wei-Yao-Liu Nonlinear Conjugate Gradient Method with Sufficient Descent Property[J].Applied Mathematics and Computation，2012，218(14):7421—7430

[7] DU X W，ZHANG P，MA W Y.Some Modified Conjugate Gradient Methods for Unconstrained Optimization[J].Journal of Computational and Applied Mathematics，2016，305(1):92—114

[8] 陳恩.WYL和HZ共軛梯度算法的改進(jìn)和推廣[D].重慶:重慶師范大學(xué),2018

CHEN E.Improvement and Generalization of WYL and HZ Conjugate Gradient Algorithms[D].Chongqing:Chongqing Normal University，2018(in Chinese)

[9] 馬文亞.基于韋增欣等的共軛梯度參數(shù)的修正共軛梯度法[D].重慶:重慶師范大學(xué)，2015

MA W Y.Conjugate Gradient Algorithms Based on the Conjugate Gradient Parameter of Wei et al[D].Chongqing:Chongqing Normal University，2015(in Chinese)

[10] YAO S W，QIN B.A Hybrid of DL and WYL Nonlinear Conjugate Gradient Methods[J].Abstract and Applied Analysis，2014(2014):1—9

[11] YAO S W，LU X W，WEI Z X.A Conjugate Gradient Method with Global Convergence for Large-Scale Unconstrained Optimization Problems[J].Journal of Applied Mathematics，2013(9):1—9

[12] CHENG Y L，MOU Q，PAN X B，et al.A Sufficient Descent Conjugate Gradient Method and Its Global Convergence[J].Optimization Methods and Software，2016，31(3):577—590

[13] 謝麗.一類修正的DL共軛梯度法[J].周口師范學(xué)院學(xué)報(bào),2019,36(5):31—35

XIE L.A Modified DL Conjugate Gradient Method[J].Journal of Zhoukou Normal University,2019,36(5):31—35(in Chinese)

[14] GILBERT J C，NOCEDAL J.Global Convergence Properties of Conjugate Gradient Methods for Optimization[J].SIAM Journal on Optimization，1992，2(1):21—42

[15] DAI Y H，HAN J Y，LIU G H，et al.Convergence Properties of Nonlinear Conjugate Gradient Methods[J].SIAM Journal on Optimization，2000，10(2):345—358

[16] DAI Y H,KOU C X.A Nonlinear Conjugate Gradient Algorithm with an Optimal Property and an Improved Wolf Line Search[J].SIAM Journal on Optimization.2013，23(1):296—320

[17] GOULD N I M，ORBAN D，TOINT P L.CUTEr and SifDec:A Constained and Unconstrained and Testing Environment Revisited[J].ACM Transactions on Mathematical Software，2003，29(4):373—394

[18] DOLAN E D，MORé J J.Benchmarking Optimization Software with Performance Profiles[J].Mathematical Programming，2002，91(2):201—213