楊 雪，李 鋒

(云南師范大學(xué) 數(shù)學(xué)學(xué)院，云南 昆明 650500)

優(yōu)化問題與我們的工作和生活息息相關(guān)，比如每個公司都需要考慮“在一定成本下，如何使利潤最大化或者損失最小化”的問題，此時，可以利用最優(yōu)化方法去解決類似的實(shí)際優(yōu)化問題．而優(yōu)化問題存在有約束條件和無約束條件兩種情況，也可將其稱之為有約束優(yōu)化和無約束優(yōu)化．在處理實(shí)際問題時，通常會將有約束優(yōu)化問題轉(zhuǎn)變?yōu)闊o約束優(yōu)化問題求解．因此，無約束優(yōu)化一直是優(yōu)化問題的研究重點(diǎn)．對于無約束優(yōu)化問題，若目標(biāo)函數(shù)連續(xù)可微，則可以利用最速下降法、牛頓法、擬牛頓法、共軛梯度法等方法對函數(shù)進(jìn)行求解．這些方法都是利用目標(biāo)函數(shù)的導(dǎo)數(shù)信息，然后采取一定的迭代格式求出目標(biāo)函數(shù)的最優(yōu)值[1]．

在上述方法中，最簡單的方法是最速下降法，但其面對一些復(fù)雜的問題時會受到鋸齒現(xiàn)象的影響導(dǎo)致收斂速度很慢．牛頓法和擬牛頓法的優(yōu)勢是收斂速度快，但由于其需要計算和儲存矩陣且搜索方向的求解復(fù)雜，為大規(guī)模優(yōu)化問題的求解增加了難度[2]．而共軛梯度法在計算時僅需求目標(biāo)函數(shù)的一階導(dǎo)數(shù)，且與最速下降法相比提高了收斂速度，同時又避免了牛頓法對存儲空間的要求和求解Hesse矩陣及其逆矩陣的缺點(diǎn)．基于上述原因，在處理實(shí)際問題時共軛梯度法受到人們的廣泛喜愛．

隨著大數(shù)據(jù)時代的來臨，亟須對海量數(shù)據(jù)進(jìn)行分析應(yīng)用，于是對大規(guī)模優(yōu)化問題的求解提出新的要求．而具有收斂性強(qiáng)，且算法簡單、易操作的共軛梯度法恰恰是大規(guī)模問題的重要求解方法之一[2]．因此，為了處理某些優(yōu)化問題，研究共軛梯度法具有重要意義．

1 共軛梯度法的發(fā)展及其收斂性

1.1 共軛梯度法的發(fā)展

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

min{f(x)|x∈Rn}，

(1)

1952年Hestenes等[3]提出了HS共軛梯度法，該方法不需要求逆矩陣或矩陣分解，而是以迭代的方式求線性方程的解，且結(jié)果具有有限終止性．對于一個線性方程組

Ax=b,x∈Rn,

(2)

其中，A是對稱正定矩陣，且A∈Rm×n,b∈Rm．

在解決了線性方程組的問題之后，如何將該方法推廣到非線性領(lǐng)域值得關(guān)注．于是Fletcher等[4]將HS法的思想運(yùn)用到非線性優(yōu)化問題，并提出了FR法，F(xiàn)R法可先在精確線搜索下求解凸二次函數(shù)最小值問題，之后他們又將其推廣到一般函數(shù)最小值的求解中[1]；1969年P(guān)olak等[5]和Polyak[6]提出了PRP方法，該方法通過對FR方法中βk的改動，改善了FR方法的收斂速度慢的情況；1987年Fletcher[7]在其著作中引入了CD法，即共軛下降法，從而得到了關(guān)于下降方向更好的性質(zhì)；1991年Liu等[8]在PRP方法的基礎(chǔ)上提出了LS法；1999年戴彧虹等[9]提出了在Wolfe線搜索條件下的DY方法；2001年戴彧虹等[10]提了DL法，該方法利用擬牛頓方程及HS方法的共軛性使得新算法在收斂性和下降方向上均有所改善；2004年Yabe等[11]根據(jù)DL方法的思想得到了YT方法．

不同的共軛梯度法區(qū)別在于βk不同，現(xiàn)將以上方法中的βk計算公式歸納如下：

(3)

(4)

(5)

(6)

(7)

1.2 共軛梯度法的收斂性

1.2.1 FR方法

起初對FR方法的收斂性分析工作是在精確線搜索基礎(chǔ)上展開，Zoutendijk[12]給出了精確線搜索下FR方法對一般非凸函數(shù)全局收斂的證明，之后，Powell[13]給出FR方法全局有效性，同時證明了精確線搜索下的FR方法若在某一步產(chǎn)生一個小步長則后面生成的步長也可能很?。虼?，F(xiàn)R方法收斂可能很慢．此外，Powell[13]的分析也對FR方法數(shù)值表現(xiàn)不佳提供了一些依據(jù)．

由于精確線搜索計算量較大，實(shí)際計算通常采用非精確搜索確定迭代步長．1985年，Al-Baali[14]首先分析了FR方法在非精確搜索下的收斂性，且證明當(dāng)參數(shù)滿足0<ρ<σ<1/2;1/2時，F(xiàn)R方法在強(qiáng)Wolfe線搜索下滿足充分下降性及全局收斂性；Liu等[15]繼續(xù)研究了FR方法在強(qiáng)Wolfe線搜索下的收斂性，證明了當(dāng)σ=1/2它也是充分下降且全局收斂的；1996年戴彧虹等[16]給出了FR方法在σ=1/2的強(qiáng)Wolfe線搜索時全局收斂的新證明，并還舉出一個反例證明：當(dāng)σ=1/2時FR方法可能因?yàn)楫a(chǎn)生上升方向而導(dǎo)致算法失??；此外戴彧虹等[17]還提出新的廣義線搜索，并給出FR方法在廣義線搜索下的全局收斂性；之后，戴彧虹等[18]在沒有充分下降條件的情況下建立了FR方法和PRP方法的收斂性．

1.2.2 DY方法

由于前人對FR方法和CD方法的收斂性研究大多停留在精確線搜索或強(qiáng)Wolfe線搜索上，如何在較弱的線搜索條件下提出一種具有全局收斂性的共軛梯度法顯得尤為重要．于是戴彧虹等[9]對原來的方法進(jìn)行深入研究后，提出一種在Wolfe線搜索下能自動保持下降條件且全局收斂的共軛梯度法，并將其稱之為DY方法．之后，戴彧虹[19]分析了DY方法的內(nèi)在性質(zhì)，給出了該方法在遠(yuǎn)離最優(yōu)點(diǎn)時大部分迭代點(diǎn)列都滿足充分下降條件的證明．

1.2.3 PRP方法

(8)

(9)

延續(xù)WYL方法的思想，2007年Yao等[24]將這種方法推廣到HS和LS方法上，并提出新的算法，其形式如下：

(10)

(11)

(12)

2012年Dai等[26]受到文獻(xiàn)[27]提出的新算法能夠產(chǎn)生充分下降條件的啟發(fā)下，對Zhang[25]的NPRP方法進(jìn)行了改進(jìn)，使改進(jìn)后的NPRP方法在下降方向上具有更好的性能，并將該方法稱為DPRP法．因此，DPRP方法和NPRP方法相比較，不僅對任意線搜索具有充分的下降性，而且在Wolfe線搜索或Armijo線搜索下非凸極小化都保持全局收斂性．此外，將這一結(jié)果推廣到NHS方法，并稱為DHS方法．其中：

(13)

(14)

2 共軛梯度法的研究現(xiàn)狀及熱點(diǎn)

目前，對于共軛梯度法的研究主要有兩種思路：一種是直接改進(jìn)共軛參數(shù)βk；另一種是利用混合方法能夠取長補(bǔ)短的特點(diǎn)將不同的方法進(jìn)行混合．眾所周知，證明FR法、DY法和CD法的收斂性時，全局收斂定理只需要滿足Lipschitz假設(shè)，而不需要有界性假設(shè)．這決定了它們雖然計算效果一般，卻具有很好的全局收斂性．另外，由于PRP法、HS法和LS法能夠自動調(diào)節(jié)βk避開干擾步長，具有內(nèi)置重新啟動功能，因此在一般情形下可能不收斂，但是它們卻具有良好的數(shù)值表現(xiàn)．正是因?yàn)榛旌瞎曹椞荻确ň哂薪Y(jié)合兩類方法優(yōu)缺點(diǎn)的特點(diǎn)，所以從混合共軛梯度法的思路出發(fā)構(gòu)造出一種既具有好的收斂性質(zhì)，又具有優(yōu)秀的數(shù)值表現(xiàn)的新算法具有深遠(yuǎn)的意義．

混合共軛梯度法一般是將其他共軛梯度法與經(jīng)典共軛梯度法混合．1990年Touati-Ahmed等[28]首先通過將FR方法和PRP方法投影，引入了混合共軛梯度法．這是對混合共軛梯度法的一次有效嘗試，新方法兼具FR方法和PRP方法的特點(diǎn)，并克服了FR方法數(shù)值表現(xiàn)一般的缺點(diǎn)，其中：

(15)

為擴(kuò)展PRP更新參數(shù)的允許選擇范圍，同時保持全局收斂性，Gilbert等[22]提出：

(16)

該算法的數(shù)值表現(xiàn)雖然比FR方法好，但卻不如PRP方法．由于DY方法具有比FR方法更好的全局收斂性，因此戴彧虹等[9]沿著這種思路給出一種混合DY方法和HS方法的新算法：

(17)

而且其以大量的數(shù)值實(shí)驗(yàn)證明該算法明顯優(yōu)于HS方法和DY方法，特別在面對較為復(fù)雜的問題時數(shù)值表現(xiàn)也比PRP方法好．由于受文獻(xiàn)[22]的啟發(fā)，何曉旭等[29]在2016年提出一種將FR和PRP算法混合的新算法．該算法充分利用二者的優(yōu)勢，下降方向dk由新算法產(chǎn)生且不依賴于任何一種線搜索條件．其中：

(18)

(19)

(20)

為了延續(xù)DPRP法[26]、DY法[9]等多種共軛梯度法的優(yōu)點(diǎn)，韓信等[30]在2017年提出了一種新HZW法，其在發(fā)表的文章中不僅給出了新算法良好的收斂性證明，而且用文獻(xiàn)[31]中的11個測試函數(shù)對它的數(shù)值表現(xiàn)進(jìn)行了驗(yàn)證，其中：

(21)

除此之外，劉玲等[32]在2016年提出了一種新的帶參數(shù)的共軛梯度法，并給出了新算法全局收斂性證明．新算法最大的特點(diǎn)是搜索方向滿足充分下降性卻不依賴任何線搜索，但引入?yún)?shù)的選取會對最后的數(shù)值效果造成一定的影響．其中βk為：

(22)

(23)

與此同時，利用兩種方法的凸組合構(gòu)造新算法的嘗試也在進(jìn)行．Andrei[33]給出了一種新的混合共軛梯度算法，其中：

(24)

對于這種方法，一個必須解決的問題就是凸組合參數(shù)θk確定．在文獻(xiàn)[33]中，作者先假設(shè)搜索方向dk為牛頓方向，據(jù)此得出θk的表達(dá)式為：

(25)

(26)

類似也可以得到dk的表達(dá)式，最終得到的dk在一定條件下為近似牛頓方向．但這種方法的局限性在于不能保證生成的dk一定是下降方法，因此可能導(dǎo)致數(shù)值結(jié)果不穩(wěn)定．除此之外，作者還給出了新算法在一定條件下的收斂性證明以及數(shù)值實(shí)驗(yàn)表現(xiàn)．

Liu等[34]在Andrei[33]的啟發(fā)下，綜合考慮LS方法數(shù)值表現(xiàn)及DY方法的收斂性，提出了基于LS和DY方法凸組合的一種新的混合共軛梯度法，該方法下的搜索方向滿足Dai等[10]提出的D-L共軛條件：

(27)

2019年Mtagulwa等[35]借鑒Alhawarat[36]和文獻(xiàn)[34]的思想，構(gòu)造了NPRP與FR方法的凸組合的新混合共軛梯度法．該方法繼承了PRP、FR和NPRP共軛梯度的特點(diǎn)，并將βk更新為：

(28)

(29)

此外，關(guān)于凸組合的其他混合共軛梯度法還可以參見Djordjevic[37-38]提出的LS和CD方法凸組合的混合共軛梯度法及LS和FR方法凸組合的混合共軛梯度法．

目前，對混合共軛梯度法研究的方法已有很多，但對不同的混合方法而言，其優(yōu)缺點(diǎn)、原理、算法特點(diǎn)以及收斂性特征等仍存在差異．因此對混合共軛梯度法進(jìn)行深入研究仍具有重要意義，在未來研究中爭取探索出更多兼具好的收斂性質(zhì)及良好數(shù)值表現(xiàn)的混合共軛梯度法．

3 共軛梯度法的應(yīng)用

由于共軛梯度法能夠高效、簡潔地處理一些大規(guī)模線性等式和非線性優(yōu)化問題，在處理實(shí)際問題時，其應(yīng)用范圍廣泛，如：圖像復(fù)原、壓縮感知問題和求解大規(guī)模非線性互補(bǔ)問題等．

3.1 共軛梯度法在圖像復(fù)原中的應(yīng)用

圖像是獲取信息的重要方式之一，為高效、快捷、精準(zhǔn)地從圖像中獲取重要信息，對圖像復(fù)原進(jìn)行研究具有重要應(yīng)用價值．圖像復(fù)原的基本任務(wù)是最大限度地保留原始圖像的邊緣信息和去除污染圖像中噪聲及模糊部分．對污染圖像的處理時，要先根據(jù)不同的污染情況建立相應(yīng)的原始圖像和污染圖像的數(shù)學(xué)模型，然后利用污染圖像信息，對建立好的數(shù)學(xué)模型進(jìn)行反解[39]．因此圖像復(fù)原本質(zhì)上可以看成是數(shù)學(xué)中反問題的研究范疇．在得到一個數(shù)學(xué)模型后，可以先對最小化模型進(jìn)行離散處理，然后再利用最優(yōu)化方法對離散后的模型進(jìn)行求解．而離散模型其中的一個子問題需要對大規(guī)模線性方程組進(jìn)行求解，此時就可以利用共軛梯度法來實(shí)現(xiàn)．

2020年Yuan等[40]將最速下降算法和LS方法進(jìn)行凸組合，提出了一種修正的共軛算法．新算法的搜索方向在沒有任何線搜索技術(shù)的情況下，具有充分下降性和信賴域性質(zhì)，在一定的條件及回溯線搜索技術(shù)下建立了全局收斂性[41]．此外，為了改善目標(biāo)函數(shù)值會隨迭代次數(shù)增加而縮減的情況，作者對步長采用了加速系統(tǒng)[42]，并將該算法成功的應(yīng)用到圖像復(fù)原中，而且數(shù)值實(shí)驗(yàn)表明，該算法與其他方法相比具有一定的優(yōu)勢．同年，Cao等[43]提出了一種修正PRP共軛梯度法，由新算法定義的搜索方向具有充分下降性和信賴域特征．由于這兩個特別好的特性，因此能夠更簡單地證明非凸函數(shù)在Armijo線搜索下的全局收斂性．同時作者還用數(shù)值實(shí)驗(yàn)證明了在圖像復(fù)原背景下新算法同PRP方法相比具有較大優(yōu)越性．

3.2 共軛梯度法在壓縮感知中的應(yīng)用

2006年Donoho[44]和Candes等[45]的兩篇突破性的論文使壓縮感知進(jìn)入了大眾視野．隨著現(xiàn)代科學(xué)技術(shù)的迅猛發(fā)展，壓縮感知方法已經(jīng)廣泛應(yīng)用在電子工程、醫(yī)學(xué)、計算機(jī)科學(xué)等領(lǐng)域．它利用一個高度不完備的線性測量對稀疏信號進(jìn)行采樣，這時獲取的是被“壓縮”后的數(shù)據(jù)．然后，通過使用高效的方法對“壓縮”的數(shù)據(jù)進(jìn)行重構(gòu)就能恢復(fù)原稀疏信號[46]．在進(jìn)行第2步重構(gòu)時，就可利用共軛梯度法恢復(fù)原始信號．

在處理信號恢復(fù)模型時，由于l1-范數(shù)是非光滑凸函數(shù)，給l1-范數(shù)最小化問題的求解帶來了一定難度．李雙安[47]利用Nesterov光滑技術(shù)把l1-范數(shù)近似為一個光滑函數(shù)，原問題就轉(zhuǎn)變成求解光滑無約束凸規(guī)劃問題，然后利用改進(jìn)的HS算法求解該問題，從而達(dá)到大規(guī)模稀疏信號恢復(fù)的目的．

與前述類似，王慧敏等[48]為解決l0-范數(shù)非凸非連續(xù)無法用凸優(yōu)化算法求解的問題，基于Gauss函數(shù)提出一個新的光滑函數(shù)逼近l0-范數(shù)．因此原模型就轉(zhuǎn)化成可用凸優(yōu)化算法求解的凸優(yōu)化問題，作者在研究中選擇PRP法完成了信號恢復(fù)過程．

4 小結(jié)

共軛梯度法是解決大規(guī)模線性等式和非線性優(yōu)化問題的重要方法之一，其突出優(yōu)點(diǎn)是收斂性強(qiáng)、迭代步驟簡單、對存儲要求低．本文分別介紹了幾種經(jīng)典共軛梯度法及其改進(jìn)算法的發(fā)展變化和收斂性，然后描述了混合共軛梯度法的研究現(xiàn)狀以及共軛梯度法在圖像復(fù)原和壓縮感知中的應(yīng)用．

現(xiàn)有的共軛梯度法在實(shí)踐中取得了優(yōu)異的表現(xiàn)，但部分算法尚存在易受參數(shù)影響、適用于特定的函數(shù)、可能需要在特定條件下證明收斂性等局限性，因此凸組合法中凸組合參數(shù)的選取、對新共軛梯度法的優(yōu)化以及在更弱的搜索條件下證明算法的收斂性等問題有待于后期進(jìn)一步的研究和完善．除此之外，結(jié)合譜方法的譜共軛梯度法中譜參數(shù)的選擇、三項(xiàng)混合共軛梯度法等也值得今后繼續(xù)挖掘和拓展．