一類修正Hager-Zhang共軛梯度法的收斂性及其數(shù)值實驗

王松華, 夏 師, 黎 勇

(百色學(xué)院 數(shù)學(xué)與統(tǒng)計學(xué)院, 廣西 百色533000)

0 引 言

考慮如下無約束優(yōu)化問題：

min{f(x)|x∈n},

(1)

其中：f:n→二次連續(xù)可微.非線性共軛梯度法是求解大規(guī)模無約束優(yōu)化問題的一類重要方法, 其迭代公式為

xk+1=xk+αkdk,

(2)

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

(3)

式中αk為步長因子,dk為搜索方向,gk為梯度函數(shù)f(xk)的簡記,βk為共軛參數(shù).經(jīng)典的共軛梯度法有FR(Fletcher-Reeves),PRP(Polak-Ribière-Polyak),HS(Hestenes-Stiefel),CD(Conjugate-Descent),DY(Dai-Yuan)和LS(Liu-Storey)算法等[1]. 研究表明,類共軛參數(shù)公式的分子為‖gk‖2(‖‖為歐氏范數(shù)), 這類算法在弱Wolfe-Powell線搜索條件下對一般函數(shù)全局收斂, 但數(shù)值結(jié)果并不理想； 而類共軛參數(shù)公式的分子為這類算法具有自動重開始的性能, 可有效避免連續(xù)產(chǎn)生小步長, 數(shù)值結(jié)果較好, 但在弱Wolfe-Powell線搜索下算法的下降性不能保證.

(4)

基于充分下降性的條件, Hager等[6]在自調(diào)比BFGS方法(擬牛頓法)的基礎(chǔ)上提出了一種修正HS共軛梯度法, 稱為HZ(Hager-Zhang)共軛梯度法, 其共軛參數(shù)公式為

(5)

(6)

其中η>0.本文簡稱該方法為HZb算法. HZb算法具有穩(wěn)定和有效的數(shù)值性能, 是目前數(shù)值結(jié)果性能最好的算法之一[7]. 之后, Hager等[8]又將HZ算法進(jìn)行推廣, 得到了與文獻(xiàn)[2]方法完全相似的理論結(jié)果, 本文簡稱為HZp算法, 其共軛參數(shù)公式為

(7)

文獻(xiàn)[9-13]基于搜索方向滿足充分下降條件的理論方法, 給出了HZ算法的推廣及應(yīng)用.

文獻(xiàn)[14-16]對線搜索型非線性共軛梯度法的研究表明, 搜索方向具有信賴域性質(zhì), 對算法的全局收斂性分析有積極作用, 即搜索方向滿足下列條件：

‖dk‖≤c0‖gk‖, ?k∈,c0>0.

(8)

文獻(xiàn)[6,8-13]中的HZ算法及其推廣算法均滿足充分下降性條件, 但沒有信賴域性質(zhì). Yuan等[16]研究了一類新型非凸函數(shù)的共軛梯度法簇, 構(gòu)建了一組搜索方向公式自動滿足條件(7),(8), 不僅有良好的收斂性質(zhì), 而且初步數(shù)值實驗結(jié)果表明, 該算法比經(jīng)典PRP,HS,CD,FR,LS和DY等算法性能更好. 文獻(xiàn)[16]還給出了一種修正HZ搜索方向公式, 但未建立相應(yīng)的算法. 受文獻(xiàn)[6,8,14-16]工作的啟發(fā), 本文提出一類針對大規(guī)模無約束優(yōu)化問題的修正HZ共軛梯度法, 并討論新算法的全局收斂性和R-線性收斂速度, 給出其數(shù)值性能分析.

1 算法及其性質(zhì)

(9)

本文采用弱Wolfe-Powell線搜索[17], 并聯(lián)合搜索方向式(9), 構(gòu)建新的修正HZ算法, 簡稱為MHZ算法, 其步驟如下：

取初始點x0∈n, 常數(shù)令k∶=0.

1) 如果‖gk‖≤ε, 則停止;

2) 采用弱Wolfe-Powell(WWP)線搜索計算步長αk, WWP線搜索公式為

(10)

(11)

3) 計算xk+1=xk+αkdk;

4) 如果‖gk+1‖≤ε, 則停止;

6) 計算修改后的搜索方向

7) 令k=k+1, 返回步驟2).

引理1如果搜索方向由MHZ算法給出, 則下式成立：

(12)

證畢.

引理2如果搜索方向由MHZ算法給出, 則下式成立：

‖dk+1‖≤(1+ρ0)‖gk+1‖, 0<ρ0<1.

(13)

證明： 當(dāng)k=0時, 式(13)顯然成立.當(dāng)k≥1時, 對式(9)兩邊取范數(shù), 可得

證畢.

引理1表明, MHZ算法的搜索方向不依賴任何線搜索, 滿足充分下降性; 引理2表明, MHZ算法的搜索方向具有信賴域性質(zhì).

2 MHZ算法收斂性分析

假設(shè)11) 目標(biāo)函數(shù)f(x)二次連續(xù)可微, 有下界； 定義的水平集L0={x|f(x)≤f(x0)}有界.

2) 目標(biāo)函數(shù)f(x)的梯度gk是Lipschitz連續(xù)的, 即存在常數(shù)L>0, 使得下式成立：

‖g(x)-g(y)‖≤L‖x-y‖, ?x,y∈n.

(14)

結(jié)合引理1、 引理2和假設(shè)1, 下面證明MHZ算法是全局收斂的, 所用方法類似文獻(xiàn)[16]中定理3.

定理1如果假設(shè)1成立, 序列{xk,dk,αk,gk}由MHZ算法給出, 則下式成立：

(15)

證明： 由式(10),(12), 可得

整理得

δαk(1-ρ0)‖gk‖2≤f(xk)-f(xk+1),

(16)

對不等式(16)從k=0到∞累加求和, 并結(jié)合假設(shè)1中1), 可得

即

αk‖gk‖2→0,k→∞.

(17)

由式(11),(13),(14), 可得

整理得

(18)

假設(shè)2若函數(shù)f(x)為二次連續(xù)可微一致凸函數(shù), 則對?x,d∈n, 存在SM≥sN>0, 使得下式成立:

sN‖d‖2≤dT2f(x)d≤SM‖d‖2,

假設(shè)1和假設(shè)2表明, 問題(1)存在唯一解x*, 對?x∈n, 如下兩個不等式成立：

(19)

sN‖x-x*‖≤‖g(xk)‖≤SM‖x-x*‖.

(20)

定理2若假設(shè)2成立,x*是問題(1)的唯一解, 則存在常數(shù)a>0,l0∈(0,1), 使得下式成立:

(21)

證明： 由式(4),(10), 再聯(lián)合式(19),(20), 可得

由式(19), 得

定理2表明, MHZ算法對一致凸函數(shù)具有R-線性收斂速度.

3 數(shù)值實驗

為檢驗MHZ算法的有效性, 本文采用文獻(xiàn)[18]的40個非線性函數(shù)進(jìn)行數(shù)值實驗, 函數(shù)名稱列于表1. 將MHZ算法與HZ算法、 HZb算法、 HZp算法進(jìn)行對比分析. 數(shù)值實驗中, 對應(yīng)的HZ算法、 HZb算法和HZp算法, 分別在MHZ算法中, 采用下式替換MHZ算法的步驟5)和步驟6)計算搜索方向dk+1, 其余步驟不變, 3類對比算法的搜索方向dk+1公式分別為

(23)

(24)

(25)

其中yk=gk+1-gk.

表1 測試函數(shù)名稱

數(shù)值實驗采用MATLAB編寫程序并運行. 計算機(jī)配置： Windows 10操作系統(tǒng), Intel(R)Xeon(R)CPU, E5507 @2.27 GHz, 內(nèi)存4.00 GB； 終止條件： ‖gk‖≤10-6或者迭代次數(shù)NI<800； 4種算法相應(yīng)的參數(shù)設(shè)置：δ=0.22,σ=0.93,ρ0=0.18,η=3,θ=1,ε=10-6； 維數(shù)為1 500,4 500,9 000,12 000； 主要針對4種算法的迭代次數(shù)NI、 函數(shù)值的計算次數(shù)NFG和實驗運行所需時間CPU這3個常用指標(biāo)進(jìn)行測試. 4種算法的數(shù)值實驗結(jié)果列于表2.

表2 4種算法的數(shù)值實驗結(jié)果

續(xù)表2

續(xù)表2

續(xù)表2

由表2可見, 4種算法均能解決所給定的測試問題, MHZ算法比HZ算法、 HZb算法和HZp算法更有效. 下面采用Dolan等[19]的評價準(zhǔn)則, 對4種算法進(jìn)行綜合性能評估. 該評價準(zhǔn)則為： 曲線越靠上所對應(yīng)的算法越穩(wěn)定, 效果越好. 4種算法的迭代次數(shù)、函數(shù)值計算次數(shù)和CPU運行時間的性能評估結(jié)果如圖1所示. 在計算精度一致的條件下, 由圖1(A),(B)可見, MHZ算法最優(yōu), 其次為HZb算法和HZp算法, 這3種算法均比HZ算法好, 充分說明了這4類算法的性能發(fā)展趨勢. 由圖1(C)可見, 4種算法CPU運行時間較接近, MHZ算法總體結(jié)果較好, 這可能是因為本文實驗相關(guān)參數(shù)的取值對CPU運行時間有一定影響.

圖1 4種算法的迭代次數(shù)(A)、 函數(shù)值計算次數(shù)(B)和CPU運行時間(C)性能評估Fig.1 Performance evaluation of iteration numbers (A), calculation numbers of function value (B) and CPU runtime (C) for four algorithms

綜上所述, 本文基于文獻(xiàn)[16]的搜索方向, 利用弱Wolfe-Powell線搜索構(gòu)建了MHZ算法, 該算法具有如下優(yōu)點： 1) 搜索方向具有充分下降性和信賴域性質(zhì)； 2) 在常規(guī)假設(shè)條件下, 算法不僅對一般函數(shù)全局收斂, 在所給的條件下對一致凸函數(shù)具有R-線性收斂速度； 3) 數(shù)值實驗結(jié)果表明, 在求解無約束優(yōu)化問題上, MHZ算法比MZ算法、 HZb算法和HZp算法更有效.