敖 衛(wèi) 斌

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

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

敖 衛(wèi) 斌

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

提出了一種新的非線性修正的DY共軛梯度算法(MDYCG),該算法得到的搜索方向為下降方向，它既不受線搜索規(guī)則的影響；也不受目標函數的凸性影響；在精確線搜索下，MDYCG算法化歸為標準的DY共軛梯度算法；證明了該方法在Armijo型線搜索下的全局收斂性，給出了初步的數值結果。

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

0 引 言

考慮無約束優(yōu)化問題：

minf(x),x∈Rn

(1)

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

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

xk+1=xk+αkdk

(2)

(3)

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

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

在文獻[9]的啟發(fā)下，選取不同的βk，提出了一種修正的DY算法(MDYCG)并證明了該算法在Armijo型線搜索下的全局收斂性。所采用的Armijo型線搜索準則，取步α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)。

本文做如下假設：

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

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

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

(8)

同時由上述的假設可以得到存在正常數β和γ滿足：

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

(9)

3 算法的收斂性

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

(10)

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

(11)

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

證畢。

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

(12)

(13)

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

‖gk‖=0

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

‖gk‖≥ε，?k≥0

(14)

4 數值試驗

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

表1 MDY方法在Armijo型搜索下的數值結果

[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

責任編輯：代小紅