用图神经网络求解凸优化，保证解的可行性且速度超越传统求解器。
Towards graph neural networks for provably solving convex optimization problems
- 设计迭代式图神经网络框架，可模拟内点法求解带线性约束的二次问题。
- 在多个数据集上解的质量和可行性均优于现有神经基线，部分场景快于Gurobi。
- 适用于需严格可行解的场景，如支持向量机等实际优化任务。
近年来，消息传递图神经网络（MPNN）因其能捕捉变量-约束间交互，在组合与连续优化问题中展现出潜力。现有方法多用于近似求解或为传统求解器提供初始值，但在凸优化场景下常缺乏可行性保证。本文提出一种迭代式MPNN框架，可对凸优化问题提供可证明的可行性保障。首先，我们证明了MPNN可准确模拟标准内点法求解带线性约束的二次问题，涵盖支持向量机（SVM）等典型问题。其次，为确保可行性，引入一种从可行点出发、逐步限制搜索范围于可行域内的变体。实验表明，该方法在解的质量与可行性上优于现有神经基线，对未见问题规模具有良好泛化能力，部分情况下求解速度超过先进求解器Gurobi。
原文摘要 · Abstract (English)
Recently, message-passing graph neural networks (MPNNs) have shown potential for solving combinatorial and continuous optimization problems due to their ability to capture variable-constraint interactions. While existing approaches leverage MPNNs to approximate solutions or warm-start traditional solvers, they often lack guarantees for feasibility, particularly in convex optimization settings. Here, we propose an iterative MPNN framework to solve convex optimization problems with provable feasibility guarantees. First, we demonstrate that MPNNs can provably simulate standard interior-point methods for solving quadratic problems with linear constraints, covering relevant problems such as SVMs. Secondly, to ensure feasibility, we introduce a variant that starts from a feasible point and iteratively restricts the search within the feasible region. Experimental results show that our approach outperforms existing neural baselines in solution quality and feasibility, generalizes well to unseen problem sizes, and, in some cases, achieves faster solution times than state-of-the-art solvers such as Gurobi.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。