用双图神经网络模拟对偶上升法，解约束优化问题。
Unrolled Graph Neural Networks for Constrained Optimization
- 用两个耦合GNN模拟对偶上升算法的迭代过程
- 在测试中得到近优且近可行的解，泛化能力好
- 适合解决需要强鲁棒性的优化类任务
本文将对偶上升（DA）算法的动力学过程展开为两个耦合的图神经网络（GNN），用于求解约束优化问题。这两个网络在层间相互作用，以寻找拉格朗日函数的鞍点。原始网络在给定对偶乘子时找到一个驻点，而对偶网络则不断更新估计值以逼近最优解。通过施加下降与上升约束，强制使原始与对偶网络镜像匹配DA算法的动力学行为。我们提出一种交替更新原始与对偶网络的联合训练方案。数值实验表明，该方法可获得近优且近可行的解，并在分布外（OOD）问题上具有良好泛化性。
原文摘要 · Abstract (English)
In this paper, we unroll the dynamics of the dual ascent (DA) algorithm in two coupled graph neural networks (GNNs) to solve constrained optimization problems. The two networks interact with each other at the layer level to find a saddle point of the Lagrangian. The primal GNN finds a stationary point for a given dual multiplier, while the dual network iteratively refines its estimates to reach an optimal solution. We force the primal and dual networks to mirror the dynamics of the DA algorithm by imposing descent and ascent constraints. We propose a joint training scheme that alternates between updating the primal and dual networks. Our numerical experiments demonstrate that our approach yields near-optimal near-feasible solutions and generalizes well to out-of-distribution (OOD) problems.
Thank you to arXiv for use of its open access interoperability. PaperDance 不是 arXiv 官方产品；中文卡片由大模型生成，请以原文为准。