摘 要：PRP方法是最有效的非线性共轭梯度优化方法之一，然而该方法不能保证产生目标函数的下降方向，这给一般函数的全局收敛带来了困难。为了保证PRP方法的全局收敛性，提出了一种改进的PRP共轭梯度方法。文章以非凸优化问题为目标，简要介绍了非下降线搜索技术以及一些适当的假设条件，探讨了改进PRP方法的全局收敛性。基于MATLAB软件工具，验证了新方法在处理无约束优化和图像恢复问题时的有效性和实用性。
关键词：共轭梯度方法；非下降线搜索；全局收敛性；无约束优化；图像修复
中图分类号：TP391；O221 文献标识码：A 文章编号：2096-4706（2024）17-0062-06
0 引 言
图像恢复是当前研究中一个备受关注的领域。通过利用图像退化的先验信息建立图像退化模型，这种图像处理技术可以比较准确地还原图像的原始信息。图像恢复不仅是人们获取和理解图像信息的重要步骤，也是进行进一步图像处理的基础。图像恢复问题的关键在于将其转化为大规模的非光滑和非凸的最优化问题，因此需要采用一些优化方法来解决。共轭梯度法是一种被广泛应用于图像处理领域的稳定迭代方法，它具有诸多优点。在处理图像数据时，共轭梯度法能够高效地找到图像中的最优解，提高图像处理的准确性和效率。
Hanke等[1]讨论了含有噪声和近似已知卷积核的图像病态反卷积问题。利用共轭梯度法迭代计算，可以得到清晰的近似图像，避免模糊情况发生。而景越峰等[2]将闪光照相图像重建问题视为大型稀疏矩阵的线性方程组的求解问题。共轭梯度算法被证明是解决这类大规模优化问题的有效算法，并且可根据不同需要在一定准则下求解不适定的闪光照相图像重建问题。此外，引入了Tikhonov的正则化方法来解决不适定问题。针对非光滑非凸的最小化图像恢复问题，Chen等[3]进行了相关研究，考虑如下形式的模型：
提出了一种光滑的非线性共轭梯度算法，该算法能够随时调整光滑参数，确保得到的每个聚点都是Clarke不动点。同时，还提出了一系列具有很好逼近性质的光滑函数。
通过以上阐述可知，共轭梯度方法在图像处理中具有广泛应用。因此，本文提出了一种改进的共轭梯度方法，旨在提升图像恢复的质量。研究过程中考虑如下无约束优化问题：
其中，为一个连续可微的函数。在实际生产中，无约束优化问题通常具有大规模性和难度大的特点。非线性共轭梯度法是求解大规模无约束优化问题的一种广泛且高效的方法。传统的非线性共轭梯度算法首先给定初始点，然后生成迭代点序列{xk}，其通常具有以下形式：
其中αk为由某些线搜索技术确定的步长，dk为搜索方向，由以下式子计算得到：
其中gk=g（xk）=∆f（xk）为函数f（xk）在xk点的梯度，βk为共轭参数，一些经典的共轭参数定义分别如下：
其中yk-1=gk-gk-1，Sk-1=xk-xk-1以及为欧几里得范数。CD方法、DY方法和FR方法的收敛性相对容易建立，但具体的数值结果并没有达到预期。Powell[4]对FR方法的数值缺点进行了解释，例如如果一个小步骤是从解点开始的，则后续步骤会非常短。但是，如果在实际计算中出现方向不好的情况，PRP、HS或LS方法会执行重启，所以这三种方法的性能要比以上三种方法好得多，它们通常被认为是最有效的共轭梯度法。需要注意的是，βk的不同选择衍生出不同的共轭梯度方法，其理论性质和数值效果可能存在显著差异[5-10]。尽管传统的共轭梯度方法取得了丰富的成果，但文献[11]指出仍然存在一些理论和计算挑战，包括步长计算、二阶曲率信息、最佳共轭条件等。因此，针对大规模问题设计具有更好性能的共轭梯度方法是有意义的。
对一个高效的算法而言，选用适当的线性搜索方法对其性能起到了决定性的作用。如今，众多的单调线搜索技术已经被提出并在共轭梯度算法中得到应用，其中Armijo线搜索被认为是最具代表性的方法之一。对于给定的δ∈（0，1），该方法的步长αk=max{pj，j=0，1，2，…}需满足：
其中ρ∈（0，1）。Grippo等[12]为了确保PRP方法在处理一般函数时具有全局收敛特性，提出了一种全新的下降线搜索方法：
且
其中， μ＞0，δ＞0，0＜t＜1且0＜t1＜1＜t2。Dai提出了另外一种下降线搜索技术，形式如下：
且，
其中t∈（0，1），δ＞0，σ2∈（0，1）且αk=tm，m＞0。当采用上述两种线性搜索方法时，PRP方法能够满足一般函数的收敛性要求。与Armijo线搜索相比，以上两种线搜索需要更多时间来计算梯度评估，因此Zhou[13]引入了非下降回溯型线搜索，对于给定的ρ∈（0，1），正常数δ和η，其步长αk=max{1，ρ1，ρ2，…}满足：
（1）
其中{ηk}为一个正序列且对于正常数η满足：
（2）
很容易看出，线搜索技术（1）定义良好，并且无论dk是否是下降方向，都不会计算除gk之外的其他梯度评估。
PRP方法的全局收敛特性已经受到了广大研究者的关注。Polak等已经证实，对于强凸函数，具有精确线搜索功能的PRP方法是全局收敛的，但在Wolfe线搜索技术环境下，该方法无法满足一般函数的全局收敛需求。在搜索方向呈现下降趋势时，Yuan采用了经过优化的Wolfe线搜索方法，从而进一步确立了全局的收敛性。所有关于PRP算法的收敛性讨论都表明研究PRP方法的关键问题是充分下降条件。然而，PRP方法有几个局限性，使得它可能无法在精确线搜索下提供目标函数的下降方向，这对一般函数的全局收敛产生了很大影响。基于此，Gilbert和Nocedal给定，对于非凸函数，PRP方法在合适的线搜索下是全局收敛的。因此，通过修改βk，算法可以满足一般函数的全局收敛性。Hager等[14]设计参数βk如下：
其中η＞0为一个常数。该方法的一个突出优点是搜索方向dk与所使用的线搜索无关，且满足。在Wolfe线搜索下，该方法也是全局收敛的。
结合以上讨论，本文提出一种新的改进PRP共轭梯度方法，dk的更新公式如下：
（3）
（4）
其中：
新方法的搜索方向具有梯度值和函数值信息，并且如果在远离解的地方产生一个小步长，则倾向于转向最速下降方向，从而防止出现一系列的微小步长。结合线搜索（1），验证了改进的PRP共轭梯度方法具有全局收敛特性，并且数值结果表明，对于指定问题，改进的PRP方法相比于标准PRP方法更有竞争力。针对图像修复问题，通过比较PSNR值和CPU时间，改进的PRP方法也表现出优异的性能。
1 算法和收敛性分析
基于线搜索技术（1）和改进的PRP公式（3），提出了一种改进的PRP算法：
算法1
1）选择初始点，δ＞0，η＞0，ρ∈（0，1），
ε∈（0，1）。令正序列{ηk}满足式（2），设置。
2）如果，停止。
3）利用式（3）计算dk。
4）利用非下降线搜索规则（1）计算步长αk。
5）设xk+1=xk+αkdk。令k=k+1，并转到步骤2。
算法1在目标函数上的全局收敛性需要一些必要的假设，以下是假设1：
1）水平集是有界的；
2）在T0的某个邻域N内，目标函数f是可微的，且其梯度函数g是Lipschitz连续的，即对于常数L＞0：
， （5）
假设1意味着存在一个正常数M，使得：
， （6）
引理1 令假设1成立，则：
证 由式（1）（2）可知，该结论显然成立。
由引理1可知：
（7）
引理2 令假设1成立，如果存在常数τ＞0满足：
（8）
则对于常数M1＞0，有：
. （9）
证 根据（5）式和中值定理可得：
其中a∈（0，1）。
由上式和式（4）（5）（6）（7）（8）可得：
（10）
这意味着存在一个整数k0和一个常数r∈（0，1），使得：
，
再根据式（3）可得：
其中：
得证。
定理1 令假设1成立，序列{xk}由算法一产生，则：
（11）
证 用反证法。假设（11）是不成立的，则存在一个正常数τ，使得式（8）对于所有的k≥0成立。因此引理2成立。
1）如果，根据式（3）（10）（9）可得：
此结论与（8）式矛盾。
2）如果，由式（7）可得：
（12）
由上式可知，当，式（1）是不成立的，即：
上式等价于：
（13）
由中值定理和（3）式可知，存在θk∈（0，1）使得：
则（13）式转化为：
（14）
根据式（10）（9）（6）可得：
由于{xk}∈T0是有界的，那么不失一般性，假设，令（14）式两边同时，可得：
即：
上式和式（8）相矛盾，即得证。
2 数值实验
本节将给出改进的PRP算法和传统的PRP算法的一些不同的数值结果，包括普通的无约束优化问题和图像修复问题。所有代码均用MATLAB编写，并在Windows 11操作系统、具有8.00 GB内存的2.40 GHz CPU上运行。
2.1 普通无约束优化问题
为了验证算法一的数值性能，使用改进的PRP算法和传统的PRP算法以及相同的非下降线搜索技术进行各种数值实验，实验中使用的参数数据如下：
停止准则（Himmelblau停止规则[15]），如果，令：
或
如果满足条件或stop1＜e2，其中e1=e2=10-5且ε=10-6，则迭代次数大于1 000时算法将停止。
被测试问题的维度：3 000，6 000，9 000。
参数设置：δ=0.2，ρ=0.8。
Dolan等[16]提出了一种新工具来展示算法性能，以便分析算法的效率。图1至图3分别表示CPU时间、迭代次数NI和计算函数值和梯度值的总次数NFG相关的曲线。图中水平和垂直坐标的参数表示如下：τ为新方法在求解某一个问题时的性能（CPU时间、NI或NFG）和所有方法中最佳性能的比值的倒数， 表示当此方法的比率小于参数τ时，能够解决的问题占总问题的比值。
图1～3表明，改进PRP算法的性能从某种意义上来讲是最好的。在图2中它以最少的迭代次数（NI）解决了大约96%的测试问题，而标准PRP方法只解决了60%的测试问题。同时图2显示，改进PRP算法在计算函数值和梯度值总次数（NFG）的问题上以最少的次数解决了88%的测试问题，并且当τ=5时，可以解决98%以上的问题，这个结果表明改进PRP算法有更强的鲁棒稳定性。如图1所示，改进PRP算法的CPU时间优于标准PRP算法。综上所述，本文提出的算法具有一定的优势和较强的竞争力，是解决无约束优化问题的最有效方法之一。
2.2 图像修复问题
在本节中，为了消除脉冲噪声，求解如下无约束优化问题：
其中为对应的合成运算符，它被列为用来合成信号x=Wκ的波形，W*为分析运算符，[W*x]i为第i次的W*x元素，ϕj为第j次具有参数μ的保边势函数，最后λ＞0为一个常数。
本实验旨在把受脉冲噪声损害的图像还原为原始图像。随着图像处理应用范围的逐步扩大，学者们也开始将注意力集中在如何使用优化方法求解图像处理问题。本实验将改进PRP方法与标准PRP方法对同一图像进行复原，从而比较了两种算法在性能上的差异。实验中的数据选取如下：
停止准则：
或成立
噪声信息：30%、50%、75%强度的椒盐噪声。
参数设置：与上一个实验相同。
测试图像：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值。基于以上数据可以得到如下结论：
1）两种算法都在合适的时间内成功地修复了图像，并获得了合适的 PSNR 值。基于非下降线搜索的改进PRP方法在图像恢复方面表现出有效性。
2）随着噪声水平的逐渐升高，所需的CPU处理时间也相应延长，这导致图像恢复所需的成本也随之上升。
3）对于不同强度的噪声问题，改进PRP算法比标准PRP算法更加有效和可靠。综合考虑上述实验数据和深入分析，新算法在市场上具有显著的竞争优势和出色的性能表现。
3 结 论
共轭梯度方法因其简单性和较低的存储需求，在处理大规模无约束优化问题时表现出极高的有效性。基于一种非下降线搜索技术，提出了一类搜索方向具有梯度值和函数值，且可以防止出现一系列的微小步长的改进PRP共轭梯度算法。在某些适当的前提条件中，建立了非凸函数的全局收敛特性。数值结果表明，在非凸优化方面，改进的PRP方法与标准PRP方法相比具有更强的竞争力。新算法在图像恢复问题上的应用也展示了出色的执行性能。对于不同强度的噪声问题，改进PRP算法更加有效和可靠。未来还应考虑新算法对于其他的线搜索技术是否也会表现出如此优异的性能，并且应该针对大型实际问题进行更多的数值实验。
参考文献：
[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共轭梯度法的全局收敛性及其数值结果 [J].数值计算与计算机应用，2007（1）：56-62.
[6] 王祥玲，左双勇.在新线搜索下修正PRP共轭梯度法的收敛性 [J].云南民族大学学报：自然科学版，2017，26（1）：46-49.
[7] 王松华，黎勇，吴加其，等.一种修正的三项PRP共轭梯度法 [J].河北科技大学学报，2018，39（6）：518-526.
[8] 张慧玲，赛·闹尔再，吴晓云.修正PRP共轭梯度方法求解无约束最优化问题 [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—），男，汉族，河南长葛人，助教，硕士，研究方向：图像处理、最优化控制理论。
DOI：10.19850/j.cnki.2096-4706.2024.17.012
收稿日期：2024-03-16
基金项目：2023年中央高校基本科研业务经费项目（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
