一類推廣的共軛梯度法及收斂性分析

鄭小平，陳忠 (長江大學信息與數學學院，湖北 荊州 434023)

?

一類推廣的共軛梯度法及收斂性分析

鄭小平，陳忠 (長江大學信息與數學學院，湖北 荊州 434023)

共軛梯度法由于其計算量小、收斂速度快，在求解大規模無約束問題中起著重要作用。通過對參數βk的修正，構造了一種求解無約束問題新的共軛梯度算法，并證明了算法的全局收斂性。

無約束最優化；共軛梯度法；充分下降性；線搜索；全局收斂性

考慮無約束最優化問題：

(1)

其中，f:Rn→R為連續可微函數。求解問題(1)的迭代公式為：

xk+1=xk+αkdk

(2)

(3)

式中，gk=f(xk)；dk為搜索方向；αk≥0為步長因子；選取不同的βk可以構成不同的共軛梯度算法。比較常見的βk選取公式[1～4]有：

其中,‖·‖為歐式范數。

文獻[5]給出了一族包含CD方法的新共軛梯度算法,并證明了它們在非精確線性搜索下具有全局收斂性；文獻[6]給出了收斂共軛梯度法參數βk的構造條件并建立了其收斂性定理。下面筆者給出一種新的βk的選取方法：

(4)

式中，μ為參數。

顯然, μ=0時式(4)為CD公式，μ=1時式(4)為HS公式。

1 算法描述

步1 給定x1∈Rn，ε>0，0<ρ<σ<1，令d1=-g1，k=1；

步2 利用Wolfe線性搜索準則求得αk：

(5)

(6)

步3 計算xk+1=xk+αkdk；如果‖gk+1‖≤ε，則停止；否則轉步4;

步4 由式(4)計算βk，由式(3)計算dk；

步5 令k=k+1，轉步2。

2 算法全局收斂性

假設(H)：

(ii)f(x)在水平集L的某個鄰域N內，其導函數g滿足Lipschitz條件，即存在常數M>0，使得:

‖g(x)-g(y)‖≤M‖x-y‖ ?x,y∈N

(7)

證明采用數學歸納法。

當n=k-1時，由式(3)和式(4)有：

(8)

結合式(4)和式(6)可知：

綜上，引理1得證。

(9)

證明采用反證法。假設定理1不成立，則存在常數c>0，使得：

‖gk‖2>c k=1,2,3,…

(10)

由式(6)可得：

從而有：

(11)

由式(3)可得：

dk+gk=βkdk-1

兩邊取平方移項可得：

故而有：

又：

則：

即：

[1]Hestenes M R, Stiefel E. Methods of conjugate gradients for solving linear syste-ms[J]. J Res Nat Bur Standards Sect,1952,49(5):409～436.

[2]Polyack B T. The conjugate gradient method in extreme problems[J].USSR Computational Mathematics and Mathematical Physics,1969,9(1):94～112.

[3]Fletcher R, Reeves C M. Function minimization by conjugate gradients [J]. The C-Omputer Journal, 1964,7(2):149～154.

[4]Fletcher R.Practical Methods of Optimization: Vol.2: Constrained Optimization [M]. John Wiley & Sons Inc,1987.

[5]高麗，謝鐵軍.Wolfe線搜索下新的共軛梯度法的全局收斂性[J].運籌與管理，2008，17(1):38～41.

[6]Zhang Liwei.Conditions on Parameter βkin a Convergent Conjugate Gradi-ent Method[J].運籌學學報，1999,3(2):71～81.

[編輯] 張濤

2016-09-15

國家自然科學基金項目(61273179)。

陳忠(1964-)，男，博士(后)，教授，博士生導師，現主要從事最優化理論與算法方面的教學與研究工作；E-mail：czhong@yangtzeu.edu.cn。

O224

A

1673-1409(2016)34-0001-03

[引著格式]鄭小平，陳忠.一類推廣的共軛梯度法及收斂性分析[J].長江大學學報(自科版)，2016,13(34)：1～3.