NeuroSQP：用于大规模带等式约束的非线性优化的加速学习型序列二次规划方法

《Neurocomputing》：NeuroSQP: Learning-accelerated sequential quadratic programming for large-scale equality-constrained nonlinear optimization

　　大规模非线性优化问题在众多科学和工程领域中普遍存在，包括最优控制[4]、[12]、[54]、[59]、[72]，以及经济学与金融领域[5]、[32]、[41]，化学过程设计[13]、[88]、[92]，还有各种工程应用[6]、[69]。这类问题通常被表述为，其中和都是二次连续可微的函数。随着应用规模的扩大和精度要求的提高，现代求解器需要处理包含数千到数百万个决策变量的问题，这就使得高效的线性代数运算、可扩展的导数计算以及有效的预处理策略变得愈发重要。

在约束非线性规划的主要算法体系中，增广拉格朗日法[11]、[28]、[47]、[56]，内点法[40]、[45]、[90]，以及序列二次规划法[14]、[18]、[19]、[20]、[29]、[43]、[51]、[57]、[63]，其中序列二次规划法具有独特的优势。增广拉格朗日法具备良好的初始求解能力，但在接近最优解时确定正确的活跃集可能存在困难。内点法对于单个大规模问题具有出色的鲁棒性，但往往需要复杂的因子分解技术，不太适合处理一系列相关问题。而序列二次规划法则具有若干在现代应用中尤为吸引人的特性：快速的局部收敛速度，通常是超线性的；在非退化情况下能够可靠地识别活跃约束；在不同问题序列之间可实现自然的初始求解；还能与最先进的线性求解器和预处理技术相整合。这些特点使得序列二次规划法在最优控制、参数估计、轨迹优化、偏微分方程约束优化以及实时或模型预测控制等领域表现出色。

序列二次规划法的基础可追溯到Wilson在1963年发表的博士论文[91]。此后的发展——包括优度函数[22]、[42]，拟牛顿方法[21]、[24]、[38]、[39]，以及信任域法和滤波全局化技术[1]、[22]、[42]、[48]、[49]、[89]——使得序列二次规划法成为一种成熟且强大的约束非线性优化框架[23]、[30]。尽管已经相当成熟，但序列二次规划法的可扩展性仍受两大计算难题的限制。首先，对于大规模问题，精确计算并构建拉格朗日海森矩阵的代价可能极高，因此人们采用了拟牛顿更新或有限内存近似方法[70]。其次，在求解二次规划子问题时，每次迭代都需要解决一个二次规划子问题，其最优性条件会导致出现稀疏的、不定型的卡鲁什-库恩-塔克方程组。直接对这种方程组进行因子分解虽然可行，但在大规模问题上成本过高；而像广义最小残差法这样的迭代Krylov子空间方法，则需要利用问题的稀疏性、耦合结构以及各迭代过程中海森矩阵的变化特性来设计预处理器[9]、[46]、[73]。不过，设计这样的预处理器仍然十分困难：传统的预处理器[9]、[16]、[36]、[37]可能需要针对特定问题进行调优，而且在面对结构不同或尺度不匹配的问题时性能会下降。

近期的机器学习方法为设计预处理器提供了新途径，即通过学习稀疏线性系统中的结构模式来实现。图神经网络[7]、[17]、[87]已被成功用于近似稀疏矩阵的因子分解。神经不完全因子分解方法[15]、[58]则利用图神经网络学习生成稀疏三角因子，以此近似对称正定矩阵，且在某些大规模问题上取得了不错的效果。类似地，神经网络也被直接用于求解二次规划问题，比如带约束的凸二次规划[61]，用于线性约束二次规划的离散时间循环神经网络[66]，用于二阶锥规划的循环神经网络[65]，以及用于二元二次规划指针网络[55]。

除了预处理之外，序列二次规划法的可扩展性还得益于将经典优化方法与启发式或神经网络组件相结合的混合计算框架。近期的一些研究展示了序列二次规划法在这些框架中的广泛应用。例如，它已被与随机算法结合用于核物理学中奇异周期非线性微分系统的求解[76]，与启发式计算结合用于四阶Emden–Fowler方程的求解[82]，与带有前馈Gudermannian神经网络的进化启发式方法结合用于奇异三阶Emden–Fowler模型的求解[83]，还与人工神经网络和遗传算法结合用于二阶预测微分模型的求解[81]。其他应用还包括奇异多滑轨延迟微分方程[84]以及医学领域中吸烟行为的非线性模型[85]。与此同时，神经网络也被用作数学模型的端到端求解器，比如用于HIV系统的径向基函数网络和Sigmoid网络[78]，用于预测微分模型的Morlet小波网络与内点法结合使用[75]，用于分数阶系统的贝叶斯正则化网络[79]，用于COVID-19模型的Levenberg–Marquardt反传算法[80]，还有将人工神经网络与遗传算法及内点法结合使用的算法（ANN-GA-IPA），用于奇异三点二阶边值问题的求解[77]。在神经网络动力学方面的理论进展，比如对具有时变延迟的Hopfield网络的稳定性分析[2]、[3]，进一步凸显了神经计算在科学应用中的重要性。尽管这些研究展现了学习型模型的强大能力，但它们大多侧重于直接求解特定方程，或者将神经网络作为优化器本身。然而，这类方法往往并未着眼于在每次迭代中高效地求解大型、不定型的卡鲁什-库恩-塔克方程组。在本研究中，我们正是针对这一核心计算瓶颈，提出了NeuroSQP——一种基于学习的加速型序列二次规划方法，它在保持传统序列二次规划法收敛性保证的同时，大幅降低了每次迭代的成本。NeuroSQP结合了一种混合海森矩阵策略：对于规模适中的问题使用精确的海森矩阵计算，而对于更大规模的问题则采用Broyden–Fletcher–Goldfarb–Shanno（BFGS）更新方法；同时，它还运用基于神经不完全因子分解的神经网络约束预处理器，该预处理器能够根据序列二次规划子问题不断变化的结构进行调整。该预处理器被集成到一种原始-对偶内点二次规划求解器中，即神经预处理内点法（NeuroIPM），并在重启后的GMRES算法中作为右预处理器，从而高效地求解卡鲁什-库恩-塔克方程组。由于经过正则化的海森矩阵和雅可比矩阵会在迭代过程中逐渐变化，这种学习得到的预处理器能够在不同子问题之间良好通用，进而降低整体计算成本。该方法具有三大实际优势：能够在普通硬件上处理变量数量高达一定水平的难题；具备较强的抗填充效应和内存限制能力，而这些正是传统直接求解法所面临的困扰；此外，即便仅基于合成数据训练，它也能适用于多种不同类型的问题，无需针对每个问题进行单独调优。

需要明确的是，NeuroSQP与那些将神经网络作为优化问题端到端求解器的方法有所不同。例如，Hopfield神经网络已被用于通过动态演化逼近最优解的方式来求解二次规划问题[61]，而指针网络则被应用于二元二次规划问题[55]。在这些方法中，神经网络本身就充当优化器，直接生成候选解。虽然这类方法在计算效率上可能具有优势，但它们往往无法提供传统优化算法所具备的严格收敛性和可行性保证，而这些属性在许多科学和工程应用中至关重要。相比之下，NeuroSQP仅将图神经网络作为传统序列二次规划框架内的预处理器。神经网络负责学习一种近似的因子分解方式，用以加速卡鲁什-库恩-塔克方程组的求解，而序列二次规划的主循环，包括线搜索和优度函数部分，则保持不变。因此，NeuroSQP完全继承了传统序列二次规划方法的收敛性保证：无论从何种初始点出发，都能通过优度函数和线搜索实现向卡鲁什-库恩-塔克点的全局收敛；而在接近解之后，则能实现快速的局部收敛，收敛速度可能是超线性的或二次的。这种混合设计将成熟优化理论的可靠性与机器学习的适应性及高效性有机结合在了一起。

本研究的主要贡献如下：
•据我们所知，这是首次将基于图神经网络的不完全因子分解模型作为约束预处理器集成到序列二次规划框架中，用于非线性等式约束优化问题的求解。
•提出了一种混合海森矩阵策略，能够在精确的二阶信息处理与BFGS拟牛顿更新之间无缝切换，从而在保证精度的同时提升计算效率。
•设计并实现了NeuroSQP这一完整的算法框架，其中包括基于神经预处理的内点二次规划求解器（NeuroIPM），以及与之配合的重启GMRES算法。
•在CUTEst测试集上进行了大量数值实验，结果显示该方法的成功率很高，即便面对变量数量极为庞大的大规模问题也能成功求解，而其他竞争方法则往往无法完成此类任务。

本文的其余结构如下：第2节回顾了卡鲁什-库恩-塔克方程组以及传统约束预处理技术，这些内容为我们的神经网络方法提供了理论基础。第3节介绍了图神经网络及其在我们预处理策略中的应用方式。第4节描述了用于二次规划子问题的神经预处理内点求解器（NeuroIPM）。第5节详细阐述了完整的NeuroSQP算法，包括混合海森矩阵近似方法以及通过某种优度函数实现的全局化策略。第6节汇报了在CUTEst基准测试集上进行的全面数值实验结果。最后，第7节给出了总结性意见。