基于非下降線搜索的改進(jìn)PRP共軛梯度方法及在圖像恢復(fù)中的應(yīng)用

摘 要：PRP方法是最有效的非線性共軛梯度優(yōu)化方法之一，然而該方法不能保證產(chǎn)生目標(biāo)函數(shù)的下降方向，這給一般函數(shù)的全局收斂帶來了困難。為了保證PRP方法的全局收斂性，提出了一種改進(jìn)的PRP共軛梯度方法。文章以非凸優(yōu)化問題為目標(biāo)，簡要介紹了非下降線搜索技術(shù)以及一些適當(dāng)?shù)募僭O(shè)條件，探討了改進(jìn)PRP方法的全局收斂性?；贛ATLAB軟件工具，驗(yàn)證了新方法在處理無約束優(yōu)化和圖像恢復(fù)問題時(shí)的有效性和實(shí)用性。

關(guān)鍵詞：共軛梯度方法；非下降線搜索；全局收斂性；無約束優(yōu)化；圖像修復(fù)

中圖分類號(hào)：TP391；O221 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：2096-4706（2024）17-0062-06

0 引 言

圖像恢復(fù)是當(dāng)前研究中一個(gè)備受關(guān)注的領(lǐng)域。通過利用圖像退化的先驗(yàn)信息建立圖像退化模型，這種圖像處理技術(shù)可以比較準(zhǔn)確地還原圖像的原始信息。圖像恢復(fù)不僅是人們獲取和理解圖像信息的重要步驟，也是進(jìn)行進(jìn)一步圖像處理的基礎(chǔ)。圖像恢復(fù)問題的關(guān)鍵在于將其轉(zhuǎn)化為大規(guī)模的非光滑和非凸的最優(yōu)化問題，因此需要采用一些優(yōu)化方法來解決。共軛梯度法是一種被廣泛應(yīng)用于圖像處理領(lǐng)域的穩(wěn)定迭代方法，它具有諸多優(yōu)點(diǎn)。在處理圖像數(shù)據(jù)時(shí)，共軛梯度法能夠高效地找到圖像中的最優(yōu)解，提高圖像處理的準(zhǔn)確性和效率。

Hanke等[1]討論了含有噪聲和近似已知卷積核的圖像病態(tài)反卷積問題。利用共軛梯度法迭代計(jì)算，可以得到清晰的近似圖像，避免模糊情況發(fā)生。而景越峰等[2]將閃光照相圖像重建問題視為大型稀疏矩陣的線性方程組的求解問題。共軛梯度算法被證明是解決這類大規(guī)模優(yōu)化問題的有效算法，并且可根據(jù)不同需要在一定準(zhǔn)則下求解不適定的閃光照相圖像重建問題。此外，引入了Tikhonov的正則化方法來解決不適定問題。針對非光滑非凸的最小化圖像恢復(fù)問題，Chen等[3]進(jìn)行了相關(guān)研究，考慮如下形式的模型：

提出了一種光滑的非線性共軛梯度算法，該算法能夠隨時(shí)調(diào)整光滑參數(shù)，確保得到的每個(gè)聚點(diǎn)都是Clarke不動(dòng)點(diǎn)。同時(shí)，還提出了一系列具有很好逼近性質(zhì)的光滑函數(shù)。

通過以上闡述可知，共軛梯度方法在圖像處理中具有廣泛應(yīng)用。因此，本文提出了一種改進(jìn)的共軛梯度方法，旨在提升圖像恢復(fù)的質(zhì)量。研究過程中考慮如下無約束優(yōu)化問題：

其中，為一個(gè)連續(xù)可微的函數(shù)。在實(shí)際生產(chǎn)中，無約束優(yōu)化問題通常具有大規(guī)模性和難度大的特點(diǎn)。非線性共軛梯度法是求解大規(guī)模無約束優(yōu)化問題的一種廣泛且高效的方法。傳統(tǒng)的非線性共軛梯度算法首先給定初始點(diǎn)，然后生成迭代點(diǎn)序列{xk}，其通常具有以下形式：

其中αk為由某些線搜索技術(shù)確定的步長，dk為搜索方向，由以下式子計(jì)算得到：

其中g(shù)k=g（xk）=?f（xk）為函數(shù)f（xk）在xk點(diǎn)的梯度，βk為共軛參數(shù)，一些經(jīng)典的共軛參數(shù)定義分別如下：

其中yk-1=gk-gk-1，Sk-1=xk-xk-1以及為歐幾里得范數(shù)。CD方法、DY方法和FR方法的收斂性相對容易建立，但具體的數(shù)值結(jié)果并沒有達(dá)到預(yù)期。Powell[4]對FR方法的數(shù)值缺點(diǎn)進(jìn)行了解釋，例如如果一個(gè)小步驟是從解點(diǎn)開始的，則后續(xù)步驟會(huì)非常短。但是，如果在實(shí)際計(jì)算中出現(xiàn)方向不好的情況，PRP、HS或LS方法會(huì)執(zhí)行重啟，所以這三種方法的性能要比以上三種方法好得多，它們通常被認(rèn)為是最有效的共軛梯度法。需要注意的是，βk的不同選擇衍生出不同的共軛梯度方法，其理論性質(zhì)和數(shù)值效果可能存在顯著差異[5-10]。盡管傳統(tǒng)的共軛梯度方法取得了豐富的成果，但文獻(xiàn)[11]指出仍然存在一些理論和計(jì)算挑戰(zhàn)，包括步長計(jì)算、二階曲率信息、最佳共軛條件等。因此，針對大規(guī)模問題設(shè)計(jì)具有更好性能的共軛梯度方法是有意義的。

對一個(gè)高效的算法而言，選用適當(dāng)?shù)木€性搜索方法對其性能起到了決定性的作用。如今，眾多的單調(diào)線搜索技術(shù)已經(jīng)被提出并在共軛梯度算法中得到應(yīng)用，其中Armijo線搜索被認(rèn)為是最具代表性的方法之一。對于給定的δ∈（0，1），該方法的步長αk=max{pj，j=0，1，2，…}需滿足：

其中ρ∈（0，1）。Grippo等[12]為了確保PRP方法在處理一般函數(shù)時(shí)具有全局收斂特性，提出了一種全新的下降線搜索方法：

且

其中， μ＞0，δ＞0，0＜t＜1且0＜t1＜1＜t2。Dai提出了另外一種下降線搜索技術(shù)，形式如下：

且，

其中t∈（0，1），δ＞0，σ2∈（0，1）且αk=tm，m＞0。當(dāng)采用上述兩種線性搜索方法時(shí)，PRP方法能夠滿足一般函數(shù)的收斂性要求。與Armijo線搜索相比，以上兩種線搜索需要更多時(shí)間來計(jì)算梯度評估，因此Zhou[13]引入了非下降回溯型線搜索，對于給定的ρ∈（0，1），正常數(shù)δ和η，其步長αk=max{1，ρ1，ρ2，…}滿足：

（1）

其中{ηk}為一個(gè)正序列且對于正常數(shù)η滿足：

（2）

很容易看出，線搜索技術(shù)（1）定義良好，并且無論dk是否是下降方向，都不會(huì)計(jì)算除gk之外的其他梯度評估。

PRP方法的全局收斂特性已經(jīng)受到了廣大研究者的關(guān)注。Polak等已經(jīng)證實(shí)，對于強(qiáng)凸函數(shù)，具有精確線搜索功能的PRP方法是全局收斂的，但在Wolfe線搜索技術(shù)環(huán)境下，該方法無法滿足一般函數(shù)的全局收斂需求。在搜索方向呈現(xiàn)下降趨勢時(shí)，Yuan采用了經(jīng)過優(yōu)化的Wolfe線搜索方法，從而進(jìn)一步確立了全局的收斂性。所有關(guān)于PRP算法的收斂性討論都表明研究PRP方法的關(guān)鍵問題是充分下降條件。然而，PRP方法有幾個(gè)局限性，使得它可能無法在精確線搜索下提供目標(biāo)函數(shù)的下降方向，這對一般函數(shù)的全局收斂產(chǎn)生了很大影響。基于此，Gilbert和Nocedal給定，對于非凸函數(shù)，PRP方法在合適的線搜索下是全局收斂的。因此，通過修改βk，算法可以滿足一般函數(shù)的全局收斂性。Hager等[14]設(shè)計(jì)參數(shù)βk如下：

其中η＞0為一個(gè)常數(shù)。該方法的一個(gè)突出優(yōu)點(diǎn)是搜索方向dk與所使用的線搜索無關(guān)，且滿足。在Wolfe線搜索下，該方法也是全局收斂的。

結(jié)合以上討論，本文提出一種新的改進(jìn)PRP共軛梯度方法，dk的更新公式如下：

（3）

（4）

其中：

新方法的搜索方向具有梯度值和函數(shù)值信息，并且如果在遠(yuǎn)離解的地方產(chǎn)生一個(gè)小步長，則傾向于轉(zhuǎn)向最速下降方向，從而防止出現(xiàn)一系列的微小步長。結(jié)合線搜索（1），驗(yàn)證了改進(jìn)的PRP共軛梯度方法具有全局收斂特性，并且數(shù)值結(jié)果表明，對于指定問題，改進(jìn)的PRP方法相比于標(biāo)準(zhǔn)PRP方法更有競爭力。針對圖像修復(fù)問題，通過比較PSNR值和CPU時(shí)間，改進(jìn)的PRP方法也表現(xiàn)出優(yōu)異的性能。

1 算法和收斂性分析

基于線搜索技術(shù)（1）和改進(jìn)的PRP公式（3），提出了一種改進(jìn)的PRP算法：

算法1

1）選擇初始點(diǎn)，δ＞0，η＞0，ρ∈（0，1），

ε∈（0，1）。令正序列{ηk}滿足式（2），設(shè)置。

2）如果，停止。

3）利用式（3）計(jì)算dk。

4）利用非下降線搜索規(guī)則（1）計(jì)算步長αk。

5）設(shè)xk+1=xk+αkdk。令k=k+1，并轉(zhuǎn)到步驟2。

算法1在目標(biāo)函數(shù)上的全局收斂性需要一些必要的假設(shè)，以下是假設(shè)1：

1）水平集是有界的；

2）在T0的某個(gè)鄰域N內(nèi)，目標(biāo)函數(shù)f是可微的，且其梯度函數(shù)g是Lipschitz連續(xù)的，即對于常數(shù)L＞0：

， （5）

假設(shè)1意味著存在一個(gè)正常數(shù)M，使得：

， （6）

引理1 令假設(shè)1成立，則：

證 由式（1）（2）可知，該結(jié)論顯然成立。

由引理1可知：

（7）

引理2 令假設(shè)1成立，如果存在常數(shù)τ＞0滿足：

（8）

則對于常數(shù)M1＞0，有：

. （9）

證 根據(jù)（5）式和中值定理可得：

其中a∈（0，1）。

由上式和式（4）（5）（6）（7）（8）可得：

（10）

這意味著存在一個(gè)整數(shù)k0和一個(gè)常數(shù)r∈（0，1），使得：

，

再根據(jù)式（3）可得：

其中：

得證。

定理1 令假設(shè)1成立，序列{xk}由算法一產(chǎn)生，則：

（11）

證 用反證法。假設(shè)（11）是不成立的，則存在一個(gè)正常數(shù)τ，使得式（8）對于所有的k≥0成立。因此引理2成立。

1）如果，根據(jù)式（3）（10）（9）可得：

此結(jié)論與（8）式矛盾。

2）如果，由式（7）可得：

（12）

由上式可知，當(dāng)，式（1）是不成立的，即：

上式等價(jià)于：

（13）

由中值定理和（3）式可知，存在θk∈（0，1）使得：

則（13）式轉(zhuǎn)化為：

（14）

根據(jù)式（10）（9）（6）可得：

由于{xk}∈T0是有界的，那么不失一般性，假設(shè)，令（14）式兩邊同時(shí)，可得：

即：

上式和式（8）相矛盾，即得證。

2 數(shù)值實(shí)驗(yàn)

本節(jié)將給出改進(jìn)的PRP算法和傳統(tǒng)的PRP算法的一些不同的數(shù)值結(jié)果，包括普通的無約束優(yōu)化問題和圖像修復(fù)問題。所有代碼均用MATLAB編寫，并在Windows 11操作系統(tǒng)、具有8.00 GB內(nèi)存的2.40 GHz CPU上運(yùn)行。

2.1 普通無約束優(yōu)化問題

為了驗(yàn)證算法一的數(shù)值性能，使用改進(jìn)的PRP算法和傳統(tǒng)的PRP算法以及相同的非下降線搜索技術(shù)進(jìn)行各種數(shù)值實(shí)驗(yàn)，實(shí)驗(yàn)中使用的參數(shù)數(shù)據(jù)如下：

停止準(zhǔn)則（Himmelblau停止規(guī)則[15]），如果，令：

或

如果滿足條件或stop1＜e2，其中e1=e2=10-5且ε=10-6，則迭代次數(shù)大于1 000時(shí)算法將停止。

被測試問題的維度：3 000，6 000，9 000。

參數(shù)設(shè)置：δ=0.2，ρ=0.8。

Dolan等[16]提出了一種新工具來展示算法性能，以便分析算法的效率。圖1至圖3分別表示CPU時(shí)間、迭代次數(shù)NI和計(jì)算函數(shù)值和梯度值的總次數(shù)NFG相關(guān)的曲線。圖中水平和垂直坐標(biāo)的參數(shù)表示如下：τ為新方法在求解某一個(gè)問題時(shí)的性能（CPU時(shí)間、NI或NFG）和所有方法中最佳性能的比值的倒數(shù)， 表示當(dāng)此方法的比率小于參數(shù)τ時(shí)，能夠解決的問題占總問題的比值。

圖1～3表明，改進(jìn)PRP算法的性能從某種意義上來講是最好的。在圖2中它以最少的迭代次數(shù)（NI）解決了大約96%的測試問題，而標(biāo)準(zhǔn)PRP方法只解決了60%的測試問題。同時(shí)圖2顯示，改進(jìn)PRP算法在計(jì)算函數(shù)值和梯度值總次數(shù)（NFG）的問題上以最少的次數(shù)解決了88%的測試問題，并且當(dāng)τ=5時(shí)，可以解決98%以上的問題，這個(gè)結(jié)果表明改進(jìn)PRP算法有更強(qiáng)的魯棒穩(wěn)定性。如圖1所示，改進(jìn)PRP算法的CPU時(shí)間優(yōu)于標(biāo)準(zhǔn)PRP算法。綜上所述，本文提出的算法具有一定的優(yōu)勢和較強(qiáng)的競爭力，是解決無約束優(yōu)化問題的最有效方法之一。

2.2 圖像修復(fù)問題

在本節(jié)中，為了消除脈沖噪聲，求解如下無約束優(yōu)化問題：

其中為對應(yīng)的合成運(yùn)算符，它被列為用來合成信號(hào)x=Wκ的波形，W*為分析運(yùn)算符，[W*x]i為第i次的W*x元素，?j為第j次具有參數(shù)μ的保邊勢函數(shù)，最后λ＞0為一個(gè)常數(shù)。

本實(shí)驗(yàn)旨在把受脈沖噪聲損害的圖像還原為原始圖像。隨著圖像處理應(yīng)用范圍的逐步擴(kuò)大，學(xué)者們也開始將注意力集中在如何使用優(yōu)化方法求解圖像處理問題。本實(shí)驗(yàn)將改進(jìn)PRP方法與標(biāo)準(zhǔn)PRP方法對同一圖像進(jìn)行復(fù)原，從而比較了兩種算法在性能上的差異。實(shí)驗(yàn)中的數(shù)據(jù)選取如下：

停止準(zhǔn)則：

或成立

噪聲信息：30%、50%、75%強(qiáng)度的椒鹽噪聲。

參數(shù)設(shè)置：與上一個(gè)實(shí)驗(yàn)相同。

測試圖像：Barbara（512×512）、Baboon（512×512）、Lena（512×512）。

為了定性評估兩種方法對圖像恢復(fù)的性能，采用文獻(xiàn)[17]中的峰值信噪比（PSNR）。詳細(xì)的性能結(jié)果在圖4、5、6和表1中給出。

如圖4所示，第一列的圖片是被30%強(qiáng)度椒鹽噪聲破壞的圖像，第二列和第三列分別是由標(biāo)準(zhǔn)PRP算法和改進(jìn)PRP算法恢復(fù)的圖像。

如圖5所示，第一列的圖片是被50%強(qiáng)度椒鹽噪聲破壞的圖像，第二列和第三列分別是由標(biāo)準(zhǔn)PRP算法和改進(jìn)PRP算法恢復(fù)的圖像。

如圖6所示，第一列的圖片是被75%強(qiáng)度椒鹽噪聲破壞的圖像，第二列和第三列分別是由標(biāo)準(zhǔn)PRP算法和改進(jìn)PRP算法恢復(fù)的圖像。

圖4、5、6分別展示了因不同程度的椒鹽噪聲受損的圖像和由兩種不同算法恢復(fù)的圖像，表1列出了所需的CPU時(shí)間（以秒為單位）和相應(yīng)的PSNR值?；谝陨蠑?shù)據(jù)可以得到如下結(jié)論：

1）兩種算法都在合適的時(shí)間內(nèi)成功地修復(fù)了圖像，并獲得了合適的 PSNR 值?；诜窍陆稻€搜索的改進(jìn)PRP方法在圖像恢復(fù)方面表現(xiàn)出有效性。

2）隨著噪聲水平的逐漸升高，所需的CPU處理時(shí)間也相應(yīng)延長，這導(dǎo)致圖像恢復(fù)所需的成本也隨之上升。

3）對于不同強(qiáng)度的噪聲問題，改進(jìn)PRP算法比標(biāo)準(zhǔn)PRP算法更加有效和可靠。綜合考慮上述實(shí)驗(yàn)數(shù)據(jù)和深入分析，新算法在市場上具有顯著的競爭優(yōu)勢和出色的性能表現(xiàn)。

3 結(jié) 論

共軛梯度方法因其簡單性和較低的存儲(chǔ)需求，在處理大規(guī)模無約束優(yōu)化問題時(shí)表現(xiàn)出極高的有效性。基于一種非下降線搜索技術(shù)，提出了一類搜索方向具有梯度值和函數(shù)值，且可以防止出現(xiàn)一系列的微小步長的改進(jìn)PRP共軛梯度算法。在某些適當(dāng)?shù)那疤釛l件中，建立了非凸函數(shù)的全局收斂特性。數(shù)值結(jié)果表明，在非凸優(yōu)化方面，改進(jìn)的PRP方法與標(biāo)準(zhǔn)PRP方法相比具有更強(qiáng)的競爭力。新算法在圖像恢復(fù)問題上的應(yīng)用也展示了出色的執(zhí)行性能。對于不同強(qiáng)度的噪聲問題，改進(jìn)PRP算法更加有效和可靠。未來還應(yīng)考慮新算法對于其他的線搜索技術(shù)是否也會(huì)表現(xiàn)出如此優(yōu)異的性能，并且應(yīng)該針對大型實(shí)際問題進(jìn)行更多的數(shù)值實(shí)驗(yàn)。

參考文獻(xiàn)：

[1] HANKE M，NAGY J. Restoration of Atmospherically Blurred Images by Symmetric Indefinite Conjugate Gradient Techniques [J].Inverse Problems，1996，12（2）： 157-173.

[2] 景越峰，劉瑞根，董維申.一種基于約束共軛梯度的閃光照相圖像重建算法 [J].強(qiáng)激光與粒子束，2005（7）：1083-1087.

[3] CHEN X J，ZHOU W J. Smoothing Nonlinear Conjugate Gradient Method for Image Restoration Using Nonsmooth Nonconvex Minimization [J].SIAM Journal on Imaging Sciences，2010，3（4）： 765-790.

[4] POWELL M J D. Convergence Properties of Algorithm for Nonlinear Optimization [J].SIAM Review，1986，28（4）： 487–500.

[5] 莫降濤，顧能柱，韋增欣.修正PRP共軛梯度法的全局收斂性及其數(shù)值結(jié)果 [J].數(shù)值計(jì)算與計(jì)算機(jī)應(yīng)用，2007（1）：56-62.

[6] 王祥玲，左雙勇.在新線搜索下修正PRP共軛梯度法的收斂性 [J].云南民族大學(xué)學(xué)報(bào)：自然科學(xué)版，2017，26（1）：46-49.

[7] 王松華，黎勇，吳加其，等.一種修正的三項(xiàng)PRP共軛梯度法 [J].河北科技大學(xué)學(xué)報(bào)，2018，39（6）：518-526.

[8] 張慧玲，賽·鬧爾再，吳曉云.修正PRP共軛梯度方法求解無約束最優(yōu)化問題 [J].運(yùn)籌學(xué)學(xué)報(bào)，2022，26（2）：64-72.

[9]李丹丹，王松華.解非線性方程組的雜交修正共軛梯度法及其應(yīng)用[J].云南師范大學(xué)學(xué)報(bào)：自然科學(xué)版，2022，42（4）：18-24.

[10]劉慧云，簡艾倫，孫文娟，等.一個(gè)修正的非線性三項(xiàng)PRP共軛梯度算法[J].廣西大學(xué)學(xué)報(bào)：自然科學(xué)版，2023，48（1）：213-225.

[11] MATHEMATICAL M，ANDREI N. Open Problems in Nonlinear Conjugate Gradient Algorithms for Unconstrained Optimization [J].The Bulletin of the Malaysian Mathematical Society Series，2011，2（2）： 319–330.

[12] GRIPPO L，LUCIDI S. A globally Convergent Version of the Polak-Ribière-Polyak Conjugate Gradient Method [J].Mathematical Programming，1997，78（3）：375-391.

[13] ZHOU W. A Short Note on the Global Convergence of the Unmodified PRP Method [J].Optimization Letters，2013，7（6）：1367-1372.

[14] HAGER W W，ZHANG H. A Survey of Nonlinear Conjugate Gradient Methods [J].Pacific Journal of Optimization，2006，2（1）：35-58.

[15] YUAN Y，SUN W. Theory and Methods of Optimization [M].Beijing：Science Press，1999.

[16] DOLAN E D，MORé J J. Benchmarking Optimization Software with Performance Profiles [J].Mathematical Programming，2002，91（2）：201–213.

[17] BOVIK A. Handbook of Image and Video Processing [J].Academic Press，2000.

作者簡介：李朋原（1995.11—），男，漢族，河南長葛人，助教，碩士，研究方向：圖像處理、最優(yōu)化控制理論。

DOI：10.19850/j.cnki.2096-4706.2024.17.012

收稿日期：2024-03-16

基金項(xiàng)目：2023年中央高?；究蒲袠I(yè)務(wù)經(jīng)費(fèi)項(xiàng)目（2023TJJBKY017）

Improved PRP Conjugate Gradient Method Based on Non-descent Line Search and Application on Image Restoration

LI Pengyuan

（Department of Image and Network Investigation， Zhengzhou Police University， Zhengzhou 450000， Ch+J+8N3Jkhf6mFnYxRXSwYQ==ina）

Abstract： PRP method is one of the most effective methods for nonlinear Conjugate Gradient optimization. However， this method cannot guarantee the decreasing direction of the objective function， which makes the global convergence of the general function difficult. In order to ensure the global convergence of PRP method， an improved PRP Conjugate Gradient Method is proposed. Aiming at the non-convex optimization problem， this paper briefly introduces the non-descent line search technique and some appropriate assumed conditions， and discusses the global convergence of the improved PRP method. Based on MATLAB software tool， the effectiveness and practicability of the new method for processing the unconstrained optimization and image restoration problems are verified.

Keywords： Conjugate Gradient Method; non-descent line search; global convergence; unconstrained optimization; image restoration