陳 貞 晶

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

共軛梯度法是求解大規(guī)模無約束優(yōu)化問題的最有效的方法之一，具有所需存儲量小、強收斂性和計算方便等優(yōu)點。比如考慮無約束優(yōu)化問題 minf(x),x∈Rn，共軛梯度法的一般迭代格式為：

xk+1=xk+αkdk

(1)

d0=-g0,dk+1=-gk+1+βkdk

(2)

其中：αk是通過某種線搜索獲得的步長，αk>0；dk+1是搜索方向；g(x)是目標函數(shù)f(x)的梯度，gk+1=▽f(xk+1)；βk是共軛梯度參數(shù)，簡稱CG參數(shù)。不同的βk值，對應不同的共軛梯度方法。

常用的線搜索有很多，我們在這里只考慮Wolfe線搜索：

f(xk+αkdk)-f(xk)≤δαk▽f(xk)Tdk

(3)

▽f(xk+αkdk)Tdk≥σ▽f(xk)Tdk

(4)

其中，0<δ<σ<1。

Hestenes-Stiefel(簡稱“HS”)方法和Dai-Yuan(簡稱“DY”)方法都是經典的共軛梯度方法，其參數(shù)[1]如下：

HS方法在非精確線搜索下不能保證收斂性，可能無限循環(huán)，且不趨近于任何一個解點，但數(shù)值計算效果較好。DY方法具有強收斂性，但由于在計算時會受干擾現(xiàn)象的影響，計算效果不佳[2]。

1 HCG方法的修正

1.1 HCG方法

2008年，Neculai Andrei基于擬牛頓方向滿足割線條件，提出了混合的HS和DY方法[2]，簡稱HCG方法。其CG參數(shù)如下：

其中

割線方程為Bk+1sk=yk。

HCG方法的計算效果不是很好，不如經典的HS方法。

1.2 ZZL方法

2015年，Saman Babaie-Kafaki和Reza Ghanbari[2]基于HCG方法，采用最小二乘思想，將HCG方法的搜索方向逼近三項共軛梯度法方向[3]之間，極小化后，獲得混合參數(shù)θk新的取值，即

(5)

其中，三項共軛方向如下所示：

(6)

HCG方法的搜索方向和CG參數(shù)如下：

?k≥0

(7)

(8)

對CG參數(shù)進行非負限制，得

這個方法簡稱HCG+方法。HCG+方法在Wolfe線搜索下全局收斂，計算時間上優(yōu)于HS和DY 方法。

1.3 EZZL方法

為了減少計算時間，我們采用文獻[2]中的最小二乘思想，將ZZL方法替換成帶有參數(shù)tk的EZZL方法[4]，即

(9)

所以

(10)

其中

?k≥0

(11)

tk是一個混合參數(shù)。通過對ZZL方法的搜索方向矩陣進行特征值分析，可得參數(shù)tk的取值。

η∈(0,1]

(12)

該擴展的搜索方向，在不依賴任何線搜索和目標函數(shù)的凸性下，滿足充分下降條件。EZZL方法對一致凸函數(shù)全局收斂，且計算上優(yōu)于ZZL方法。其中，η=0.96。

1.4 HCGQN方法

2018年，Babaie-Kafaki和Ghanbari基于HS方法和無記憶BFGS方法的線性組合，提出了一個新的混合的方法[5]，簡稱HCGQN方法。其中，無記憶BFGS校正形式為：

其搜索方向如下：

(13)

當目標函數(shù)是一致凸函數(shù)時，滿足充分下降條件。

對上述的搜索方向引入一個基于最小二乘技巧求解的混合參數(shù)θk，則式(13)可以寫成如下形式：

其中

通過求解下列最小二乘問題，獲得混合參數(shù)θk。

(14)

(15)

其中，ξ是一個很小的正數(shù)。在數(shù)值計算上，HCGQN方法勝過HS和ZZL方法，ξ=10-7。

1.5 MHCG方法

為了減少計算所用的時間，利用文獻[2]中采用HCG方法逼近一個充分下降的三項共軛梯度法的思想，將HCG方法[1]逼近一個帶有參數(shù)的三項共軛梯度法EZZL[4]，使得計算效果優(yōu)于HCG方法。對混合共軛梯度方法采用極小化最小二乘問題來求解參數(shù)θk。

θk∈[0,1]

(16)

通過將HCG方法的搜索方向與EZZL方法的搜索方向的距離之差極小化，可得

(17)

所以有

(18)

MHCG方法的計算步驟如下：

Step1: 初始化x0∈Rn，且0<δ<σ<1，令k:=0。

Step3: 通過式(2)(12)(16)(18)計算下降方向dk+1。

Step4: 步長αk由式(3)(4)決定。

Step5: 令xk+1=xk+αkdk。

Step6: 令k:=k+1，且轉入Step2。

2 MHCG方法的收斂性

在證明收斂性之前，先給出目標函數(shù)的兩個基本假設和一些重要的引理、定理。

2.1 基本假設

對目標函數(shù)進行以下基本假設[2]。

(19)

2.2 引理

[引理1](充分下降條件) 考慮迭代方法如式(1)(2)，CG參數(shù)如式(16)，混合參數(shù)θk如式(18)，tk的取值如式(12)，在Wolfe線搜索下，搜索方向dk+1滿足充分下降條件。

(20)

當k≥1時

因此，有

(21)

由引理1，可得

2.3 收斂性證明

下面，證明MHCG方法滿足性質(*)。

性質(*)：考慮由式(1)(2)產生的共軛梯度法MHCG，假設

(22)

在假設A、B下，我們說MHCG方法滿足性質(*)，如果存在常數(shù)b>1和λ>0，使得對任意的k有

|βk|≤b

(23)

且

(24)

[引理3][2]若條件A、B成立，考慮迭代方法即式(1)(2)滿足下面3個性質：

(i)βk≥0,?k≥0

(ii) 步長αk由式(3)(4)得到，搜索方向dk滿足充分下降條件即式(20)和Zoutendijk條件即式(21)。

(iii) 性質(*)成立，則有

(25)

接下來，證明MHCG方法的全局收斂性。先給出目標函數(shù)f(x)是一致凸函數(shù)的等價定義。

等價定義[7]：f(x)是一個一致凸函數(shù)。如果存在一個常數(shù)μ>0，使得

?x,y∈Ω

(26)

由一致凸函數(shù)的等價定義，可得

由假設B(梯度函數(shù)g是Lipschitz連續(xù)的)和式(19)，可得

由式(4)，可得

因為θk∈[0,1]，則有

(27)

(28)

3 計算效果比較

Hager和Zhang在2005年提出了一個具有充分下降性的共軛梯度方法[7]，簡稱HZ方法。其參數(shù)如下：

截斷形式：

Dai和Kou在2013年提出了一個共軛參數(shù)[8]：

截斷形式：

采用以下方式來比較3種共軛梯度方法的有效性。

首先，定義如下比率。

其中：Ncpu,i(EM(j))表示方法j解第i個問題所用的CPU時間；Ncpu,i(EM(1))表示第1個方法解第i個問題所用的CPU時間。

當?shù)?個方法能解問題i0，而第j0個方法不能解問題i0時，

ri0(EM(j0))=max{ri0(EM(j0)):(i0,j0)?P1}，

其中，S1={{i0,j0}:方法j0能解決問題i}。

當?shù)?個方法不能解問題i0，而第j0個方法能解問題i0時，ri0(EM(j0))=min{ri0(EM(j0)):(i0,j0)?P1}。

當?shù)?個方法和第j0個方法都不能解問題i0時，ri0(EM(j0))=1。

用這些比率的幾何平均數(shù)作為算法的最終比值，即

其中：P是測試問題的集合；|P|是測試問題集中測試問題的個數(shù)。顯然，比值越小，算法的數(shù)值計算效果越好。

其次，采用文獻[9]提供的方式，繪制各方法的性能曲線，以直觀比較各方法的計算效果。

計算結果見表1。其中，NI表示方法的迭代次數(shù)，NF表示函數(shù)值計算次數(shù)，NG表示梯度值計算次數(shù)，T表示所用的CPU時間。以HZ+方法的計算用時、迭代次數(shù)、函數(shù)值計算次數(shù)和梯度值計算次數(shù)為基準，將其單位化，均用1表示。

表1 測試結果比較

圖1至圖4展示了 HZ+、DK+ 和MHCG這3種方法在解決測試問題時表現(xiàn)出的性能差異。在計算時間上，MHCG方法的計算用時最少，所以MHCG方法優(yōu)于 HZ+、DK+方法。

圖1 計算用時比較

圖2 函數(shù)迭代次數(shù)比較

圖3 函數(shù)計算次數(shù)比較

4 結 語

通過對HCG方法逼近一種新的帶參數(shù)的三項共軛梯度法(EZZL方法)，采用最小二乘的思想，通過極小化混合的方法和充分下降的三項共軛梯度法的搜索方向之間的距離之差，得到新的混合參數(shù)θk。從理論上證明了修正后的HCG方法(即MHCG方法)在Wolfe線搜索下滿足充分下降性，且對一致凸函數(shù)全局收斂。運用HZ+、DK+方法和MHCG方法計算了測試函數(shù)庫中的59個問題，比較其計算性能差異。結果表明，MHCG方法在計算時間上優(yōu)于 HZ+、DK+方法。

圖4 梯度計算次數(shù)比較