大规模单调方程的无导数谱投影方法

《Mathematics》：Derivative-Free Spectral Projection Methods for Large-Scale Monotone Equations

　　

摘要专业翻译 研究人员针对带凸约束的大规模单调方程（monotone equations）提出了两种无导数谱投影方法（derivative-free spectral projection methods）。第一种方法SOPP（谱最优Perry投影，Spectral Optimal-Perry Projection）通过在其正定范围内最小化对称化Perry矩阵（symmetrized Perry matrix）的条件数（condition number）来选择Perry参数，取代了早期工作中使用的特征值间隙（eigenvalue-gap）准则。一个裁剪步骤（clipping step）通过构造赋予搜索方向信赖域性质（trust-region property）。第二种方法SDLP（谱Dai–Liao投影，Spectral Dai–Liao Projection）用自适应谱参数取代了固定的Dai–Liao因子。两种方向均独立于线搜索（line search）满足充分下降条件（sufficient descent）。在标准假设下，每种方法要么有限步终止于解，要么生成一个收敛到解的整列序列。SOPP的结果不需要Lipschitz连续性（Lipschitz continuity），而SDLP的分析则需要。在基准问题和两个应用上的数值实验表明，两种方法在合理参数选择下均具有计算可行性和稳定性。

论文解读

一、研究背景与问题

在科学与工程领域，大量实际问题可归结为求解带凸约束的单调方程组（monotone equations），即寻找向量满足G(x)=0且x属于某非空闭凸集，其中G为连续单调映射。变分不等式问题、互补问题、化学平衡计算、压缩感知与信号恢复、正则化逻辑回归以及流体和等离子体物理等问题均可转化为该形式。

当G可微时，Newton法和拟Newton法具有快速局部收敛性，但需要计算或近似Jacobian矩阵，存储量和单步计算成本高昂，在大规模问题或G不可微时不再实用。共轭梯度（CG）方法仅需函数值和O(n)存储，适合大规模问题，但经典CG参数在约束单调方程框架下的扩展仍面临挑战。将CG更新公式与谱参数（spectral parameter）结合形成谱共轭梯度方法，是近年来的重要发展方向。

将此类方法推广到约束情形的关键工具是Solodov和Svaiter提出的投影技术（projection technique）：每步先构造下降方向并经回溯线搜索得到试探点，再利用G的单调性构造分离解集的超平面，最后沿超平面法向做松弛步并投影回可行集。已有多种无导数投影方法基于该框架，但存在若干不足：MOPCG方法通过对称化Perry矩阵的特征值分析推导更新参数，但该准则不一定保持矩阵正定性；CGPM方法的三项系数为Hager–Zhang型，需Lipschitz连续性假设；STTDFPM虽无需Lipschitz条件，但收敛率较低。此外，现有方法中系数常通过最大值、最小值或两式切换选取，而非单一公式，缺乏自适应性。

二、研究内容与结论

针对上述问题，研究人员将自适应谱缩放参数引入MOPCG和CGPM两种框架，提出了两种新方法。SOPP方法在正定范围内直接最小化对称化Perry矩阵的条件数，以闭式解给出唯一最优参数，并通过正交化裁剪步骤在无光滑性假设下构造性地控制方向范数。SDLP方法以自适应谱参数取代固定Dai–Liao因子，其三项方向结构继承CGPM的修正项构造。两种方向均独立于线搜索满足充分下降条件，SOPP甚至满足精确恒等式。

在收敛性方面，SOPP在解集非空、G单调且连续三个假设下即可保证有限步终止或整列收敛，完全不需要Lipschitz连续性；SDLP则在额外假设Lipschitz连续性和参数条件满足时同样收敛。两种方法的正容差版本均保证有限步终止并返回可行近似解。

数值实验覆盖18个测试问题、6个维度、10个初始点共1080个实例，每个实例由5种方法求解。结果显示：SDLP在98.4%的实例上收敛，SOPP为96.9%，分别优于其前身CGPM（96.1%）和MOPCG（93.7%）。SOPP将MOPCG的中位迭代次数从148降至49，SDLP将CGPM的中位函数评估数从90降至65。在压缩感知应用中，SDLP以中位161次迭代和1.87秒CPU时间成为最高效方法，SOPP和SDLP在所有240个实例上全部收敛，而MOPCG在最困难配置上失败20例。在正则化逻辑回归的12个真实数据集上，两种方法同样表现稳定。参数敏感性研究表明，30种参数配置下收敛率始终保持在93.3%至98.9%之间，方法对参数选择不敏感。

三、主要技术方法

研究人员使用了以下关键技术方法：一是Solodov–Svaiter超平面投影技术，利用单调性构造分离超平面并投影回可行集；二是Perry型拟Newton方向，通过对称化Perry矩阵的特征分析确定参数；三是Barzilai–Borwein型谱梯度思想，构造自适应谱参数并投影到有界区间；四是正交化裁剪步骤，将方向分解为谱项与前一方向的正交分量并施加范数裁剪，构造性地保证信赖域性质；五是回溯线搜索与松弛投影步的组合框架；六是有限精度保护机制，当数值异常时自动重启为标准下降方向。数值实验在Julia 1.12中实现，硬件为Intel Core i9-9900K CPU和32GB内存。

四、研究结果

SOPP的Perry参数最优性分析。 研究人员通过引理2至引理7系统分析了对称化Perry矩阵的特征结构，证明特征值间隙最小化准则（Lemma 6）不一定保持矩阵正定性（Lemma 7），并推导出在正定范围内唯一最小化条件数的闭式参数（Theorem 1），该选择对所有数据均保证正定性。

SOPP的下降与信赖域性质。 Lemma 8证明SOPP方向满足精确下降恒等式，与参数选取和裁剪无关；Lemma 9证明裁剪步骤在无任何光滑性假设下强制方向范数有界，赋予信赖域性质。

SDLP的下降与信赖域性质。 Lemma 10通过Young不等式证明SDLP方向满足充分下降条件；Lemma 13在Lipschitz连续性下建立方向范数的上下界。

全局收敛性。 Lemma 11证明回溯线搜索在连续性下有限终止；Lemma 12建立Fejér单调性、残差平方和可求和性等核心估计；Theorem 2证明SOPP在仅假设解集非空、单调性和连续性下全局收敛；Theorem 3证明SDLP在Lipschitz连续性下全局收敛；Corollary 1和2将结果推广到正容差情形。

基准数值实验。 在1080个实例上，SDLP和SOPP取得最高收敛率（98.4%和96.9%），且各自优于其前身方法。在共享成功实例上，SOPP对MOPCG取得857胜12平，SDLP对CGPM取得761胜21平。失败分析显示线搜索失败为主要模式（140例），STTDFPM独占方向范数条件触发的32例失败。

压缩感知应用。 在240个实例上，SOPP、SDLP、CGPM和STTDFPM全部收敛，MOPCG在最困难配置上失败20例；SDLP效率最高，恢复质量各方法相当。

正则化逻辑回归应用。 在12个真实数据集上验证了方法的实际适用性。

参数敏感性研究。 30种配置下收敛率稳定在93.3%至98.9%之间，裁剪常数c和线搜索系数σ无显著影响，谱界和正则化参数影响最大但仍在可接受范围。规则对比实验表明，条件数准则相比特征值间隙准则减少约十分之一的工作量并将保护重启次数从119降至26。

五、讨论与结论

讨论部分指出，特征值间隙准则与条件数准则在目标上并不等价：间隙最小化在特定数据下可将条件数推向无穷甚至破坏正定性，而条件数最小化对所有数据保持正定且条件数有限。两种准则的差异还体现在对数据的响应方式上：间隙最小化对角度变化不敏感，而条件数最小化自适应于数据方向。谱参数选取规则的影响远小于Perry参数选取规则，交替变体的优势在单个维度上不足以改变默认选择。浮点舍入导致的max运算次序偏差对结果影响甚微。

研究结论为：所提出的SOPP和SDLP两种无导数谱投影方法在充分下降和信赖域性质上独立于线搜索，SOPP在无需Lipschitz连续性假设下即可全局收敛，SDLP在Lipschitz假设下同样收敛。数值实验表明两种方法在基准问题、压缩感知和正则化逻辑回归应用中均具有计算可行性和稳定性，SDLP在收敛率上最优，SOPP相对其前身有显著改进，且两种方法对参数选择不敏感。