一种用于求解大规模非线性单调方程和压缩感知问题的新型DL型方法

《Mathematics and Computers in Simulation》：A novel DL-type method for solving large-scale nonlinear monotone equations and compressed sensing problems

　　王斌斌|王晓亮 摘要 本文提出了一种改进的Dai-Liao型共轭梯度方法，用于求解具有凸约束的大规模非线性单调方程组。该方法通过最小化搜索方向矩阵与缩放后的无记忆BFGS更新矩阵在Frobenius范数下的距离来进行分析。该新方法属于无导数型方法，可应用于某些大规模优化问题。在温和条件下，分别证明了其充分下降性质、全局收敛性质以及线性收敛速率。针对每个测试问题，使用八种不同初始点进行的数值实验结果表明了该方法的鲁棒性。此外，该方法还被应用于受椒盐噪声干扰的信号恢复和图像重建问题，实验结果也体现了该方法的效率与有效性。引言 求解非线性方程组是一项具有广泛应用价值的重大计算挑战。由于大多数现实世界现象都具有内在的非线性特征，因此开发高效的非线性方程组数值方法仍是计算数学领域的研究热点[1]、[2]。重要的方法进展包括牛顿型方法、拟牛顿变体、信赖域算法、同伦延续法、无导数优化技术以及新兴的机器学习增强型方法。这些创新提升了复杂问题的计算效率与稳定性[3]。非线性方程组技术为多个领域带来了突破：在经济学建模中，它们为CGE和DSGE框架提供了支撑[4]；物理系统的平衡状态依赖于机械和化学系统的非线性方程组解；电力系统分析利用这些方法进行故障等级评估[5]；而机器学习优化则依赖非线性方程组求解器进行参数调优[6]；工程设计及反问题处理也展现了该技术的多功能性。最近的进展还将这些方法拓展到了信号处理和图像处理领域。混合共轭梯度方法已成功应用于含有单调方程的信号恢复问题[7]、[8]，而加速共轭梯度方法在大规模图像修复任务中表现出色[9]、[10]。若连续映射F:Rn→Rn满足以下条件，则称其具有单调性：(F(x)?F(y))T(x?y)≥0，?x,y∈C，其中C?Rn是具有易于计算的投影算子的简单闭凸非空集。在讨论非线性单调方程之前，我们首先关注无约束优化问题：minx∈Rnf(x)，其中f是一个光滑的非线性函数，其在xk处的梯度记为?f(xk)=g(xk)。对于中小规模问题，拟牛顿方法是一种非常有效的方法。它利用目标函数值及其一阶导数的信息，近似经典牛顿方法中的Hessian矩阵，从而显著降低计算成本并提高效率。其迭代形式如下：xk+1=xk+αkdk，k=0,1,…，其中xk表示当前迭代值，αk为步长，dk为搜索方向。通过最小化当前点处目标函数的二次模型，可得到搜索方向：dk=?Bk?1gk，k=0,1,…。目前已有多种拟牛顿方法被开发出来，其中BFGS（Broyden [11]–Fletcher [12]–Goldfarb [13]–Shanno [14]）方法最为著名。其更新公式为：Bk+1=Bk?BkskskTBkskTBksk+ykykTykTsk，k=0,1,…，其中sk=xk+1?xk，yk=gk+1?gk，gk+1=?f(xk+1)。利用秩一型的Sherman–Morrison–Woodbury更新公式[15]两次，可从(1.5)式中推导出Bk+1的逆矩阵Hk+1：Hk+1=Hk?skykTHk+HkykskTykTsk+1+ykTHkykykTskskskTykTsk，k=0,1,…。由于其较高的计算成本，人们倾向于采用无记忆更新方式，即在迭代过程中用单位矩阵替代矩阵Hk：Hk+1=I?skykT+ykskTykTsk+1+ykTykykTskskskTykTsk，k=0,1,…。为了提升BFGS方法的性能，人们又提出了自缩放BFGS方法。在这些方法中，采用了缩放后的无记忆BFGS更新公式[15]、[16]、[17]、[18]，即：Hk+1θk=θkI?θkskykT+ykskTskTyk+1+θkykTykskTykskskTskTyk，k=0,1,…，其中θk>0为缩放参数。尽管采用了参数缩放技术，但BFGS方法在处理大规模问题时仍表现不佳，这促使我们考虑使用共轭梯度方法。共轭梯度算法因其两大优势而成为大规模优化的首选方法：一是需要存储的空间更小，二是具有全局收敛特性，能够保证理论上的可靠性。共轭梯度方法采用迭代公式(1.3)。搜索方向dk通常由下式给出：d0=?g0，dk+1=?gk+1+βkdk，k=0,1,…，其中标量参数βk对决定共轭梯度方法的性能起着关键作用。文献[19]、[20]、[21]、[22]、[23]、[24]中提出的经典共轭梯度参数包括：βkFR=‖gk+1‖2‖gk‖2，βkCD=‖gk+1‖2?gkTdk，βkDY=‖gk+1‖2dkTyk，βkHS=gk+1TykdkTyk，βkPRP=gk+1Tyk‖gk‖2，βkLS=gk+1Tyk?gkTdk。采用公式(1.3)、(1.6)的共轭梯度方法始终满足下降条件：dk+1Tgk+1<0，k=0,1,…。然而，在大多数实际情况下，条件(1.7)并不足够，尤其是对于确保全局收敛而言。因此，需要更强的下降条件，即：dk+1Tgk+1≤?c‖gk+1‖2，k=0,1,…，其中c为正常数。Dai和Liao[25]提出了一种有效的共轭梯度方法，其中更新参数βk定义为：βkDL=gk+1TykykTdk?tgk+1TskdkTyk，yk=gk+1?gk，k=0,1,…，其中参数t∈[0,+∞)在(1.9)式中对DL型方法的数值性能有着重要影响。许多研究者[26]、[27]、[28]等提出了多种t的取值方案。特别地，Dai和Kou[26]提出t=(τk+‖yˉk‖2sˉkTyˉk?sˉkTyˉk‖sˉk‖2)，其中参数τk是根据缩放后的无记忆BFGS方法来选取的；Hager和Zhang[27]提出t=2‖yk‖2skTyk，这一方案基于迭代矩阵的奇异值分析，且能够满足dk的充分下降条件；Babaie-Kafaki和Ghanbar[28]则提出t=‖sk‖2‖yk‖2skTyk2，数值实验表明该方法的性能优于[26]中的方法。在得到共轭梯度搜索方向后，可采用混合投影方法[29]。该方法将牛顿搜索方向与投影技术相结合，无需假设函数的光滑性即可实现全局收敛到解。重要的是，该方法无需导数信息，仅需函数F的函数值，因此可应用于非光滑及大规模优化问题。在本文中，我们提出了一种针对具有凸约束的大规模非线性单调方程的新型DL型方法。本研究的主要贡献包括：(i)我们通过Frobenius范数下的新型矩阵逼近方法推导出了参数βkNDL，而非采用现有的Dai–Liao型公式。这为构建共轭梯度参数提供了新的理论视角，与以往的推导方法有本质区别。(ii)我们引入了基于特征值聚类的准则来调整参数θk。该准则提升了迭代矩阵的谱聚类特性，从而提高了算法的稳定性、收敛速度以及数值性能。(iii)我们设计了一个统一的算法框架，将上述两种技术与修正的割线条件、投影算子以及压缩感知公式相结合。相比简单组合现有模块，该算法在实际应用中表现出更优异的性能。(iv)在特定假设下，我们证明了所提算法的全局收敛性，为其可靠性提供了坚实的理论保障。(v)通过对单调方程、大规模基准问题以及压缩感知应用（包括稀疏信号恢复和图像重建）的大量数值实验，证明了该方法的有效性及竞争力。本文的结构安排如下：第2节介绍新方案的推导过程；第3节阐述所提方法的全局收敛性分析及线性收敛速率；第4节通过数值实验将所提方法与现有文献中的方法进行比较；第5节展示了该方法在现实场景中的应用，尤其是压缩感知中的图像重建任务；第6节给出总结。章节片段 一类自适应的Dai-Liao共轭梯度方法 在本节中，我们首先引入如下新的Dai-Liao搜索方向：dk+1=?Fk+1+βkNDLdk+Fk+1TsˉksˉkTyˉkyˉk，其中：βkNDL=Fk+1TyˉkdkTyˉk?1+sˉkTyˉk‖sˉk‖2+θk(‖yˉk‖2sˉkTyˉk?sˉkTyˉk‖sˉk‖2)Fk+1TsˉkdkTyˉk，其中：yˉk=‖s?k‖‖yk‖yk+csˉk，yk=F(ωk)?F(xk)，sˉk=ωk?xk，c≥1。根据(2.3)式，结合F函数的单调性，可知：sˉkTyˉk=‖s?k‖‖yk‖sˉkTyk+csˉkTsˉk≥c‖sˉk‖2>0。因此根据(2.4)式，βkNDL是有良好定义的。可以看出，该搜索方向可重新表述为：dk+1=?Mk+1Fk+1，?k>0，其中Mk+1为某个矩阵。收敛性分析 引理2 假设假设1成立。dk和xk是由算法2.1生成的序列。那么存在非负数σk，使得(2.14)式成立。证明 假设与事实相反，存在某个k0使得条件(2.14)不成立，即?F(ωk0)Tdk00为正则化参数。此处‖?‖1和‖?‖2分别对应?1范数。结论 本文提出、分析并测试了一类高效的充分下降算法，用于求解带非线性约束的单调方程。这些方法在每次迭代时既不需要方程的梯度信息，也不需要存储任何矩阵。实际上，我们的初衷非常简单直接，即基于Frobenius范数下DL方向的逼近与无记忆缩放BFGS更新的关联，进而推导出相关参数。具体而言，CRediT作者贡献声明 王斌斌：撰写——原始稿件、软件、方法论、概念构思。王晓亮：撰写——原始稿件、软件、方法论、形式分析、概念构思。