兩類無(wú)約束優(yōu)化的充分下降共軛梯度法

孫中波, 段復(fù)建, 高海音, 于海鷗

(1. 東北師范大學(xué)人文學(xué)院 數(shù)學(xué)系, 長(zhǎng)春 130117; 2. 桂林電子科技大學(xué) 數(shù)學(xué)與計(jì)算科學(xué)學(xué)院, 廣西 桂林 541004; 3. 長(zhǎng)春大學(xué) 理學(xué)院, 長(zhǎng)春 130022)

0 引 言

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

(1)

其中:f: Rn→R1是連續(xù)可微函數(shù); Rn為Euclidean空間. 對(duì)無(wú)約束優(yōu)化問(wèn)題(1), 一般采用線搜索方法進(jìn)行近似求解, 即

xk+1=xk+αkdk,

(2)

其中:αk為線搜索步長(zhǎng); {xk+1}為迭代產(chǎn)生的迭代序列;dk為線搜索方向. 針對(duì)問(wèn)題(1), 文獻(xiàn)[1-7]分別給出了不同的共軛梯度公式, 進(jìn)而得到不同的共軛梯度法, 即

時(shí)貞軍等[8]提出一種混合共軛梯度法, 該方法通過(guò)引入?yún)?shù)μ, 得到一個(gè)新的共軛梯度公式:

(3)

其中μ∈[0,1]. 當(dāng)μ=0時(shí), 混合算法轉(zhuǎn)化為PRP共軛梯度法; 當(dāng)μ=1時(shí), 混合算法轉(zhuǎn)化為L(zhǎng)S共軛梯度法. 根據(jù)算法產(chǎn)生的不同βk, 搜索方向的下降性也不同. 文獻(xiàn)[8]中搜索方向的下降性取決于參數(shù)c的選取, 當(dāng)c=1時(shí), 該算法產(chǎn)生的搜索方向是充分下降的, 但當(dāng)c=10-10時(shí), 參數(shù)c很小, 每次迭代都不能產(chǎn)生充分下降方向,會(huì)嚴(yán)重影響算法的計(jì)算效率. 孫中波等[9]提出了另外一種混合共軛梯度法. 與文獻(xiàn)[8]類似, 共軛梯度公式如下:

(4)

其中λ∈[0,1]. 當(dāng)λ=0時(shí), 混合算法轉(zhuǎn)化為FR共軛梯度法; 當(dāng)λ=1時(shí), 混合算法轉(zhuǎn)化為CD共軛梯度法. 由βk1產(chǎn)生的搜索方向也不能保證每次迭代都為充分下降方向. 如當(dāng)δ/λ=0.999 99或者δ/λ充分接近1時(shí), 算法的計(jì)算效率就會(huì)受到影響. 張利等[10]提出了兩種混合共軛梯度算法, 即

及

dk=-θkgk+βkdk-1,

(5)

第一類搜索方向dk計(jì)算公式如下:

(6)

第二類搜索方向dk計(jì)算公式如下:

(7)

對(duì)于第一類搜索方向, 當(dāng)λ=0時(shí), 混合算法可以轉(zhuǎn)化為FR共軛梯度法; 當(dāng)λ=1時(shí), 混合算法可以轉(zhuǎn)化為CD共軛梯度法. 并且兩個(gè)搜索方向dk均具有充分下降性. 在適當(dāng)?shù)臈l件下, 證明了算法是全局收斂的, 數(shù)值實(shí)驗(yàn)表明算法可行、 有效.

1 算 法

由式(2)可見(jiàn), 迭代過(guò)程的產(chǎn)生離不開步長(zhǎng)搜索, 即步長(zhǎng)αk的求解. 搜索步長(zhǎng)的產(chǎn)生有很多種, 如單調(diào)線搜索準(zhǔn)則和非單調(diào)線搜索準(zhǔn)則等, 包括有單調(diào)的Armijo,Wolfe,Goldstien準(zhǔn)則和非單調(diào)的Armijo,Wolfe,Goldstien準(zhǔn)則. 文獻(xiàn)[13]提出了一個(gè)修正的Armijo準(zhǔn)則:

本文結(jié)合文獻(xiàn)[13], 采用推廣到非單調(diào)的Armijo準(zhǔn)則求解步長(zhǎng)αk:

(8)

其中, 0≤m(k+1)≤min{m(k)+1,M},M為充分大的正整數(shù).

算法1

初始化: 假設(shè)x0∈Rn為任意初始點(diǎn), 0<λ<1,σ∈(0,1/2),m(0)=0,k∶=0. 步驟如下.

1) 終止條件判定并計(jì)算dk: 如果‖gk‖≤ε, 則算法停止; 否則分別采用式(6),(7)計(jì)算dk, 轉(zhuǎn)2);

(9)

3) 計(jì)算xk+1: 令xk+1=xk+αkdk, 轉(zhuǎn)4);

4)k=k+1, 返回1).

當(dāng)步驟2)中的M=0時(shí), 非單調(diào)線搜索算法即轉(zhuǎn)化為單調(diào)線搜索算法. 算法1實(shí)際上是兩類求解無(wú)約束優(yōu)化問(wèn)題的充分下降算法, 區(qū)別在于步驟1)中搜索方向dk的求解.

2 算法適定性

假設(shè)1水平集Λ={x∈Rn:f(x)≤f(x0)}有下界, 其中x0為初始點(diǎn), 且Λ為有界閉凸集.

假設(shè)2目標(biāo)函數(shù)f(x)的梯度f(wàn)(x)是Lipschitz連續(xù)函數(shù), 即存在常數(shù)滿足

‖f(y)-?y,z∈Rn.

由算法1知, 迭代序列{xk}始終保持在水平集Λ. 還可以得到如下結(jié)論: 存在一個(gè)正常數(shù)κ>0, 使得‖g(x)‖≤κ, ?x∈Λ.

定理1假設(shè)1成立, 搜索方向dk由式(6)計(jì)算得到, 則(gk)Tdk=-‖gk‖2<0.

證明: 由算法1知, 有如下兩種情況:

1) 若k=0, 則dk=-gk, 有(gk)Tdk=-(gk)Tgk=-‖gk‖2<0;

2) 若k>0, 則dk=-gk+βk1dk-1-νkgk, 其中βk1由式(4)確定, 有

注1當(dāng)搜索方向?yàn)槭?6)時(shí), 算法1是適定的.

定理2假設(shè)1成立, 搜索方向dk由式(7)計(jì)算得到, 則(gk)Tdk=-‖gk‖2<0.

證明: 由算法1知, 有如下兩種情況:

1) 同定理1中1);

注2當(dāng)搜索方向?yàn)槭?7)時(shí), 算法1是適定的. 由定理1和定理2可知, 算法1的充分下降性不需要線搜索保證, 搜索方向自身具有下降的性質(zhì).

3 全局收斂性分析

證明: 由算法1的步驟2)知,

引理2如果存在一個(gè)正常數(shù)>0, 使得

‖gk‖≥, ?k,

(10)

?k.

(11)

證明: 由式(6)及假設(shè)1和假設(shè)2, 有

定理3假設(shè)1和假設(shè)2成立, {xk}由算法1生成, 每次迭代過(guò)程中, {dk}為式(6)產(chǎn)生的充分下降方向. 若αk由非單調(diào)Armijo線搜索, 則

(12)

‖gk‖≥, ?k

(13)

成立. 下面分兩種情況討論：

由算法1的步驟2)知, 當(dāng)k∈Π充分大時(shí),ρ-1αk不滿足步驟2), 即

(14)

利用中值定理及其引理4知, 存在hk∈(0,1), 使得

即

定理4假設(shè)1和假設(shè)2成立, {xk}由算法1生成, 每次迭代過(guò)程中, {dk}為式(7)產(chǎn)生的充分下降方向. 若αk由非單調(diào)Armijo線搜索, 則

(16)

證明: 由算法1及假設(shè)2和引理2, 有

其中

4 數(shù)值實(shí)驗(yàn)

本文采用Rosenbrock,Freudenstein Roth,Trigonometrix函數(shù)為測(cè)試函數(shù)[16]. 在Matlab7.1環(huán)境下編寫程序代碼: CPU為奔騰(R) 2.19 GHz, 1 Gb內(nèi)存.

1) Rosenbrock函數(shù):

2) Freudenstein Roth函數(shù):

f(x)=[-13+x1+((5-x2)x2-2)x2]2+[-29+x1+((x2+1)x2-14)x2]2;

3) Trigonometrix函數(shù):

表1 算法1數(shù)值結(jié)果

表2 文獻(xiàn)[9]數(shù)值結(jié)果

表3 FR共軛梯度法數(shù)值結(jié)果

表4 CD共軛梯度法數(shù)值結(jié)果

表5 算法1為單調(diào)線搜索的數(shù)值結(jié)果

在表1中, 采用非單調(diào)線搜索產(chǎn)生搜索步長(zhǎng)αk, 并且選取M=9. 由表1可見(jiàn), 本文提出的算法可行、 有效. 在表2中, 文獻(xiàn)[9]的算法在CPU時(shí)間和迭代步數(shù)上均超過(guò)了本文提出的算法1, 表明本文提出的充分下降方向確實(shí)優(yōu)于文獻(xiàn)[9]中的算法. 當(dāng)λ=0時(shí), 混合算法可以轉(zhuǎn)化為FR共軛梯度法; 當(dāng)λ=1時(shí), 混合算法可以轉(zhuǎn)化為CD共軛梯度法. 因此, 表3和表4分別是測(cè)試FR和CD共軛梯度法, 比較可見(jiàn), 經(jīng)典共軛梯度法的CPU所用時(shí)間和迭代步數(shù)均超過(guò)本文算法, 尤其當(dāng)測(cè)試函數(shù)的維數(shù)較高時(shí). 本文算法無(wú)論是從CPU時(shí)間, 還是迭代步數(shù)均比其他幾個(gè)算法少, 顯示了算法1的優(yōu)越性. 在表5中, 選取M=0, 即算法1采用單調(diào)線搜索的情況, 數(shù)值結(jié)果表明, 非單調(diào)線搜索產(chǎn)生的步長(zhǎng)比單調(diào)搜索步長(zhǎng)更合理.

[1] Fletcher R, Reeves C M. Function Minimization by Conjugate Gradients [J]. The Computer Journal, 1964, 7(2): 149-154.

[2] Poliak B T. The Conjugate Gradient Method in Extreme Problems [J]. USSR Comput Math and Math Phys, 1969, 9(14): 94-112.

[3] Fletcher R. Practical Methods of Optimization [M]. New York: Wiley, 1987.

[4] Polak M R, Ribiere G. Note Sur la Convergence de Méthodes de Directions Conjuguées [J]. Revue Francaise d’Informatique et de Recherche Opérationelly, 1969, 16: 35-43.

[5] Liu Y, Storey C. Efficient Generalized Conjugate Gradient Algorithms, Part 1: Theory [J]. J of Optim Theorem and Appl, 1991, 69(1): 129-137.

[6] Dai Y H, Yuan Y. An Efficient Hybrid Conjugate Gradient Method for Unconstrained Optimization [J]. Ann of Oper Res, 2001, 103(1/4): 33-47.

[7] DAI Yu-hong, HAN Ji-ye, LIU Guang-hui, et al. Convergence Properties of Nonlinear Conjugate Gradient Methods [J]. SIAM J of Optim, 1999, 21: 348-358.

[8] SHI Zhen-jun, GUO Jin-hua. A New Family of Conjugate Gradient Methods [J]. J of Comput and Appl Math, 2009, 224(1): 444-457.

[9] SUN Zhong-bo, DUAN Fu-jian. A Class of Nonmonotone Conjugate Gradient Methods for Unconstrained Optimization [J]. Journal of Henan Normal University: Natural Science, 2010, 38(1): 12-15. (孫中波, 段復(fù)建. 一類無(wú)約束優(yōu)化的非單調(diào)共軛梯度法 [J]. 河南師范大學(xué)學(xué)報(bào): 自然科學(xué)版, 2010, 38(1): 12-15.)

[10] ZHANG Li, ZHOU Wei-jun. Two Descent Hybrid Conjugate Gradient Methods for Optimization [J]. J of Comput and Appl Math, 2008, 216(1): 251-264.

[11] Birgin E G, Martínez J M. A Spectral Conjugate Gradient Method for Unconstrained Optimization [J]. Appl Math & Optim, 2001, 43(2): 117-128.

[12] Raydan M. The Barzilain and Borwein Gradient Method for the Large Scale Unconstrained Minimization Problem [J]. SIAM J on Optim, 1997, 7(1): 26-33.

[13] ZHANG Li, ZHOU Wei-jun, LI Dong-hui. A Descent Modified Polak-Ribiere-Polyak Conjugate Gradient Method and Its Global Convergence [J]. IMA J of Numer Anal, 2006, 26(4): 629-640.

[14] ZHANG Li, ZHOU Wei-jun, LI Dong-hui. Global Convergence of a Modified Fletcher-Reeves Conjugate Gradient Method with Armijo-Type Line Search [J]. Numer Math, 2006, 104(4): 561-572.

[15] DUAN Fu-jian, SUN Zhong-bo. A Modified Liu-Storey Conjugate Gradient Method and Its Global Convergence for Unconstrained Optimization [C]//Proceeding of Chinese Control and Decision Conference. Shenyang: North East University Press, 2010: 1585-1588.

[16] More J J, Garbow B S, Hillstrom K E. Testing Unconstrained Optimization Software [J]. J ACM Trans on Math Software, 1981, 7(1): 17-41.