具有充分下降性的修正類Wei-Yao-Liu共軛梯度法

孫敏

(棗莊學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院，山東棗莊277160)

[摘要]基于最近的一些共軛梯度法的設(shè)計(jì)思想，本文提出了一類修正的Wei-Yao-Liu共軛梯度法.該方法的優(yōu)點(diǎn)是每步迭代都可以產(chǎn)生充分下降方向，并且這個(gè)性質(zhì)不依賴于線性搜索.在一類Armijo線性搜索下，該方法具有全局收斂性.最后的數(shù)值試驗(yàn)表明了新方法的有效性.

[關(guān)鍵詞]Wei-Yao-Liu共軛梯度法;充分下降性;全局收斂性[收稿日期]2015-08-10

[作者簡介]孫敏(1980-)，男，山東泰安人，棗莊學(xué)院數(shù)學(xué)與統(tǒng)計(jì)學(xué)院副教授，碩士，主要從事計(jì)算數(shù)學(xué)、最優(yōu)化理論與算法的研究.

[中圖分類號(hào)]O221.2 [文獻(xiàn)標(biāo)識(shí)碼]A

0引言

本文，我們考慮如下無約束最優(yōu)化問題

minf(x), x∈Rn

(1)

其中f(x):Rn→R1是連續(xù)可微函數(shù). 問題(1)有很多求解有效的方法, 如共軛梯度法、牛頓法、擬牛頓法、最小二乘法等, 其中共軛梯度法由于具有存儲(chǔ)量小, 同時(shí)又可以避免拉鋸現(xiàn)象的優(yōu)點(diǎn), 被人們廣泛的研究和使用. 共軛梯度法采用下面的迭代格式

xk+1=xk+αkdk

(2)

其中xk是當(dāng)前迭代點(diǎn),αk是步長,dk是f(x)在點(diǎn)xk的下降方向, 其迭代格式為

(3)

其中g(shù)k=▽f(xk),βk被稱為共軛梯度參數(shù).有很多著名的βk公式[1],如

其中yk-1=gk-gk-1. 大量的研究表明,FR,CD和DY方法有較好的全局收斂性，但是數(shù)值效果不如另外三種；而PRP,HS和LS方法雖然具有較好的數(shù)值效果，但全局收斂性較差. 因此很多學(xué)者對(duì)PRP,HS和LS方法進(jìn)行了研究，提出了許多修正的PRP,HS和LS方法. 本文我們考慮Wei等[2]在2006年提出的修正的PRP共軛梯度法和Wan等[3]在2011年提出的PRP型譜共軛梯度法. 先看Wei等提出的方法,其共軛梯度參數(shù)的公式為:

(4)

后來,Dai等[4]對(duì)Wei-Yao-Liu共軛梯度法進(jìn)行了深入研究, 提出了新的共軛梯度參數(shù)公式:

(5)

其中μ>1是一個(gè)常數(shù). 顯然當(dāng)采用精確線性搜索時(shí), (5)退化成(4).Wan等[3]提出了如下PRP型譜共軛梯度法:

(6)

其中c>0是一個(gè)常數(shù). 最近, 陳等[5]對(duì)將Wan等得思想應(yīng)用到一類修正的Wei-Yao-Liu共軛梯度法[6],得到了一種新的PRP型譜共軛梯度法, 該算法不依賴線性搜索就滿足充分下降性, 同時(shí)在標(biāo)準(zhǔn)的Armijo線性搜索下具有全局收斂性, 初步的數(shù)值試驗(yàn)表明了方法的有效性.

受陳等[5]所提共軛梯度法的啟發(fā), 本文對(duì)Dai等[4]提出的方法進(jìn)行修正, 使其也具有不依賴于線性搜索的充分下降性, 并且在Armijo類線性搜索的條件下具有全局收斂性. 本文的結(jié)構(gòu)如下, 第2節(jié)提出了新的具有充分下降性的修正類Wei-Yao-Liu共軛梯度法,并且證明了其具有充分下降行;第3節(jié)證明了新方法在一類Armijo線性搜索下具有全局收斂性; 第4節(jié)給出了初步的數(shù)值試驗(yàn)結(jié)果.

2修正類Wei-Yao-Liu共軛梯度法

修正類Wei-Yao-Liu共軛梯度法

步0: 取初始值x0∈Rn, 參數(shù)μ>0,ρ∈(0,1),γ>0,令k:=0;

(7)

步3: 令αk是{1,ρ,ρ2,…}中滿足下式的最大者α

(8)

令xk+1=xk+αkdk,k=k+1, 轉(zhuǎn)步1.

注1顯然, 當(dāng)采用精確線性搜索時(shí), 上面的修正類Wei-Yao-Liu共軛梯度法退化成文獻(xiàn)[7]中的改進(jìn)的Wei-Yao-Liu共軛梯度法.

注2與文獻(xiàn)[4]中的方法相比, 修正類Wei-Yao-Liu共軛梯度法中的μ的取值范圍擴(kuò)大了.

由歸納假設(shè)知命題成立.

證略.

3算法的收斂性

收斂性的證明需要下面的假設(shè):

(H1) 水平集L0={x|f(x)≤f(x0)}是有界的.

(H2) g(x)在包含L0的開凸集N上Lipschitz連續(xù), 即存在常數(shù)L>0, 使得

(9)

首先由(8)和(H1)可得：

于是

(10)

同時(shí)由(H1)(H2)可得，存在γ1>0，是得

(11)

(12)

證由(5)-(7),(11), 可得

由(10), 可得, 存在常數(shù)r∈(0,1)與整數(shù)k0, 使得對(duì)于任意的k≥k0, 都有

于是, 對(duì)于任意的k>k0, 有

下面我們證明新算法的全局收斂性.

定理1在(H1)(H2)下, 假設(shè)算法產(chǎn)生無窮點(diǎn)列{xk}, 則

(13)

(14)

于是由中值定理, 存在hk∈(0,1), 有

f(xk+αkdk/ρ)-f(xk)=ρ-1αkg(xk+αkhkdk/ρ)Tdk

(15)

‖gk‖2≤ρ-1(L+γ)αk‖dk‖2.

4數(shù)值試驗(yàn)

本節(jié), 我們從文獻(xiàn)[6]中選取一些測試函數(shù)來檢驗(yàn)新方法(記為算法1)的數(shù)值效果, 測試問題的初始值也由文獻(xiàn)[6]給出. 考慮到PRP方法是目前數(shù)值表現(xiàn)最好的共軛梯度法之一, 同時(shí)Wan等[3]提出的PRP型譜共軛梯度法(記為SPRP)是對(duì)PRP方法的改進(jìn), 因此在下文中我們將新方法與SPRP方法作比較. 兩種算法的參數(shù)設(shè)置如下:

表1　算法1和SPRP的數(shù)值結(jié)果

500018/493.1550e-006算法143/1306.8811e-006SPRP

從表1的試驗(yàn)結(jié)果可以看出, 對(duì)于所選的測試問題, 在相同的精度要求下, 兩種方法都有較好的數(shù)值表現(xiàn). 特別的, 就迭代次數(shù)與函數(shù)計(jì)算次數(shù)兩項(xiàng)評(píng)價(jià)指標(biāo)分析, 算法1對(duì)文中所選的大部分測試問題, 都具有優(yōu)于SPRP方法的數(shù)值效果. 另外, 實(shí)驗(yàn)表明, 算法1中的參數(shù)μ對(duì)實(shí)驗(yàn)的結(jié)果有較大影響, 因此, 為了得到更好的試驗(yàn)效果, 我們需要對(duì)算法1中的參數(shù)μ的選取值作進(jìn)一步的研究與探索(如自適應(yīng)).

參考文獻(xiàn)

[1]Shi Zhen-Jun, Shen Jie. Convergence of Liu-Story conjugate gradient method[J]. European Journal of Operational Research, 2007,182: 552-560.

[2]Shi Zhen-Jun. A new memory gradient method under exact line search[J]. Asia-Pacific J.Oper. Res., 2003, 20(2): 275-284.

[3]Shi Zhen-Jun. A new Super-memory gradient methodfor unconstrained optimization[J]. Advance in Mathcmatics, 2006, 35(3): 265-274.

[4]Zhang Li, Zhou Wei-Jun, Li Dong-Hui. A descent modified Polak-Ribiere-Polyak conjugate gradient method and its global convergence[J].IMA Journal of Numerical Analysis,2006,26: 629-640.

[5]Cheng Wan-You. A modified and descent nonlinear conjugate method[EB/OL].[2007-12-03]. http://www.paper.edu.cn/paper.php?serial_number=200612-316.

[責(zé)任編輯：房永磊]

The Improved Wei-Yao-Liu Conjugate Gradient Method With Sufficient Descent Property

SUN Min

(School of Mathematics and Statistics, Zaozhuang University, Zaozhuang 277160, China)

Abstract:In this paper, based on design ideas of some new conjugate gradient methods, an improved Wei-Yao-Liu conjugate gradient method is proposed. The most attractive properties of the method is that the generated iterative direction is always a sufficiently descent direction without utilizing the line search. Under an Armijo-type line search, the new method has global convergence. The preliminary numerical results show that the method is effective.

Key words: Wei-Yao-Liu conjugate gradient method; sufficiently descent; global convergence