GPU加速全局求解器GEAR：用线性界传播破解非线性规划难题

从神经网络验证到非线性规划：GEAR的跨界灵感

全局非线性规划（NLP）是优化领域的硬骨头，传统求解器如Gurobi、BARON和SCIP在处理非凸约束时往往耗时巨大。一篇最新论文提出了一种名为GEAR的GPU加速全局求解器，其核心思路源于神经网络验证中的线性界传播（linear bound propagation）框架。在神经网络验证中，该框架已被证明能带来数量级的加速；GEAR将这一范式迁移到更复杂的NLP问题上，试图解决传统方法难以企及的挑战。

据论文描述，神经网络验证通常只处理结构良好的输入盒约束，且不直接优化目标函数；而全局NLP求解器必须有效利用所有可能非结构化的非线性约束来改进目标。GEAR通过充分挖掘界传播产生的线性界来弥合这一差距——这些线性界可视为非线性约束的松弛，用于提供下界、检测不可行性并引导原始解的搜索。

线性界传播（Linear Bound Propagation） 是神经网络形式化验证中的一项核心技术，用于计算神经网络输出相对于输入扰动的安全边界。其基本思想是：给定输入层的一个区间约束（如 (x \in [l, u])），逐层传播线性上下界，最终得到输出层的区间界。具体而言，对于每一层，它利用激活函数的线性松弛（例如 ReLU 的三角形松弛）和权重矩阵的区间运算，将前一层的界传播到下一层。由于整个过程仅涉及矩阵乘法和逐元素运算，计算复杂度与网络前向传播相当，且高度可并行化，因此在大规模网络上可实现数量级加速。该框架已在 ERAN、CROWN 等验证工具中得到广泛应用。

线性界传播如何用于全局优化

GEAR的关键创新在于将线性界传播的全过程与全局求解流程深度耦合。具体而言，线性界被用作非线性约束的松弛，从而为分支定界提供下界；当界传播检测到某个子区域不可行时，可以安全剪枝；同时，这些界还能引导原始启发式搜索，帮助快速找到可行解。

为了处理NLP中常见的双线性、商函数等复杂非线性项，作者提出了更紧的线性松弛方法。这些改进使得线性界传播能够适用于更广泛的函数类型，而不是局限于神经网络验证中常见的简单激活函数。

此外，GEAR还设计了一种投影增广拉格朗日方法，与对偶求解过程紧密耦合，用于生成原始解。这种耦合确保了原始和对偶信息的高效交互，避免了传统方法中原始-对偶迭代分离带来的额外开销。

分支定界（Branch-and-Bound） 是全局优化中最经典的精确算法框架。其核心流程是：将原问题松弛为一个更易求解的子问题（通常为线性规划或凸松弛），求解松弛得到下界；若下界大于当前已知可行解的目标值（上界），则该子区域不可能包含更优解，可安全剪枝；否则，将区域分支为更小的子区域并递归处理。分支定界的效率高度依赖于松弛的紧致程度——松弛越紧，下界越接近真实最优值，剪枝越有效。GEAR 将线性界传播作为松弛手段，正是利用了其能产生较紧线性界的特点，从而为分支定界提供高质量的下界。

投影增广拉格朗日方法（Projected Augmented Lagrangian） 是一类用于求解约束优化问题的算法，特别适用于非线性规划。增广拉格朗日方法在拉格朗日函数基础上增加一个惩罚项（通常为二次项），以处理约束并改善收敛性。其基本迭代包括：固定拉格朗日乘子，求解无约束（或简单约束）子问题以更新原始变量；然后更新乘子。投影操作则用于处理变量上的简单盒约束，即在每步迭代后将变量投影回可行域。GEAR 将该方法与对偶求解过程紧密耦合，使得原始解生成与对偶界计算同步进行，避免了传统方法中原始-对偶迭代分离带来的额外开销。

基准测试结果：超越商业与开源求解器

在GAMS和MINLPLib基准测试集上，GEAR在180秒限制内求解了505个有界连续NLP问题中的421个。论文称，这一成绩超过了其对比的六种全局求解器，包括商业求解器Gurobi和BARON，以及开源求解器SCIP。

一个值得关注的细节是，有16个问题没有任何对比求解器能够证明其全局最优性，而GEAR成功求解了它们。这些问题都包含指数、对数或三角函数项，正是传统方法经常遇到困难的领域。这暗示GEAR的线性松弛技术对这些超越函数具有更好的适应性。

不过，论文并未提供与每个求解器逐一对比的详细数据，也没有给出平均求解时间或相对加速比的具体数字。因此，对于GEAR在实际应用中的性能优势，仍需更多独立复现和测试来验证。

技术细节与潜在影响

GEAR的另一个亮点是利用GPU加速。线性界传播本质上是高度并行的操作，适合在GPU上批量处理。虽然论文摘要未透露具体实现细节，但可以推测GEAR通过大规模并行计算显著提升了界传播的效率，从而在相同时间内探索更多分支。

从更广的视角看，GEAR展示了跨领域方法迁移的价值：神经网络验证中的高效技术经过改造后，可以用于解决经典的运筹学问题。这种思路可能启发更多研究，将机器学习社区的工具引入传统优化领域。

当然，GEAR目前仅针对有界连续NLP问题，且测试集规模有限。对于混合整数非线性规划、大规模稀疏问题或实际工业场景中的复杂约束，其表现仍有待检验。但无论如何，GEAR为GPU加速全局优化提供了一个有前景的方向。

项目网页已公开，包含更多实现细节和实验结果，感兴趣的读者可以进一步查阅。