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

王松華, 夏 師, 黎 勇

(百色學院 數學與統計學院, 廣西 百色533000)

0 引 言

考慮如下無約束優化問題：

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

(1)

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

xk+1=xk+αkdk,

(2)

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

(3)

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

(4)

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

(5)

(6)

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

(7)

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

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

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

(8)

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

1 算法及其性質

(9)

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

取初始點x0∈n, 常數令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)

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

證畢.

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

2 MHZ算法收斂性分析

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

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

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

(14)

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

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

(15)

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

整理得

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

(16)

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

即

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

(17)

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

整理得

(18)

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

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

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

(19)

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

(20)

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

(21)

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

由式(19), 得

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

3 數值實驗

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

(23)

(24)

(25)

其中yk=gk+1-gk.

表1 測試函數名稱

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

表2 4種算法的數值實驗結果

續表2

續表2

續表2

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

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

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