基于非下降線搜索的改進PRP共軛梯度方法及在圖像恢復中的應用

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

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

中圖分類號：TP391；O221 文獻標識碼：A 文章編號：2096-4706（2024）17-0062-06

0 引 言

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

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

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

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

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

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

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

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

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

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

且

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

且，

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

（1）

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

（2）

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

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

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

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

（3）

（4）

其中：

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

1 算法和收斂性分析

基于線搜索技術（1）和改進的PRP公式（3），提出了一種改進的PRP算法：

算法1

1）選擇初始點，δ＞0，η＞0，ρ∈（0，1），

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

2）如果，停止。

3）利用式（3）計算dk。

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

5）設xk+1=xk+αkdk。令k=k+1，并轉到步驟2。

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

1）水平集是有界的；

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

， （5）

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

， （6）

引理1 令假設1成立，則：

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

由引理1可知：

（7）

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

（8）

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

. （9）

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

其中a∈（0，1）。

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

（10）

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

，

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

其中：

得證。

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

（11）

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

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

此結論與（8）式矛盾。

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

（12）

由上式可知，當，式（1）是不成立的，即：

上式等價于：

（13）

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

則（13）式轉化為：

（14）

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

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

即：

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

2 數(shù)值實驗

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

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

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

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

或

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

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

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

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

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

2.2 圖像修復問題

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

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

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

停止準則：

或成立

噪聲信息：30%、50%、75%強度的椒鹽噪聲。

參數(shù)設置：與上一個實驗相同。

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

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

如圖4所示，第一列的圖片是被30%強度椒鹽噪聲破壞的圖像，第二列和第三列分別是由標準PRP算法和改進PRP算法恢復的圖像。

如圖5所示，第一列的圖片是被50%強度椒鹽噪聲破壞的圖像，第二列和第三列分別是由標準PRP算法和改進PRP算法恢復的圖像。

如圖6所示，第一列的圖片是被75%強度椒鹽噪聲破壞的圖像，第二列和第三列分別是由標準PRP算法和改進PRP算法恢復的圖像。

圖4、5、6分別展示了因不同程度的椒鹽噪聲受損的圖像和由兩種不同算法恢復的圖像，表1列出了所需的CPU時間（以秒為單位）和相應的PSNR值。基于以上數(shù)據(jù)可以得到如下結論：

1）兩種算法都在合適的時間內成功地修復了圖像，并獲得了合適的 PSNR 值。基于非下降線搜索的改進PRP方法在圖像恢復方面表現(xiàn)出有效性。

2）隨著噪聲水平的逐漸升高，所需的CPU處理時間也相應延長，這導致圖像恢復所需的成本也隨之上升。

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

3 結 論

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

參考文獻：

[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].強激光與粒子束，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ù)值結果 [J].數(shù)值計算與計算機應用，2007（1）：56-62.

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

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

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

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

[10]劉慧云，簡艾倫，孫文娟，等.一個修正的非線性三項PRP共軛梯度算法[J].廣西大學學報：自然科學版，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

基金項目：2023年中央高校基本科研業(yè)務經(jī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