黃玲花

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

?

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

黃玲花

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

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

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

0　引言

(1)

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

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

(2)

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

(3)

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

(4)

(5)

(6)

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

(7)

(8)

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

1　算法

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

步驟0：給定x0∈Rn，c∈(0,1),δ∈(0,1/2),σ∈(δ,1)和終止參數ε>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，轉步驟2.

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

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

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

(9)

(10)

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

因此(10)成立.證畢.

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

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

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

(11)

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

(12)

3　數值結果

為了驗證算法的有效性，給出數值檢驗結果，檢驗函數是在工程領域經常用到的Benchmark問題，這些問題列舉如下.

1)Spherefunction.

2)Schwefel'sfunction.

3)Rastriginfunction.

4)Schwefelfunction.

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

5)Griewankfunction.

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

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

表1　算法1的數值結果

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

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

4　結論

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

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

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

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

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

[責任編輯蘇琴][責任校對黃祖賓]

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.

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

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

O224

A

1673-8462(2016)02-0063-05