一類求解無約束優(yōu)化問題的三項共軛梯度法

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

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

一類求解無約束優(yōu)化問題的三項共軛梯度法

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

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

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

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

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

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

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

筆者構(gòu)造的一類新的三項共軛梯度法如下:

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

2 算法描述

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

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

算法步驟如下:

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

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

步3 按照Wolfe線搜索式(8)和式(9)來計算步長αk;

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

3 算法全局收斂性分析

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

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

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

4 數(shù)值試驗

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

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

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

[1]戴彧虹,袁亞湘.非線性共軛梯度法[M].上海:上海科學(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]王安平,馬爍.一種改進的DY共軛梯度法及其全局收斂性[J].長江大學(xué)學(xué)報(自科版),2013,10(19):3-5.

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

[13]董曉亮,高岳林,何郁波.一類Armijo搜索下的混合HS-PRP共軛梯度法[J].工程數(shù)學(xué)學(xué)報,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);長江大學(xué)工程技術(shù)學(xué)院基金項目(13J0802)。

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