Unrolled Graph Neural Networks for Constrained Optimization
This work addresses constrained optimization for applications requiring graph-based solutions, but it is incremental as it builds on existing dual ascent and GNN methods.
The paper tackles constrained optimization problems by unrolling the dual ascent algorithm into two coupled graph neural networks that interact to find saddle points of the Lagrangian, resulting in near-optimal near-feasible solutions with good generalization to out-of-distribution problems.
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.