Towards graph neural networks for provably solving convex optimization problems

• URL: http://arxiv.org/abs/2502.02446v1
• Date: Tue, 04 Feb 2025 16:11:41 GMT
• Title: Towards graph neural networks for provably solving convex optimization problems
• Authors: Chendi Qian, Christopher Morris,
• Abstract summary: We propose an iterative MPNN framework to solve convex optimization problems with provable feasibility guarantees. Experimental results show that our approach outperforms existing neural baselines in solution quality and feasibility.
• Score: 5.966097889241178
• License:
• Abstract: 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.

Related papers

• Differentiable Projection-based Learn to Optimize in Wireless Network-Part I: Convex Constrained (Non-)Convex Programming [15.689556794350674]
  This paper addresses a class of (non-)feasible optimization problems subject to general convex constraints. Traditional convex optimization methods often struggle to efficiently handle these problems in their most general form.
  arXiv  Detail & Related papers  (2025-01-29T11:52:27Z)
• Annealing Machine-assisted Learning of Graph Neural Network for Combinatorial Optimization [2.0643665408482517]
  Annealing Machines (AM) have shown increasing capabilities in solving complex problems. Graph Neural Networks (GNN) have been recently adapted to solve problems. We propose a merging approach that aims at retaining both the accuracy exhibited by AMs and the representational flexibility and scalability of GNNs.
  arXiv  Detail & Related papers  (2025-01-10T10:36:46Z)
• A Primal-dual algorithm for image reconstruction with ICNNs [3.4797100095791706]
  We address the optimization problem in a data-driven variational framework, where the regularizer is parameterized by an input- neural network (ICNN) While gradient-based methods are commonly used to solve such problems, they struggle to effectively handle nonsmoothness. We show that a proposed approach outperforms subgradient methods in terms of both speed and stability.
  arXiv  Detail & Related papers  (2024-10-16T10:36:29Z)
• An Expandable Machine Learning-Optimization Framework to Sequential Decision-Making [0.0]
  We present an integrated prediction-optimization (PredOpt) framework to efficiently solve sequential decision-making problems. We address the key issues of sequential dependence, infeasibility, and generalization in machine learning (ML) to make predictions for optimal solutions to instances problems.
  arXiv  Detail & Related papers  (2023-11-12T21:54:53Z)
• Exploring the Power of Graph Neural Networks in Solving Linear Optimization Problems [5.966097889241178]
  graph neural networks (MPNNs) speed up solving mixed-integer optimization problems. We show that MPNNs' effectiveness in emulating linear optimization remain largely unclear. We highlight how MPNNs can serve as a lightweight proxy for solving linear optimization problems.
  arXiv  Detail & Related papers  (2023-10-16T17:31:25Z)
• Optimizing Solution-Samplers for Combinatorial Problems: The Landscape of Policy-Gradient Methods [52.0617030129699]
  We introduce a novel theoretical framework for analyzing the effectiveness of DeepMatching Networks and Reinforcement Learning methods. Our main contribution holds for a broad class of problems including Max-and Min-Cut, Max-$k$-Bipartite-Bi, Maximum-Weight-Bipartite-Bi, and Traveling Salesman Problem. As a byproduct of our analysis we introduce a novel regularization process over vanilla descent and provide theoretical and experimental evidence that it helps address vanishing-gradient issues and escape bad stationary points.
  arXiv  Detail & Related papers  (2023-10-08T23:39:38Z)
• A Stable and Scalable Method for Solving Initial Value PDEs with Neural Networks [52.5899851000193]
  We develop an ODE based IVP solver which prevents the network from getting ill-conditioned and runs in time linear in the number of parameters. We show that current methods based on this approach suffer from two key issues. First, following the ODE produces an uncontrolled growth in the conditioning of the problem, ultimately leading to unacceptably large numerical errors.
  arXiv  Detail & Related papers  (2023-04-28T17:28:18Z)
• Symmetric Tensor Networks for Generative Modeling and Constrained Combinatorial Optimization [72.41480594026815]
  Constrained optimization problems abound in industry, from portfolio optimization to logistics. One of the major roadblocks in solving these problems is the presence of non-trivial hard constraints which limit the valid search space. In this work, we encode arbitrary integer-valued equality constraints of the form Ax=b, directly into U(1) symmetric networks (TNs) and leverage their applicability as quantum-inspired generative models.
  arXiv  Detail & Related papers  (2022-11-16T18:59:54Z)
• Learning Proximal Operators to Discover Multiple Optima [66.98045013486794]
  We present an end-to-end method to learn the proximal operator across non-family problems. We show that for weakly-ized objectives and under mild conditions, the method converges globally.
  arXiv  Detail & Related papers  (2022-01-28T05:53:28Z)
• dNNsolve: an efficient NN-based PDE solver [62.997667081978825]
  We introduce dNNsolve, that makes use of dual Neural Networks to solve ODEs/PDEs. We show that dNNsolve is capable of solving a broad range of ODEs/PDEs in 1, 2 and 3 spacetime dimensions.
  arXiv  Detail & Related papers  (2021-03-15T19:14:41Z)
• Offline Model-Based Optimization via Normalized Maximum Likelihood Estimation [101.22379613810881]
  We consider data-driven optimization problems where one must maximize a function given only queries at a fixed set of points. This problem setting emerges in many domains where function evaluation is a complex and expensive process. We propose a tractable approximation that allows us to scale our method to high-capacity neural network models.
  arXiv  Detail & Related papers  (2021-02-16T06:04:27Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.