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

鄭小平，陳忠 (長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

?

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

鄭小平，陳忠 (長(zhǎng)江大學(xué)信息與數(shù)學(xué)學(xué)院，湖北 荊州 434023)

共軛梯度法由于其計(jì)算量小、收斂速度快，在求解大規(guī)模無(wú)約束問(wèn)題中起著重要作用。通過(guò)對(duì)參數(shù)βk的修正，構(gòu)造了一種求解無(wú)約束問(wèn)題新的共軛梯度算法，并證明了算法的全局收斂性。

無(wú)約束最優(yōu)化；共軛梯度法；充分下降性；線搜索；全局收斂性

考慮無(wú)約束最優(yōu)化問(wèn)題：

(1)

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

xk+1=xk+αkdk

(2)

(3)

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

其中,‖·‖為歐式范數(shù)。

文獻(xiàn)[5]給出了一族包含CD方法的新共軛梯度算法,并證明了它們?cè)诜蔷_線性搜索下具有全局收斂性；文獻(xiàn)[6]給出了收斂共軛梯度法參數(shù)βk的構(gòu)造條件并建立了其收斂性定理。下面筆者給出一種新的βk的選取方法：

(4)

式中，μ為參數(shù)。

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

1 算法描述

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

步2 利用Wolfe線性搜索準(zhǔn)則求得αk：

(5)

(6)

步3 計(jì)算xk+1=xk+αkdk；如果‖gk+1‖≤ε，則停止；否則轉(zhuǎn)步4;

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

步5 令k=k+1，轉(zhuǎn)步2。

2 算法全局收斂性

假設(shè)(H)：

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

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

(7)

證明采用數(shù)學(xué)歸納法。

當(dāng)n=k-1時(shí)，由式(3)和式(4)有：

(8)

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

綜上，引理1得證。

(9)

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

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

(10)

由式(6)可得：

從而有：

(11)

由式(3)可得：

dk+gk=βkdk-1

兩邊取平方移項(xiàng)可得：

故而有：

又：

則：

即：

[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].運(yùn)籌與管理，2008，17(1):38～41.

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

[編輯] 張濤

2016-09-15

國(guó)家自然科學(xué)基金項(xiàng)目(61273179)。

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

O224

A

1673-1409(2016)34-0001-03

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