王安平 (長(zhǎng)江大學(xué)工程技術(shù)學(xué)院,湖北荊州 434020)

馬爍 (荊州理工職業(yè)學(xué)院基礎(chǔ)課部,湖北荊州 434000)

一類(lèi)求解無(wú)約束優(yōu)化問(wèn)題的三項(xiàng)共軛梯度法

王安平 (長(zhǎng)江大學(xué)工程技術(shù)學(xué)院,湖北荊州 434020)

馬爍 (荊州理工職業(yè)學(xué)院基礎(chǔ)課部,湖北荊州 434000)

基于PRP方法和HS方法在算法參數(shù)結(jié)構(gòu),算法性質(zhì)和數(shù)值表現(xiàn)方面的共性、構(gòu)造了一種求解無(wú)約束優(yōu)化問(wèn)題的三項(xiàng)共軛梯度法。該算法所確定的搜索方向不依賴于線搜索條件,恒為充分下降方向,并在Wolfe線搜索的條件下證明了該算法全局收斂性。最后選用部分測(cè)試函數(shù)進(jìn)行了數(shù)值試驗(yàn),試驗(yàn)結(jié)果表明,該算法不僅能保證全局收斂性,而且還具有較快的收斂速度。

無(wú)約束優(yōu)化;三項(xiàng)共軛梯度法;Wolfe線搜索;全局收斂性

通常,FR、CD和DY方法有較強(qiáng)的收斂性,而HS、PRP和LS方法有較好的數(shù)值表現(xiàn)。最近,一些不依賴于線搜索可自行產(chǎn)生充分下降方向,且對(duì)于非凸問(wèn)題收斂的方法[2-13]被提出,即:

若在精確搜索下,式(5)與式(6)分別退化為PRP算法和HS算法,且都滿足式(4)。下面,筆者基于PRP方法和HS方法在算法參數(shù)結(jié)構(gòu)、算法性質(zhì)和數(shù)值表現(xiàn)方面的共性,構(gòu)造一類(lèi)新的三項(xiàng)共軛梯度法。

1 三項(xiàng)共軛梯度法的構(gòu)造

筆者構(gòu)造的一類(lèi)新的三項(xiàng)共軛梯度法如下:

容易看出,筆者構(gòu)造的方法在每步迭代中都產(chǎn)生充分下降方向,有成立,即自行滿足式(3)。

2 算法描述

步長(zhǎng)策略為Wolfe線搜索,即選取αk＞0滿足:

其中,δ和σ是常數(shù),滿足0＜δ＜σ＜1。

算法步驟如下:

步1 給定初始點(diǎn)x1∈Rn及收斂精度ε＞0,d1=-g1,令k=1;

步2 若‖gk‖≤ε,則停止迭代;否則由式(7)求得dk;

步3 按照Wolfe線搜索式(8)和式(9)來(lái)計(jì)算步長(zhǎng)αk;

步4 計(jì)算xx+1=xk+αkdk,置k=k+1,轉(zhuǎn)步2。

3 算法全局收斂性分析

為了證明算法的收斂性,筆者作如下假設(shè)H:

(i)f(x)在水平集L1={x∈Rn|f(x)≤f(x1)}上有界,其中x1為初始點(diǎn);

(ii)f(x)在水平集L1的一個(gè)鄰域U內(nèi)連續(xù)可微的,其梯度g(x)是Lipschitz連續(xù)的,即存在常數(shù)L＞0,使得:

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

選用文獻(xiàn)[14-15]中的部分測(cè)試函數(shù)檢驗(yàn)筆者提出的算法,并將結(jié)果與文獻(xiàn)[4]的結(jié)果比較。所有測(cè)試均采用Wolfe線搜索,均不采用重新開(kāi)始策略。測(cè)試環(huán)境為Matlab2011,運(yùn)行環(huán)境為內(nèi)存4.00GB, CPU為2.60GHz的個(gè)人計(jì)算機(jī)上運(yùn)行。參數(shù)設(shè)置如下:δ=0.001,σ=0.1,μ=0.5,終止條件為‖gk‖≤10-4或It-limit＞9999,計(jì)算得到的數(shù)值結(jié)果如表1所示。

表1 數(shù)值測(cè)試結(jié)果及其比較

從表1可以看出,筆者提出的算法成功的對(duì)15個(gè)測(cè)試函數(shù)進(jìn)行了求解,而MPRP方法有2個(gè)函數(shù)測(cè)試失敗。對(duì)于2種算法都能成功求解的測(cè)試函數(shù),在迭代次數(shù)、函數(shù)值計(jì)算次數(shù)、梯度值計(jì)算次數(shù)方面,筆者提出的算法比MPRP方法要好很多,因此,該算法是有效的。但為了能得到更好的數(shù)值效果,還需要進(jìn)一步研究算法中參數(shù)的選取原則和改進(jìn)搜索條件。

[1]戴彧虹,袁亞湘.非線性共軛梯度法[M].上海:上?？茖W(xué)技術(shù)出版社,2000.

[2]Hager W W,Zhang H C.A new conjugate gradient method with guaranteed descent and an efficient line search[J].SIAM Journal on Optimization,2005,16(1):170-192.

[3]Zhang L,Zhou W J,Li D H.Global convergence of a modified Fletcher-Reeves conjugate gradient method with Armijo-type line search[J]. Numerische Mathematik,2006,104(4):561-572.

[4]Zhang L,Zhou W J,Li D H.A descent modified Polak-Ribiμere-Polyak conjugate gradient method and its global convergence[J]. IMA Journal of Numerical Analysis,2006,26(4):629-640.

[5]Zhang L.New versions of the Hestenes-Stiefel nonlinear conjugate gradient method based on the secant condition for optimization[J]. Computational and Applied Mathematics,2009,28(1):111-133.

[6]An X M,Li D H,Xiao Y H.Sufficient descent directions in unconstrained optimization[J].Computational Optimization and Application, 2011,48(3):515-532.

[7]Narushima Y,Yabe H,Ford J A.A three-term conjugate gradient method with sufficient descent property for unconstrained optimization[J]. SIAM Journal on Optimization,2011,21(1):212-230.

[8]Zheng X Y,Liu H W,Lu A G.Sufficient descent conjugate gradient methods for large-scale optimization problems[J].International Journal of Computer Mathematics,2011,88(16):3436-3447.

[9]Lu A G,Liu H W,Zheng X Y,et al.A variant spectral-type FR conjugate gradient method and its global convergence[J].Applied Mathematics and Computation,2011,217(12):5547-5552.

[10]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(1):296-320.

[11]王安平,馬爍.一種改進(jìn)的DY共軛梯度法及其全局收斂性[J].長(zhǎng)江大學(xué)學(xué)報(bào)(自科版),2013,10(19):3-5.

[12]李向榮.一個(gè)三項(xiàng)LS共軛梯度方法[J].廣西科學(xué),2013,20(4):348-351.

[13]董曉亮,高岳林,何郁波.一類(lèi)Armijo搜索下的混合HS-PRP共軛梯度法[J].工程數(shù)學(xué)學(xué)報(bào),2013,30(3):370-376.

[14]More J J,Garbow B S,Hillstrome K E.Testing unconstrained optimization software[J].ACM Trans Mathsofeware,1981,7: 17-41.

[15]Andrei N.An unconstrained Optimization test functions Collection[J].Advanced Modeling and Optimization,2008,10(1):147-161.

[編輯] 洪云飛

O224

A

1673-1409(2014)22-0001-03

2014-04-10

湖北省教育科學(xué)“十二五”規(guī)劃課題(2012B310);長(zhǎng)江大學(xué)工程技術(shù)學(xué)院基金項(xiàng)目(13J0802)。

王安平(1 9 8 0-),男,碩士,講師,現(xiàn)主要從事最優(yōu)化理論與算法方面的教學(xué)與研究工作。