一個共軛梯度優(yōu)化方法及其在工程中的應(yīng)用*

黃玲花

(廣西財經(jīng)學(xué)院 信息與統(tǒng)計學(xué)院，廣西 南寧　530003)

?

一個共軛梯度優(yōu)化方法及其在工程中的應(yīng)用*

黃玲花

(廣西財經(jīng)學(xué)院 信息與統(tǒng)計學(xué)院，廣西 南寧530003)

給出一個三項共軛梯度方法，該方法具有如下特點：1)搜索方向在不需要任何線搜索的條件下具有充分下降性；2)搜索方向具有自動屬于一個信賴域的特點；3)新方法不但擁有梯度值信息還擁有函數(shù)值信息；4)方法對一般函數(shù)擁有全局收斂性.數(shù)值檢驗結(jié)果表明新方法更具競爭性.

共軛梯度；充分下降；收斂性

0　引言

(1)

其中f(x):Rn→R是連續(xù)可微函數(shù).無約束最優(yōu)化問題來源于眾多實際問題，具有廣泛的應(yīng)用背景，此問題的求解方法有很多種：牛頓法、擬牛頓法、信賴域方法和共軛梯度法等等，這些優(yōu)化方法能為求解其他優(yōu)化問題提供強有力的理論支持.共軛梯度方法具有結(jié)構(gòu)簡單、計算機存儲量小和高效率的特點，因而被廣泛應(yīng)用.該方法的迭代公式是：xk+1=xk+αkdk,k=0, 1, 2,…

其中xk稱為第k次迭代點，αk>0是由線搜索產(chǎn)生的步長，dk是搜索方向，定義形式為

(2)

其中g(shù)k=▽f(xk)和gk+1=▽f(xk+1)是函數(shù)f(x)在xk和xk+1的梯度值，‖·‖表示歐式向量范數(shù).該方法數(shù)值表現(xiàn)優(yōu)越特別適合大規(guī)模優(yōu)化問題，也常常被人們用于實際的問題中，是研究最為熱門的共軛梯度公式之一.但是PRP方法的收斂性不理想，對于一般函數(shù)在弱Wolfe-Powell線搜索下的全局收斂性一直沒有得到證明，是一個開放的問題.鑒于此，許多學(xué)者希望發(fā)現(xiàn)數(shù)值表現(xiàn)能與PRP相媲美同時收斂性質(zhì)又比它優(yōu)越的方法，許多成果可參見文獻[8-15]等.研究發(fā)現(xiàn)，該方法在非精確線搜索下對一般函數(shù)收斂性不好的一個主要原因在于它不能保證充分下降性，充分下降性是指對所有k，式(3)的不等式成立

(3)

研究發(fā)現(xiàn)該性質(zhì)在收斂性的理論分析中起著重要作用.基于PRP方法，為保證(3)關(guān)系式的成立，Zhang[16]等給出了一個三項共軛梯度方法，方向為

(4)

(5)

(6)

其中δ∈(0,1/2),σ∈(δ,1)，受(6)的啟發(fā)，Yuan[17]等給出了下面的共軛梯度方向

(7)

(8)

容易看出新公式不但擁有梯度值還擁有函數(shù)值信息.

1　算法

算法1(修改的共軛梯度算法)

步驟0：給定x0∈Rn，c∈(0,1),δ∈(0,1/2),σ∈(δ,1)和終止參數(shù)ε>0.令d0=-g0=-▽f(x0)，

置k：= 0.

步驟1：若‖gk‖≤ε，停止.

步驟2：尋找滿足(5)和(6)的步長αk.

步驟3：令xk+1=xk+αkdk,如果‖gk+1‖≤ε，停止.

步驟4：利用公式(8)計算搜索方向.

步驟5：置k：=k+1，轉(zhuǎn)步驟2.

2　充分下降性、信賴域性質(zhì)和全局收斂性分析

下面證明修改的三項公式方向具有充分下降性和信賴域的性質(zhì).

引理1 對k≥0，修改的三項公式的搜索方向滿足

(9)

(10)

(9)成立.對于關(guān)系式(10)，根據(jù)(8)式，當(dāng)k=0，(10)顯然成立，當(dāng)k≥1時，我們有

因此(10)成立.證畢.

假設(shè)條件(A)：i) 水平集Ω={x∈Rn:f(x)≤f(x0)}有界.

ii)f在Ω上有下界且連續(xù)可微，它的梯度g滿足Lipschitz條件，即存在常數(shù)L>0滿足

‖g(x)-g(y)‖≤L‖x-y‖,?x,y∈Ω

(11)

證明：根據(jù)WWP線搜索的關(guān)系式(6)和Lipschitz條件(11)，得到

(12)

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

為了驗證算法的有效性，給出數(shù)值檢驗結(jié)果，檢驗函數(shù)是在工程領(lǐng)域經(jīng)常用到的Benchmark問題，這些問題列舉如下.

1)Spherefunction.

2)Schwefel'sfunction.

3)Rastriginfunction.

4)Schwefelfunction.

x*=(-420.9678,-420.9678,…，-420.9678),fSch(x*)=0

5)Griewankfunction.

上述的Benchmark問題可從下述的網(wǎng)站中找到：http://www.cs.cmu.edu/afs/cs/project/jair/pub/volume24/ortizboyer05a-html/node6.html

實際計算中，參數(shù)選取如下：c=0.5,ε=10-5,δ=0.1,σ=0.9,停止準(zhǔn)則采用Himmeblau準(zhǔn)則：

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

從表1結(jié)果可以看出，對給定的終止條件，算法1能大部分成功求解，這說明了方法的有效性.但是對一些問題，數(shù)值表現(xiàn)不是很理想，這說明方法具有待改進的地方.特別是初始點的選擇方面，有待進一步的研究.

上述Benchmark問題是工程中的常用問題，我們利用這些問題進行驗證方法的有效性，目的是為了證實算法在實際領(lǐng)域中具有一定的應(yīng)用背景.當(dāng)然還有其他更多的應(yīng)用問題有待進一步研究和探討.

4　結(jié)論

本文給出一個修改的三項PRP方法，證明了方法對一般函數(shù)在WWP線搜索下具有全局收斂性，并給出了數(shù)值檢驗結(jié)果，相對于通常的PRP方法和三項PRP方法可得出如下結(jié)論：

1)與通常的PRP方法相比較，新方法不但具有充分下降性，還具有信賴域的特點，同時能保證對一般函數(shù)在WWP線搜索下的全局收斂性，數(shù)值結(jié)果也具有競爭性；

2)與通常的三項PRP方法相比較，新方法具有了信賴域的特點且對一般函數(shù)在WWP線搜索下的全局收斂性，同時擁有梯度值信息和函數(shù)值信息；

3)與文章Yuan[17]相比較，將方法推廣到一般的光滑優(yōu)化方法中，且兩種方法所具有的函數(shù)值信息不同.

[1] Y. Dai , Y. Yuan. A nonlinear conjugate gradient with a strong global convergence properties [J]. SIAM J. Optim, 2000 (10):177-182.

[2] R. Fletcher. Practical Method of Optimization, Vol I: Unconstrained Optimization [M]. 2nd edition, Wiley, New York, 1997.

[3] R. Fletcher , C. Reeves. Function minimization bu conjugate gradients[J].Compute. J, 1964 (7): 149-154.

[4] M. R. Hestenes , E. Stiefel. Method of conjugate gradient for solving linear equations, J, Res [J]. Nat. Bur. Stand, 1952 (49):409-436.

[5] Y. Liu , C. Storey. Effcient generalized conjugate gradient algorithms, part 1: theory[J].Journal of optimization theory and Application ,1992 (69).

[6] E. Polak , G. Ribiere.Note sur la xonvergence de directions conjugees[J]. Rev. Francaise informat Recherche Operatinelle , 3e Annee, 1969 (16).

[7] B. T. Polyak.The conjugate gradient method in extreme problems [J].USSR Comp Math Math Phys,1969 (9): 94-112.

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

[9] W. W. Hager , H. Zhang.Algorithm 851: CGDESCENT, A conjugate gradient method with guaranteed descent[J]. ACM Transactions on Mathematical Software, 2006 (32): 113-137.

[10] G. Li, C. Tang, Z. Wei.New conjugacy condition and related new conjugate gradient methods for unconstrained optimization problems[J]. Journal of Computational and Applied Mathematics, 2007(202):532-539.

[11] Z. Wei, G. Li, L. Qi. New nonlinear conjugate gradient formulas for large-scale unconstrained optimization problems[J].Applied Mathematics and Computation, 2006 (179):407-430.

[12] Z. Wei, G. Li, L. Qi.Global convergence of the PRP conjugate gradient methods with inexact line search for nonconvex unconstrained optimization problems[J].Mathematics of Computation, 2008 (77): 2173-2193.

[13] Z. Wei, S. Yao, L. Liu. The convergence properties of some new conjugate gradient methods[J]. Applied Mathematics and Computation, 2006 (183):1341-1350.

[14] G. L. Yuan. Modified nonlinear conjugate gradient methods with suffcient descent property for large-scale optimization problems[J]. Optimization Letters, 2009 (3): 11-21.

[15] G. L. Yuan , X. W. Lu. A modified PRP conjugate gradient method[J]. Annals of Operations Research, 2009 (166): 73-90.

[16] L. Zhang, W. Zhou, D. Li.A descent modified Polak-Ribi`ere-Polyak conjugate method and its global convergence[J]. IMA Journal on Numerical Analysis, 2006 (26) :629-649.

[17] G. Yuan, Z. Wei, G. Li. A modified Polak-Ribière-Polyak conjugate gradient algorithm for nonsmooth convex programs[J].Journal of Computational and Applied Mathematics, 2014 (255):86-96.

[18] J. Z. Zhang, N. Y. Deng, L. H. Chen, New quasi-Newton equation and related methods for unconstrained optimization[J]. Journal of Optimization Theory and Application, 1999 (102):147-167.

[責(zé)任編輯蘇琴][責(zé)任校對黃祖賓]

A Conjugate Gradient Optimization Method and Its Applications in Engineer

HUANG Ling-hua

(DepartmentofMathematicsandStatistics,GuangxiUniversityofFinanceandEconomics,Nanning530003,China)

In this paper, a conjugate gradient method is proposed. The given method possess the following features: 1) The search direction possesses the sufficient descent property; 2) The search direction belongs to a trust region;3) The new method has not only the gradient value but also function value;4) The presented method has the global convergence for general functions. Numerical results turns out the new method is more competitive to the normal method.

conjugate gradient；sufficient descent；trust region；convergence

2016-03-20.

廣西財經(jīng)學(xué)院數(shù)量經(jīng)濟學(xué)重點實驗室項目開放性課題(2014SYS05)；國家自然科學(xué)基金項目資助(11161003).

黃玲花(1965-)，女，廣西財經(jīng)學(xué)院信息與統(tǒng)計學(xué)院副教授，研究方向:應(yīng)用數(shù)學(xué).

O224

A

1673-8462(2016)02-0063-05