一種修正的DY共軛梯度法的全局收斂性

敖 衛(wèi) 斌

(重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶 401331)

一種修正的DY共軛梯度法的全局收斂性

敖 衛(wèi) 斌

(重慶師范大學(xué) 數(shù)學(xué)學(xué)院，重慶 401331)

提出了一種新的非線性修正的DY共軛梯度算法(MDYCG),該算法得到的搜索方向?yàn)橄陆捣较?，它既不受線搜索規(guī)則的影響；也不受目標(biāo)函數(shù)的凸性影響；在精確線搜索下，MDYCG算法化歸為標(biāo)準(zhǔn)的DY共軛梯度算法；證明了該方法在Armijo型線搜索下的全局收斂性，給出了初步的數(shù)值結(jié)果。

無(wú)約束優(yōu)化；共軛梯度法；Armijo型線搜索；全局收斂性

0 引 言

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

minf(x),x∈Rn

(1)

其中f：Rn→R為連續(xù)可微函數(shù)，其梯度向量記為g(x)，簡(jiǎn)記為g。

共軛梯度法是求解大規(guī)模無(wú)約束優(yōu)化問(wèn)題的有效算法之一，它像最速下降法一樣在每步迭代中不需要存儲(chǔ)和計(jì)算矩陣，其迭代格式：

xk+1=xk+αkdk

(2)

(3)

其中，gk=f(xk)，dk為搜索方向，αk是通過(guò)一維線搜索獲得的步長(zhǎng)，βk為標(biāo)量。不同的βk對(duì)應(yīng)著不同的共軛梯度算法。1964年, Fletcher和Reeves首先提出非線性共軛梯度法參數(shù)βk，它定義為還有其他著名的βk，比如：

其中‖·‖為歐幾里得范數(shù),yk-1=gk-gk-1。FR方法、CD方法和DY方法具有較好的理論收斂性，然而PRP方法、HS方法和LS方法具有較好的數(shù)值計(jì)算結(jié)果。

在文獻(xiàn)[9]的啟發(fā)下，選取不同的βk，提出了一種修正的DY算法(MDYCG)并證明了該算法在Armijo型線搜索下的全局收斂性。所采用的Armijo型線搜索準(zhǔn)則，取步αk：

αk=max{ρj,j=0,1,2,…}

(4)

(5)

其中ρ∈(0,1),δ1∈(0,1),δ2>0。

2 修正的DY新算法

本文給出的新算法迭代式(2)和式(6)：

(6)

(7)

下面給出新的算法步驟：

(1) 給出x1∈Rn，ρ∈(0,1),δ1∈(0,1),δ2∈(0,1),ε≥0，令k：=1,d1=-g1，若‖g1‖≤ε，立即停止；

(2) 找到αk>0滿足Armijo型線搜索規(guī)則；

(3) 令xk+1=xk+αkdk, 且gk+1=g(xk+1)，若‖gk‖≤ε，立即停止；

(5) 令k=k+1，返回(2)。

本文做如下假設(shè)：

(A)f(x)在水平集Ω={x∈Rn|f(x)≤f(x1)}有下界，其中x1為初始點(diǎn);

(B)Ω的一個(gè)領(lǐng)域N內(nèi)，f連續(xù)可微且其梯度向量滿足Lipschitz條件，即存在常數(shù)L>0，使得:

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

(8)

同時(shí)由上述的假設(shè)可以得到存在正常數(shù)β和γ滿足：

‖x‖≤β, ‖g(x)‖≤γ,?x∈Ω

(9)

3 算法的收斂性

如果αk<1, 由Armijo型線搜索規(guī)則,ρ-1αk不滿足式(5)。則有：

(10)

由中值定理和假設(shè)B，存在某一個(gè)tk∈(0,1)使得：

(11)

結(jié)合不等式(10)、式(11)和式(7)得：

證畢。

引理2 假設(shè)(A)，(B)成立，MDYCG算法中αk滿足Armijo型線搜索，則有Zoutendijk條件：

(12)

(13)

定理3 若假設(shè)(A)和(B)成立，MDYCG算法中αk滿足Armijo型線搜索，或者對(duì)某個(gè)k成立，或者有：

‖gk‖=0

證明反正法。假設(shè)結(jié)論不成立，則存在一個(gè)常數(shù)ε使得式(14)成立，式(14)如下：

‖gk‖≥ε，?k≥0

(14)

4 數(shù)值試驗(yàn)

本節(jié)在標(biāo)準(zhǔn)Armijo型非精確線搜索準(zhǔn)則下，利用MARTLAB 7.1， MDY方法對(duì)測(cè)試函數(shù)[10]進(jìn)行試算。表格中Problem表示測(cè)試函數(shù)的名稱,NI/NF/NG分別代表迭代次數(shù)、函數(shù)迭代次數(shù)、梯度迭代次數(shù)，Dim表示測(cè)試函數(shù)自變量的個(gè)數(shù)，“—”表示迭代失敗。計(jì)算中參數(shù)σ=0.5，ρ=0.8，取ε=10-5，VP代表極值點(diǎn)，OV代表極值。終止條件為‖gk‖≤10-5。表1簡(jiǎn)單的數(shù)值試驗(yàn)表明了新方法的特點(diǎn)，該方法是有效的。

表1 MDY方法在Armijo型搜索下的數(shù)值結(jié)果

[1] SHI Z J. Convergence of line search methods for unconstrained optimization [J]. Applied Mathematics andComputation, 2004(157)：393-405

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

[3] POLAK E ，RIBIERE G. Note sur la convergence de directions conjugees[J]. Rev Francaise InformatRecherche Operatinelle, 3e Annee, 1969(16)： 35-43

[4] POLAKB T. The conjugate gradient method in extremem problems[J]. USSR Comp Math and Math. Phys.1969(9)： 94-112

[5] HESTENES M R， STEIFEL E L. Methods of conjugate gradients for solving linear systems[J]. J Res Nat Bur Standards Sect. 1952, 5(49)： 409-436

[6] LIU Y， STIEFELC. Efficient generalized conjugate gradient algorithms[J].JOTA, 1991， 69(1)： 129-152

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

[8] FLETCHER R. Practical methods of optimization [M]. New York： Unconstrained Optimization,1987

[9] ZHANG L, ZHOU W.LI D. Global convergence of a modified Fletcher-Reeves conjugate gradientmethod method with Armijo-type line search[J]. Numerische Mathematik 2006,104(4)：561-572

[10] MORE J,GARBOW B,HILLSTROMK E. Testing unconstrained optimization software[J].ACM Trans,Math.Software,1981,7(1)：17-41

Global Convergence for a Modified DY Conjugate Gradient Algorithm

AOWei-bin

(School of Mathematics, Chongqing Normal University, Chongqing 401331, China)

This paper proposes a kind of new nonlinear modified DY conjugate gradient algorithm, whose search direction is descent direction and which is not affected by line search rule and is not affected by the convexity of objective function either.Under accurate line search, the modified DY conjugate gradient algorithm is turned to standard DY conjugate algorithm. This paper proves the global convergence of this algorithm under Armijo-type line search and gives initial numerical result.

unconstrained optimization；conjugate gradient algorithm；Armijo-type line search；global convergence

1672-058X(2013)10-0017-04

2013-04-07；

2013-05-07.

敖衛(wèi)斌(1987-)，男，重慶九龍坡人，碩士研究生，從事最優(yōu)化理論與研究.

O182.1

A

責(zé)任編輯：代小紅