一類修正的DY共軛梯度法

陳 恩

(重慶師范大學 數學科學學院， 重慶 401331)

1 背景

考慮如下的無約束最優化問題：

minf(x),x∈Rn

(1)

其中要求目標函數f是連續可微的，它的梯度函數gx是可獲得的。

共軛梯度法是解決上面無約束優化問題的最有效方法之一，它的一般迭代格式如下：

xk+1=xk+αkdk

(2)

(3)

其中：αk是通過計算某種線搜索獲得的步長；gk=▽f(xk)；βk是共軛梯度法中的一個參數。著名的共軛梯度法有HS方法[1]、FR方法[2]、PRP方法[3-4]、CD方法[5]、LS方法[6]以及DY方法[7]，它們的參數βk分別如下：

其中：||·||為歐幾里得范數；yk-1=gk-gk-1。

另外，比較常見的線搜索有標準Wolfe線搜索，它要求步長αk滿足：

(4)

(5)

其中0<δ<σ<1。

共軛梯度算法要求搜索方向滿足下降性條件：

?k≥0

(6)

或者滿足充分下降性條件：

?k≥0,c>0

(7)

2006年，Wei等在文獻[8]中對經典的PRP方法進行了修正，提出了如下的參數公式，并證明了該方法在標準Wolfe線搜索條件下對一般函數的全局收斂性：

(8)

2007年，Yao等受文獻[8]的啟發,在文獻[9]中提出了如下兩種修正的HS和LS方法：

(9)

2009年，Zhang在文獻[10]中進一步修正上面的參數公式為：

(10)

2010年，Wei等在文獻[11]提出了一個新的參數公式：

(11)

2011年，江等在文獻[12]中進一步修正上面的參數，提出了如下參數公式：

(12)

2 方法的提出

(13)

(14)

3 收斂性分析

為了獲得由式(2)(3)(14)組成的共軛梯度方法的全局收斂性，本文作如下兩個基本假設：

1) 水平集Ω={x∈Rn:f(x)

2) 目標函數f在水平集Ω的某個領域N上是連續可微的，并且梯度函數g滿足Lipschitz連續，即存在一個常數L>0使得

(15)

(16)

證明完畢。

現給出著名的Zoutendijk條件：

引理2 若假設1)、2)成立，考慮迭代公式為(2)(3)的共軛梯度方法。當方向dk為下降方向，步長αk滿足標準Wolfe線搜索的條件時，有

(17)

證明過程見文獻[7]的引理3.2。

(18)

因為dk=-gk+βkdk-1，有：dk+gk=βkdk-1。兩邊同時平方后有：

(19)

(20)

所以有：

(21)

式(21)與Zoutendijk條件的式(17)矛盾，于是定理得證。

[1] HESTENES M R，STIEFEL E.Method of conjugate gradient for solving linear equations[J].J Res Nat Bur Stand，1952，49:409-436.

[2] FLETCHER R，REEVES C M.Function minimization by conjugate gradients[J].The Computer Journal，1964,7(2):149-154.

[3] POLAK E，RIBIERE G.Note sur la convergence de méthodes de directions conjuguées[J].ESAIM:Mathematical Modelling and Numerical Analysis-Modélisation Mathématique et Analyse Numérique，1969，3(R1):35-43.

[4] POLYAK B T.The conjugate gradient method in extremal problems[J].USSR Computational Mathematics and Mathematical Physics，1969，9(4):94-112.

[5] FLETCHER R.Practical Methods of Optimization vol.1:Unconstrained Optimization[M].New York:John Wiley & Sons，1987.

[6] LIU Y，STOREY.Efficient generalized conjugate gradient algorithms，Part 1:Theory[J].Journal of Optimization Theory and Applications，1991，69(1):129-137.

[7] DAI Y H，YUAN Y.A nonlinear conjugate gradient method with a strong global convergence property[J].SIAM Journal on Optimization，1999，10(1):177-182.

[8] WEI Z X,YAO S W,LIU L Y.The convergence properties of some new conjugate gradient methods[J].Applied Mathematics and Computation,2006,183(2):1341-1350.

[9] YAO S W，WEI Z X，HUANG H.A note about WYLs conjugate gradient method and its applications[J].Applied Mathematics and Computation,2007,191:381-388.

[10] ZHANG L.An improved Wei-Yao-Liu nonlinear conjugate gradient method for optimization computation[J].Applied Mathematics and computation，2009，215(6):2269-2274.

[11] WEI Z X，HUANG H D，TAO Y R.A modified hestenes-stiefel conjugate gradient method and its convergence[J].Journal of Mathematical Research with Applications，2010，30(2):297-308.

[12] 江羨珍，馬國棟，簡金寶.Wolfe線搜索下一個新的全局收斂共軛梯度法[J].工程數學學報，2011，28(6):779-786.