幾種混合型共軛梯度法的數(shù)值性能

黃元元, 楊穎珂

(河南科技大學(xué) 數(shù)學(xué)與統(tǒng)計學(xué)院, 河南 洛陽 471023)

共軛梯度法是求解無約束優(yōu)化問題

minf(x),x∈n,

(1)

的有效方法之一, 最早由Hestenes等[1]提出用于求解線性方程組, 之后被Fletcher等[2]推廣到求解非線性無約束優(yōu)化問題(1)上. 求解非線性無約束優(yōu)化問題(1)的經(jīng)典共軛梯度法, 除HS共軛梯度法和FR共軛梯度法外, 還有PRP共軛梯度法[3-4]、 CD共軛梯度法[5]、 LS共軛梯度法[6]、 DY共軛梯度法[7]和DL共軛梯度法[8]等. 以這些經(jīng)典的共軛梯度法為基礎(chǔ), 目前已提出了多種混合型共軛梯度法, 如具有充分下降性質(zhì)的共軛梯度法、 混合型共軛梯度法、 三項共軛梯度法和預(yù)條件共軛梯度法等.

在多種共軛梯度法中, 具有充分下降性質(zhì)的混合型共軛梯度法通常具有較好的數(shù)值性能, 因此備受關(guān)注. Hager等[9]基于HS算法提出的CG_DESCENT算法因數(shù)值性能較好而被廣泛應(yīng)用. Cheng等[10]利用Gram-Schmidt正交化策略, 設(shè)計了一種滿足充分下降性質(zhì)的共軛梯度法, 也具有較好的數(shù)值性能. 繼Andrei[11-13]提出了基于經(jīng)典共軛梯度算法凸組合, 設(shè)計混合型共軛梯度法的概念后, Babaie-Kafaki等[14]提出了一種基于DY和HS算法某種凸組合形式的混合型共軛梯度算法, 指出該類混合型共軛梯度算法的數(shù)值性能極大程度上依賴于組合參數(shù)的選取, 并給出了一個自適應(yīng)的組合參數(shù). 為提高該類算法的數(shù)值效果, Livieris等[15]通過極小化共軛梯度方向和有限記憶BFGS方向之間的距離, 借助擬牛頓思想, 設(shè)計了一種基于DY和HS+的改進的HCG+共軛梯度法, 該方法滿足充分下降條件且在Wolfe線搜索下全局收斂.

本文在上述已有工作的基礎(chǔ)上, 設(shè)計一類收斂的混合型共軛梯度法, 并借助CUTEst測試環(huán)境, 對該類混合型共軛梯度法的有效性進行驗證, 同時與文獻[15]提出的改進算法進行數(shù)值性能比較, 分析這些算法在弱Wolfe線搜索下的數(shù)值行為.

1 算法描述

經(jīng)典共軛梯度法的算法框架如下： 對任意給定的初始點x0∈n, 迭代序列{xk}由

xk+1=xk+αkdk

(2)

產(chǎn)生, 步長αk可由弱Wolfe一維線搜索：

(3)

(4)

得到, 其中: 0<σ1<σ2<1；dk為搜索方向, 且

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

這里gk+1=f(xk+1),βk為迭代參數(shù), 不同參數(shù)βk對應(yīng)不同的共軛梯度法.經(jīng)典的共軛梯度法有FR[2],DY[7],PRP[3-4]和HS[10]等, 所對應(yīng)的參數(shù)βk分別定義為

FR和DY共軛梯度法通常具有較好的全局收斂性質(zhì), 但數(shù)值結(jié)果不理想； PRP和HS共軛梯度法數(shù)值結(jié)果比前兩種更優(yōu)越, 但理論上不能完全保證收斂性.

共軛梯度法的充分下降條件為

(5)

Hager等[9]提出的CG_DESCENT算法滿足該充分下降條件(5), 且c=7/8, 其參數(shù)βk是基于HS算法給出的, 公式為

(6)

其中yk=gk+1-gk.Cheng等[10]提出的正交化共軛梯度算法, 其搜索方向dk由

(7)

產(chǎn)生, 這類搜索方向滿足充分下降性質(zhì)(5), 且c=1.式(7)中不同的參數(shù)βk對應(yīng)不同的正交化共軛梯度法.

本文在保證算法全局收斂的前提下, 設(shè)計正交化的混合型共軛梯度算法, 算法描述如下.

算法1正交化的混合型共軛梯度算法.

步驟1) 選取初始點x0∈n, 0<σ1<σ2<1,ε>0， 令k=0；

步驟2) 若‖gk‖≤ε, 則停止； 否則, 利用弱Wolfe線搜索式(3)和式(4)確定步長αk；

步驟3) 由式(2)計算新的迭代點xk+1；

步驟4) 由式(7)計算新的下降方向dk+1, 令k∶=k+1, 并轉(zhuǎn)步驟2).

算法1中的參數(shù)βk不再采用經(jīng)典共軛梯度法中βk的定義, 本文以經(jīng)典算法中的參數(shù)βk為基礎(chǔ), 設(shè)計4種混合型的迭代參數(shù), 對應(yīng)的4個正交化共軛梯度法的收斂性分析證明類似于文獻[10]中的理論證明, 故本文略.下面給出基于算法1框架的4個正交化共軛梯度法.

1) 基于ZL方法的共軛梯度法(HCG_ZL).

Zhang和Li[16]給出了CG_DESCENT方法的一般形式, 即定義參數(shù)βk為

(8)

其特點是分母有正的下界.若式(7)中的參數(shù)βk采用式(8)進行迭代計算, 則算法1稱為基于ZL方法的共軛梯度法, 簡記為HCG_ZL算法.

2) 基于PRP和HS的混合型共軛梯度法(HCG_PRPHS).

為體現(xiàn)經(jīng)典的PRP和HS算法的數(shù)值優(yōu)勢, 本文給出基于PRP和HS算法特點的參數(shù)βk, 定義為

其中ζ>0.若式(7)中的參數(shù)βk采用式(9)進行迭代計算, 則算法1稱為基于PRP和HS的混合型共軛梯度法, 簡記為HCG_PRPHS算法.

3) 基于DY和FR的混合型共軛梯度法(HCG_DYFR).

作為對比組, 基于DY和FR的算法定義參數(shù)βk為

此時的算法1稱為基于DY和FR的混合型共軛梯度法, 簡記為HCG_DYFR算法.

4) 基于DY和HS的混合型共軛梯度法(HCG_DYHS).

Babaie-Kafaki等[14]基于凸組合概念, 提出了HCG+混合型共軛梯度法, 其參數(shù)βk定義為

(10)

此時的算法1為自適應(yīng)下降混合型共軛梯度法, 即文獻[15]中的算法, 簡記為ADHCG+算法.

借鑒HCG_PRPHS算法和ADHCG+算法的思想, 以凸組合的形式設(shè)計基于DY和HS的混合型共軛梯度法, 簡記為HCG_DYHS算法, 為保證算法的充分下降條件, 定義參數(shù)βk為

其中vk=λkgk+1+(1-λk)yk,λk的選取與ADHCG+算法中λk的選取方式一致.

2 數(shù)值實驗

下面從數(shù)值計算的角度研究HCG_ZL算法、 HCG_PRPHS算法、 HCG_DYFR算法和HCG_DYHS算法在弱Wolfe線搜索下的數(shù)值性能并與ADHCG+算法進行比較. 所有算法均在操作系統(tǒng)為Linux Ubuntu 12.04, 處理器為Intel(R) Xeon(R) i5-500U 2.40 GHz, 內(nèi)存為8.00 GB的筆記本電腦上運行.

為使實驗結(jié)果更客觀, 從CUTEst測試環(huán)境中提取138個無約束優(yōu)化問題對本文算法的數(shù)值性能進行比較. 在算法執(zhí)行過程中, 選取終止準(zhǔn)則為

‖gk‖∞≤max{ε,ε(1+fk)},

其中ε=10-6且fk=f(xk).弱Wolfe線搜索(3)-(4)中的參數(shù)σ1=0.1,σ2=0.9, 初始步長α0的選取準(zhǔn)則參見文獻[9].不同算法的數(shù)值結(jié)果列于表1.

表1 算法的數(shù)值結(jié)果(部分)

由于算法求解CUTEst測試問題的數(shù)據(jù)量較大, 因此表1中僅列出部分?jǐn)?shù)據(jù), 以展示所得到的數(shù)據(jù)類型, 其中: Name表示測試問題在CUTEst測試環(huán)境中的名稱,n表示問題的維數(shù)； Iter表示算法終止時的迭代次數(shù)； Nf表示算法達到終止準(zhǔn)則時函數(shù)值被計算的次數(shù)； Ng表示算法達到終止準(zhǔn)則時, 函數(shù)的梯度值被調(diào)用的次數(shù)；tCPU表示算法運行的CPU時間.

將算法求解CUTEst測試問題, 達到終止準(zhǔn)則時的迭代次數(shù), 函數(shù)值被計算的次數(shù), 函數(shù)梯度值被調(diào)用的次數(shù)和算法運行的CPU時間作為評價指標(biāo), 利用Dolan等[17]提出的比較準(zhǔn)則, 對算法分別就這4個評價指標(biāo)的數(shù)據(jù)進行比較, 結(jié)果分別如圖1～圖4所示. 圖1～圖4中曲線表示算法求解測試問題效率的分布函數(shù), 橫軸表示算法求解問題的效率閾值, 縱軸表示在即定閾值下, 算法求解出的問題占總問題量的比例. 曲線越靠上, 該曲線所表示的算法越穩(wěn)定, 曲線越靠左, 相應(yīng)算法求解問題的效率越高.

圖1 不同算法基于迭代次數(shù)的比較Fig.1 Comparison of different algorithms based on number of iterations

圖2 不同算法基于函數(shù)值計算次數(shù)的比較Fig.2 Comparison of different algorithms based on function value calculation times

圖3 不同算法基于梯度值計算次數(shù)的比較Fig.3 Comparison of different algorithms based on gradient value calculation times

圖4 不同算法基于CPU運行時間的比較Fig.4 Comparison of different algorithms based on CPU running time

由圖1～圖4可見, 5種算法都能有效求解CUTEst測試環(huán)境中的無約束優(yōu)化問題, HCG_DYFR算法的數(shù)值性能相對較差, 在效率和穩(wěn)定性上均不及其余4種算法, 這是由經(jīng)典的DY和FR算法本身所具有的數(shù)值特點決定的. 其余4種算法均可以認(rèn)為是基于HS算法的正交型共軛梯度法, 繼承了經(jīng)典的HS算法良好的數(shù)值特性, 但數(shù)值性能又有所不同. HCG_DYHS算法和ADHCG+算法均是基于經(jīng)典的DY算法和HS算法進行設(shè)計的混合型算法, 雖然設(shè)計思路不同, 但數(shù)值性能較相似, 從數(shù)值效果上看, 強于DYFR類算法, 但無論從函數(shù)值計算次數(shù)還是從梯度計算次數(shù)上看, 效率均略遜于HCG_ZL算法和HCG_PRPHS算法. HCG_PRPHS算法和HCG_ZL算法具有較強的可比性, 不同的是HCG_PRPHS算法同時凸顯了經(jīng)典的PRP算法和HS算法的數(shù)值性能優(yōu)勢.

綜上所述, 本文通過138個CUTEst測試問題說明了基于PRP和HS的混合型正交共軛梯度法在運行效率和穩(wěn)定性方面均具有優(yōu)勢, 為實際工程應(yīng)用中共軛梯度法的選擇提供了借鑒方向.