兩類無約束優化的充分下降共軛梯度法

孫中波, 段復建, 高海音, 于海鷗

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

0 引 言

考慮無約束優化問題

(1)

其中:f: Rn→R1是連續可微函數; Rn為Euclidean空間. 對無約束優化問題(1), 一般采用線搜索方法進行近似求解, 即

xk+1=xk+αkdk,

(2)

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

時貞軍等[8]提出一種混合共軛梯度法, 該方法通過引入參數μ, 得到一個新的共軛梯度公式:

(3)

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

(4)

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

及

dk=-θkgk+βkdk-1,

(5)

第一類搜索方向dk計算公式如下:

(6)

第二類搜索方向dk計算公式如下:

(7)

對于第一類搜索方向, 當λ=0時, 混合算法可以轉化為FR共軛梯度法; 當λ=1時, 混合算法可以轉化為CD共軛梯度法. 并且兩個搜索方向dk均具有充分下降性. 在適當的條件下, 證明了算法是全局收斂的, 數值實驗表明算法可行、 有效.

1 算 法

由式(2)可見, 迭代過程的產生離不開步長搜索, 即步長αk的求解. 搜索步長的產生有很多種, 如單調線搜索準則和非單調線搜索準則等, 包括有單調的Armijo,Wolfe,Goldstien準則和非單調的Armijo,Wolfe,Goldstien準則. 文獻[13]提出了一個修正的Armijo準則:

本文結合文獻[13], 采用推廣到非單調的Armijo準則求解步長αk:

(8)

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

算法1

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

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

(9)

3) 計算xk+1: 令xk+1=xk+αkdk, 轉4);

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

當步驟2)中的M=0時, 非單調線搜索算法即轉化為單調線搜索算法. 算法1實際上是兩類求解無約束優化問題的充分下降算法, 區別在于步驟1)中搜索方向dk的求解.

2 算法適定性

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

假設2目標函數f(x)的梯度f(x)是Lipschitz連續函數, 即存在常數滿足

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

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

定理1假設1成立, 搜索方向dk由式(6)計算得到, 則(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當搜索方向為式(6)時, 算法1是適定的.

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

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

1) 同定理1中1);

注2當搜索方向為式(7)時, 算法1是適定的. 由定理1和定理2可知, 算法1的充分下降性不需要線搜索保證, 搜索方向自身具有下降的性質.

3 全局收斂性分析

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

引理2如果存在一個正常數>0, 使得

‖gk‖≥, ?k,

(10)

?k.

(11)

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

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

(12)

‖gk‖≥, ?k

(13)

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

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

(14)

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

即

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

(16)

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

其中

4 數值實驗

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

1) Rosenbrock函數:

2) Freudenstein Roth函數:

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

3) Trigonometrix函數:

表1 算法1數值結果

表2 文獻[9]數值結果

表3 FR共軛梯度法數值結果

表4 CD共軛梯度法數值結果

表5 算法1為單調線搜索的數值結果

在表1中, 采用非單調線搜索產生搜索步長αk, 并且選取M=9. 由表1可見, 本文提出的算法可行、 有效. 在表2中, 文獻[9]的算法在CPU時間和迭代步數上均超過了本文提出的算法1, 表明本文提出的充分下降方向確實優于文獻[9]中的算法. 當λ=0時, 混合算法可以轉化為FR共軛梯度法; 當λ=1時, 混合算法可以轉化為CD共軛梯度法. 因此, 表3和表4分別是測試FR和CD共軛梯度法, 比較可見, 經典共軛梯度法的CPU所用時間和迭代步數均超過本文算法, 尤其當測試函數的維數較高時. 本文算法無論是從CPU時間, 還是迭代步數均比其他幾個算法少, 顯示了算法1的優越性. 在表5中, 選取M=0, 即算法1采用單調線搜索的情況, 數值結果表明, 非單調線搜索產生的步長比單調搜索步長更合理.

[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. (孫中波, 段復建. 一類無約束優化的非單調共軛梯度法 [J]. 河南師范大學學報: 自然科學版, 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.