楊 雪，李 鋒

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

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

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

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

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

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

對(duì)于無(wú)約束優(yōu)化問(wèn)題：

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

(1)

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

Ax=b,x∈Rn,

(2)

其中，A是對(duì)稱(chēng)正定矩陣，且A∈Rm×n,b∈Rm．

在解決了線性方程組的問(wèn)題之后，如何將該方法推廣到非線性領(lǐng)域值得關(guān)注．于是Fletcher等[4]將HS法的思想運(yùn)用到非線性?xún)?yōu)化問(wèn)題，并提出了FR法，F(xiàn)R法可先在精確線搜索下求解凸二次函數(shù)最小值問(wèn)題，之后他們又將其推廣到一般函數(shù)最小值的求解中[1]；1969年P(guān)olak等[5]和Polyak[6]提出了PRP方法，該方法通過(guò)對(duì)FR方法中βk的改動(dòng)，改善了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計(jì)算公式歸納如下：

(3)

(4)

(5)

(6)

(7)

1.2 共軛梯度法的收斂性

1.2.1 FR方法

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

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

1.2.2 DY方法

由于前人對(duì)FR方法和CD方法的收斂性研究大多停留在精確線搜索或強(qiáng)Wolfe線搜索上，如何在較弱的線搜索條件下提出一種具有全局收斂性的共軛梯度法顯得尤為重要．于是戴彧虹等[9]對(duì)原來(lái)的方法進(jìn)行深入研究后，提出一種在Wolfe線搜索下能自動(dòng)保持下降條件且全局收斂的共軛梯度法，并將其稱(chēng)之為DY方法．之后，戴彧虹[19]分析了DY方法的內(nèi)在性質(zhì)，給出了該方法在遠(yuǎn)離最優(yōu)點(diǎn)時(shí)大部分迭代點(diǎn)列都滿(mǎ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ā)下，對(duì)Zhang[25]的NPRP方法進(jìn)行了改進(jìn)，使改進(jìn)后的NPRP方法在下降方向上具有更好的性能，并將該方法稱(chēng)為DPRP法．因此，DPRP方法和NPRP方法相比較，不僅對(duì)任意線搜索具有充分的下降性，而且在Wolfe線搜索或Armijo線搜索下非凸極小化都保持全局收斂性．此外，將這一結(jié)果推廣到NHS方法，并稱(chēng)為DHS方法．其中：

(13)

(14)

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

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

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

(15)

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

(16)

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

(17)

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

(18)

(19)

(20)

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

(21)

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

(22)

(23)

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

(24)

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

(25)

(26)

類(lèi)似也可以得到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方法凸組合的一種新的混合共軛梯度法，該方法下的搜索方向滿(mǎn)足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)于凸組合的其他混合共軛梯度法還可以參見(jiàn)Djordjevic[37-38]提出的LS和CD方法凸組合的混合共軛梯度法及LS和FR方法凸組合的混合共軛梯度法．

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

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

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

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

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

2020年Yuan等[40]將最速下降算法和LS方法進(jìn)行凸組合，提出了一種修正的共軛算法．新算法的搜索方向在沒(méi)有任何線搜索技術(shù)的情況下，具有充分下降性和信賴(lài)域性質(zhì)，在一定的條件及回溯線搜索技術(shù)下建立了全局收斂性[41]．此外，為了改善目標(biāo)函數(shù)值會(huì)隨迭代次數(shù)增加而縮減的情況，作者對(duì)步長(zhǎng)采用了加速系統(tǒng)[42]，并將該算法成功的應(yīng)用到圖像復(fù)原中，而且數(shù)值實(shí)驗(yàn)表明，該算法與其他方法相比具有一定的優(yōu)勢(shì)．同年，Cao等[43]提出了一種修正PRP共軛梯度法，由新算法定義的搜索方向具有充分下降性和信賴(lài)域特征．由于這兩個(gè)特別好的特性，因此能夠更簡(jiǎn)單地證明非凸函數(shù)在Armijo線搜索下的全局收斂性．同時(shí)作者還用數(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ì)算機(jī)科學(xué)等領(lǐng)域．它利用一個(gè)高度不完備的線性測(cè)量對(duì)稀疏信號(hào)進(jìn)行采樣，這時(shí)獲取的是被“壓縮”后的數(shù)據(jù)．然后，通過(guò)使用高效的方法對(duì)“壓縮”的數(shù)據(jù)進(jìn)行重構(gòu)就能恢復(fù)原稀疏信號(hào)[46]．在進(jìn)行第2步重構(gòu)時(shí)，就可利用共軛梯度法恢復(fù)原始信號(hào)．

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

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

4 小結(jié)

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

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