基于最小二乘修正的混合HS和DY共軛梯度法

陳 貞 晶

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

共軛梯度法是求解大規(guī)模無約束優(yōu)化問題的最有效的方法之一，具有所需存儲(chǔ)量小、強(qiáng)收斂性和計(jì)算方便等優(yōu)點(diǎn)。比如考慮無約束優(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)是目標(biāo)函數(shù)f(x)的梯度，gk+1=▽f(xk+1)；βk是共軛梯度參數(shù)，簡稱CG參數(shù)。不同的βk值，對(duì)應(yīng)不同的共軛梯度方法。

常用的線搜索有很多，我們在這里只考慮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”)方法都是經(jīng)典的共軛梯度方法，其參數(shù)[1]如下：

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

1 HCG方法的修正

1.1 HCG方法

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

其中

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

HCG方法的計(jì)算效果不是很好，不如經(jīng)典的HS方法。

1.2 ZZL方法

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

(5)

其中，三項(xiàng)共軛方向如下所示：

(6)

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

?k≥0

(7)

(8)

對(duì)CG參數(shù)進(jìn)行非負(fù)限制，得

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

1.3 EZZL方法

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

(9)

所以

(10)

其中

?k≥0

(11)

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

η∈(0,1]

(12)

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

1.4 HCGQN方法

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

其搜索方向如下：

(13)

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

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

其中

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

(14)

(15)

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

1.5 MHCG方法

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

θk∈[0,1]

(16)

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

(17)

所以有

(18)

MHCG方法的計(jì)算步驟如下：

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

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

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

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

Step6: 令k:=k+1，且轉(zhuǎn)入Step2。

2 MHCG方法的收斂性

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

2.1 基本假設(shè)

對(duì)目標(biāo)函數(shù)進(jìn)行以下基本假設(shè)[2]。

(19)

2.2 引理

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

(20)

當(dāng)k≥1時(shí)

因此，有

(21)

由引理1，可得

2.3 收斂性證明

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

性質(zhì)(*)：考慮由式(1)(2)產(chǎn)生的共軛梯度法MHCG，假設(shè)

(22)

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

|βk|≤b

(23)

且

(24)

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

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

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

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

(25)

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

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

?x,y∈Ω

(26)

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

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

由式(4)，可得

因?yàn)棣萲∈[0,1]，則有

(27)

(28)

3 計(jì)算效果比較

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

截?cái)嘈问剑?/p>

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

截?cái)嘈问剑?/p>

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

首先，定義如下比率。

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

當(dāng)?shù)?個(gè)方法能解問題i0，而第j0個(gè)方法不能解問題i0時(shí)，

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

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

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

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

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

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

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

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

表1 測試結(jié)果比較

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

圖1 計(jì)算用時(shí)比較

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

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

4 結(jié) 語

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

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