Towards graph neural networks for provably solving convex optimization problems
This work addresses the problem of ensuring feasibility in neural network-based solvers for convex optimization, which is incremental as it builds on existing MPNN methods by adding provable guarantees.
The authors tackled the lack of feasibility guarantees for graph neural networks in solving convex optimization problems by proposing an iterative MPNN framework that provably simulates interior-point methods and ensures feasibility. Their approach outperformed neural baselines in solution quality and feasibility, generalized to unseen problem sizes, and sometimes achieved faster solution times than Gurobi.
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.