段復建, 楊沖, 李向利

(桂林電子科技大學數(shù)學與計算科學學院, 廣西 桂林 541004)

1.引言

對于無約束優(yōu)化問題

其中f: Rn →R是連續(xù)可微函數(shù).g(x)是f(x)的梯度函數(shù), 即g(x) =?f(x).共軛梯度(CG)法是求解(1.1)常用的迭代方法之一, 具有算法簡單, 儲存需求低等優(yōu)點.給定初始點x0∈Rn, 共軛梯度算法迭代產生點列{xk}如下

其中步長αk ＞0,dk是搜索方向, 且

其中gk=?f(xk),βk是共軛參數(shù).

步長αk由線搜索確定.Wolfe非精確線搜索是最常用的線搜索之一, 它要求αk滿足

其中0＜δ ＜σ ＜1.在共軛梯度法的收斂性分析和數(shù)值實現(xiàn)中, 步長αk通常也由強Wolfe線搜索計算, 此時步長αk要滿足式(1.4)和

根據(jù)搜索方向dk的迭代格式(1.3)可以看出, 共軛參數(shù)βk的不同選取對應不同的共軛梯度法, 經典的βk公式包括Hestenes-Stiefel(HS)[1], Fletcher-Reeves(FR)[2], Polak-Ribière-Polyak(PRP)[3-4]和Dai-Yuan(DY)[5], 它們的計算公式分別為

其中‖·‖表示Euclidean范數(shù).

隨著共軛梯度法不斷地深入研究, 2001年, 基于標準的共軛條件= 0, 并結合擬牛頓法的思想, DAI和LIAO[6]提出一個新的共軛條件

其中yk=gk+1-gk, 參數(shù)t ＞0.由式(1.3)和(1.6)得到共軛參數(shù)

Hager和ZHANG[7]指出參數(shù)t的不同選擇, 數(shù)值結果有較大差異.文[7]中共軛參數(shù)形式為

Babaie-Kafaki和Ghanbari[8]將DL方法的搜索方向轉化成如下形式

其中

同時, 文[8]指出在迭代過程中矩陣條件數(shù)會影響數(shù)值穩(wěn)定性, 并得到矩陣Qk+1的一個譜條件數(shù)上界

并且有

2018年, 文[9]借助式(1.10), (1.11)和(1.12), 提出了關于參數(shù)t的兩種不同選取方式

2020年, 文[10]提出了參數(shù)t另一種自適應形式

2.一個自適應DL共軛梯度算法

本節(jié), 在文[8-10]的基礎上, 提出一個關于參數(shù)t的自適應形式

其中θ ＞0是一個變化實參數(shù).將式(2.1)代入到式(1.11)和(1.12)得到

將式(2.2)和(2.3)代入到式(1.10), 于是有

令

為了使cond(Qk+1)的上界盡可能小, 求得h(θ)的極小值點

由式(2.1)和(2.4), 參數(shù)t選取如下

類似文[11]中的修正方法, 由式(1.7)和(2.5)得到共軛參數(shù)

根據(jù)上述共軛參數(shù)βk的選取, 進而確定搜索方向dk.在強Wolfe線搜索條件下, 提出一種自適應DL共軛梯度算法.

算法2.1自適應DL共軛梯度算法(NADL)

步0 給定初始點x0∈Rn, 參數(shù)ε ＞0, 0＜δ ＜σ ＜1.令k=0,d0=-g0;

步1 若‖gk‖∞＜ε, 則算法終止; 否則, 進行步2;

步2 由強Wolfe條件(1.4)和(1.5)確定步長αk;

步3 計算xk+1=xk+αkdk,gk+1=?f(xk+1);

步4 由式(2.6)和(1.3)分別計算共軛參數(shù)βk和搜索方向dk;

步5 令k:=k+1, 并返回步1.

在共軛梯度法中, 搜索方向dk的下降性具有重要意義.因此, 下面討論算法2.1中搜索方向dk的下降性.

定義對稱矩陣

當

對稱矩陣Ak+1的最小特征值

此時對稱矩陣Ak+1是正定的.因此, 由式(2.7)有

從而搜索方向dk滿足下降條件.

對于本文提出的參數(shù)tk4, 容易驗證其滿足關系式(2.8), 從而說明式(1.3)和(2.6)所確定的搜索方向dk對于充分下降條件成立, 即存在一個常數(shù)c ＞0, 有

3.收斂性分析

首先回顧一致凸函數(shù)的定義.

定義3.1[13]設S ?Rn是非空開凸集,φ:S →R是一致凸函數(shù), 即存在一個常數(shù)μ ＞0, 有

基于定義3.1,φ是一致凸函數(shù)當且僅當

在本節(jié), 當目標函數(shù)f(x)是一致凸函數(shù), 在如下假設條件下, 證得算法2.1具有全局收斂性.

假設3.11)f(x)在水平集Ω={x ∈Rn|f(x)≤f(x0)}上有下界, 即存在常數(shù)B ＞0, 有

2)f(x)在水平集Ω的某鄰域N內連續(xù)可微, 且g(x)滿足Lipschitz條件, 即存在常數(shù)L ＞0,使得

基于假設3.1, 則存在一個常數(shù)γ ＞0, 使得

為了證得算法2.1具有全局收斂性, 在假設3.1的前提下, 有如下引理.

引理3.1[14]目標函數(shù)f(x)滿足假設3.1, 共軛梯度法由式(1.2)和(1.3)迭代計算, 搜索方向dk是下降方向, 步長αk由強Wolfe條件(1.4)和(1.5)確定, 若有

則

定理3.1目標函數(shù)f(x)是一致凸函數(shù), 且滿足假設3.1, 在算法2.1中, 共軛參數(shù)βk由式(2.6)計算, 搜索方向dk由(1.3)確定, 步長αk由強Wolfe條件(1.4)和(1.5)確定, 則有

證目標函數(shù)f(x)是一致凸函數(shù), 由式(3.1)可得, 存在一常數(shù)μ ＞0, 有

由式(3.4)和(3.2), 可以得到

由式(1.3), (2.6), (3.3), (3.4)和(3.5)得到

于是證得搜索方向dk有上界, 從而

成立, 由引理3.1可得

4.數(shù)值試驗

在本節(jié), 將文[7]提出的算法記為HZDL; 文[9]中參數(shù)選取式(1.13)中的tk2時, 算法記為ADL6.為了檢驗算法2.1(NADL)的數(shù)值效果, 將算法HZDL, 算法ADL6和算法NADL在完全相同的強Wolfe線搜索下, 選取文[15]中的部分測試函數(shù)進行進行對比試驗.所有算法程序都是用Matlab R2016a在CPU 3.20 GHz, RAM 4.0 GB, 操作系統(tǒng)為Windows 10的個人計算機上進行測試.參數(shù)選取為δ= 1e-4,σ= 0.8,ε= 1e-6, 終止條件為‖gk‖∞＜ε(1+|f(xk)|).數(shù)值結果見表4.1, 其中N表示測試函數(shù)序號, Function表示測試函數(shù)名稱, NI表示迭代次數(shù),FE表示目標函數(shù)值計算次數(shù), GE表示目標函數(shù)的梯度計算次數(shù), TCPU表示迭代時間(秒),NaN表示運行無結果.

表4.1 算法HZDL、算法ADL6和算法NADL的數(shù)值結果

根據(jù)表4.1中的數(shù)值結果分析, 除測試函數(shù)SING和SINGX, 我們提出的算法NADL對于其他測試函數(shù)是可行的; 對于測試函數(shù)ROSE, FROTH, BARD, BD, OSB2, ROSEX, PEN2,BV, IE以及TRID, 從迭代次數(shù), 函數(shù)值計算次數(shù), 梯度計算次數(shù)和迭代時間四個維度對比分析, 算法NADL明顯優(yōu)于另外兩種算法.利用Dolan和Mor[16]提出的性能曲線, 圖4.1和圖4.2分別針對不同測試函數(shù)求解的迭代次數(shù), 目標函數(shù)值與梯度值的總計算次數(shù)直觀分析算法的效果.從圖4.1和圖4.2可以直觀看出, 算法NADL在總體的計算性能上是優(yōu)于算法HZDL和算法ADL6.

圖4.1 基于迭代次數(shù)的性能概況

圖4.2 基于函數(shù)值和梯度值的總計算次數(shù)的性能概況