一個充分下降LS型共軛梯度算法的全局收斂性

林 穗 華

(廣西民族師范學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)系, 廣西 崇左 532200)

?

林 穗 華*

(廣西民族師范學(xué)院 數(shù)學(xué)與計算機(jī)科學(xué)系, 廣西 崇左 532200)

共軛梯度法是求解大型無約束非線性優(yōu)化問題的一種常用方法,在應(yīng)用中通常以負(fù)梯度方向作為其自動重啟方向. 該文在LS共軛梯度法的基礎(chǔ)上,結(jié)合一種新的自動重啟方向,證明了算法的自動充分下降性和在強(qiáng)Wolfe線搜索下的全局收斂性,給出的數(shù)值試驗結(jié)果表明算法是有效的.

無約束優(yōu)化; 共軛梯度法; 充分下降性; 自動重啟; 全局收斂性

假設(shè)函數(shù)f:Rn→R連續(xù)可微,共軛梯度法是求解min{f(x)|x∈Rn}的一類有效方法,其迭代格式為:

xk+1=xk+αkdk,

(1)

其中,步長αk由某種線搜索確定,搜索方向dk定義如下

(2)

gk為f在xk處的梯度,βk∈R為參數(shù).共軛梯度法具結(jié)構(gòu)簡單和存儲需求少等優(yōu)點(diǎn),自Fletcher和Reeves[1]提出首個非線性共軛梯度法以來,得到深入的研究和廣泛的應(yīng)用. 參數(shù)βk的不同選取決定了不同效果的共軛梯度法[2],著名的PRP、HS和LS共軛梯度法參數(shù)公式如下:

Yuan[6]又更進(jìn)一步修改為:

并推廣到對LS方法的修改

(3)

(4)

也得到了全局收斂的結(jié)果.

(5)

(6)

以下將分析此共軛梯度法的收斂性質(zhì),并通過數(shù)值試驗對比兩種自動重開始機(jī)制的有效性.

1 算法及其下降性

算法1(LS型共軛梯度算法)

Step1： 利用以下強(qiáng)Wolfe線搜索計算步長αk:

(7)

和

(8)

Step2： 令xk+1=xk+αkdk.若‖gk+1‖≤ε,停止;

Step4：k:=k+1,轉(zhuǎn)Step 1.

以下均假設(shè)‖gk‖≠0,否則算法已找到穩(wěn)定點(diǎn)而停止.引理1說明DLS+方法自動滿足充分下降性.

引理1設(shè){gk,dk}為算法1生成的序列,則存在常數(shù)c∈(0,1],對所有的k≥1都有

(9)

假設(shè)k≥1時(9)式成立.以下分兩種情況證明k+1時(9)式也成立.

-c‖gk+1‖2.

(10)

結(jié)合(10)式可得

根據(jù)數(shù)學(xué)歸納法原理,引理1得證.

2 算法的全局收斂性

為了證明算法1的全局收斂性,本文用到共軛梯度法文獻(xiàn)中常用的如下條件.

假設(shè)條件(A): (i)水平集Ω={x∈Rn|f(x)≤f(x1)}有界, 且f(x)在Ω有下界;

(ii)f(x)的梯度g(x)在Ω上Lipschitz連續(xù),即存在常數(shù)L>0,使任意的x,y∈Ω,有

‖g(y)-g(x)‖≤L‖y-x‖.

引理2設(shè)假設(shè)條件(A)成立, {gk,dk}為算法1生成的序列,則

(11)

證明 由(7)和(9)式,知

(12)

由(8)式及假設(shè)條件(A(ii)),可得

從而

(13)

由(7)和(9)式,結(jié)合(13)式可得

(14)

對(14)式兩端求和,由假設(shè)條件(A(i))及(12)式,可知(11)式成立,引理2得證.

引理3設(shè)假設(shè)條件(A)成立,{gk,dk}為算法1生成的序列. 若存在常數(shù)r>0,對任意k≥1,有

‖gk‖≥r,

(15)

則

(16)

證明由(9)及(15)式知,對任意k≥1有dk≠0. 設(shè)

(17)

uk=wk+δkuk-1,

(18)

從而,可得

wk=uk-δkuk-1.

上式結(jié)合‖uk‖=‖uk-1‖=1,可得

從而,可得

‖wk‖=‖uk-δkuk-1‖=‖δkuk-uk-1‖.

上式結(jié)合δk≥0及三角不等式,可得

‖uk-uk-1‖≤(1+δk)‖uk-uk-1‖=

‖(uk-δkuk-1)+(δkuk-uk-1)‖≤

‖uk-δkuk-1‖+‖δkuk-uk-1‖=

2‖wk‖,

(19)

由(17)式,可得

結(jié)合(18)和(19)式,可得

由(9),(11),(15)式,結(jié)合上式,可得

從而,可得(16)式成立.引理3得證.

性質(zhì)1[4]考慮形如(1)和(2)的方法,并假定

(20)

證明 由假設(shè)條件(A)可知, ‖yk-1‖≤L‖xk-xk-1‖=L‖sk-1‖, ‖sk-1‖=‖xk-xk-1‖≤2q.

結(jié)合(5),(8)和(9)式,可得

(21)

由(21)式,可知

設(shè)‖sk-1‖≤λ,則由(20)式,可得

引理4得證.

證明 由(9),(11)和(20)式,可得

從而,可得

‖dk‖→+∞.

(22)

這與(22)矛盾.引理5得證.

引理6設(shè)假設(shè)條件(A)成立,{gk,dk}為算法1生成的序列. 若任意k≥1有(20)式成立,則存在λ>0,使得對任意的Δ∈Z+和指標(biāo)k0,均存在指標(biāo)k≥k0,滿足

(23)

證明 假設(shè)定理不成立,則(20)式對任意的k都滿足.

根據(jù)引理6可知,對任意的Δ,k0∈Z+,存在λ>0和k≥k0滿足(23)式.

(24)

從而,對滿足(23)式的k和任意i∈[k,k+Δ-1],利用Cauchy-Schwarz不等式及(24)式,可得

(25)

3 數(shù)值結(jié)果

[1] FLETCHER R, REEVES C.Function minimization by conjugate gradients[J].Computer Journal, 1964, 7: 149-154.

[2] 戴彧虹, 袁亞湘. 非線性共軛梯度法[M].上海:上海科學(xué)技術(shù)出版社,2001.

[3] POWELL M J D. Nonconvex Minimization Calculations and the Conjugate Gradient Method[M]. Numerical Analysis, Berlin: Springer-Verlag, 1984: 487-500.

[4] GILBERT J C, NOCEDAL J. Global convergence properties of conjugate gradient methods for optimization[J]. SIAM Journal on Optimization, 1992, 2(1): 21-42.

[5] 喻高航, 關(guān)履泰. 具有充分下降的修正PRP算法及其收斂性[J]. 中山大學(xué)學(xué)報(自然科學(xué)版), 2006, 45(4):11-14.

[6] YUAN G L. Modified nonlinear conjugate gradient methods with sufficient descent property of large-scale optimization problems[J]. Optimization Letters, 2009, 3:11-21.

[7] DAI Y H, KOU C X. A nonlinear conjugate gradient algorithm with an optimal property and an improved Wolfe line search[J]. SIAM Journal on Optimization, 2013, 23:296-320.

[8] 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.

[9] WEI Z, YAO S, LIU L. The convergence properties of some new conjugate gradient methods[J]. Applied Mathematics and Computation, 2006, 183:1341-1350.

[10] 吳慶軍. 一個修改的HS共軛梯度算法及其收斂性[J]. 華中師范大學(xué)學(xué)報(自然科學(xué)版), 2014, 48(4):474-477.

[11] 李 敏, 屈愛平. 一種充分下降的PRP共軛梯度法的全局收斂性[J]. 高等學(xué)校計算數(shù)學(xué)學(xué)報, 2013, 35(2):148-158.

The convergence property of a sufficient descent LS-type conjugates gradient method

LIN Suihua

(Department of Mathematics and Computer Science,Guangxi Normal University for Nationalities, Chongzuo, Guangxi 532200)

The conjugate gradient method is a common method for solving large-scale unconstrained nonlinear optimization problems, and in practice, the negative gradient direction is usually used as the automatic restart direction. In this paper, based on the LS conjugate gradient method and a new automatic restart direction, the corresponding algorithm is demonstrated to possess the property of automatically generating sufficient descent and the global convergence of the search in strong Wolfe line. The given numerical results show that the proposed algorithm is efficent.

unconstrained optimization; conjugate gradient method; sufficient descent; adaptive restars; global convergence

2015-05-18.

廣西高校科研項目(ZD2014143);廣西民族師范學(xué)院科研項目(2013RCGG002);廣西重點(diǎn)培育學(xué)科(應(yīng)用數(shù)學(xué))建設(shè)項目(桂教科研[2013]16).

1000-1190(2015)06-0811-05

O242.23

A

*E-mail: linsuihuah@163.com.