Unrolled Graph Neural Networks for Constrained Optimization

• URL: http://arxiv.org/abs/2509.17156v1
• Date: Sun, 21 Sep 2025 16:55:41 GMT
• Title: Unrolled Graph Neural Networks for Constrained Optimization
• Authors: Samar Hadou, Alejandro Ribeiro,
• Abstract summary: We study the dynamics of the dual ascent algorithm in two coupled graph neural networks (GNNs)<n>We propose a joint training scheme that alternates between updating the primal and dual networks.<n>Our numerical experiments demonstrate that our approach yields near-optimal near-feasible solutions.
• Score: 83.29547301151177
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: 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.

Related papers

• Unrolled Neural Networks for Constrained Optimization [83.29547301151177]
  Our framework comprises two coupled neural networks that jointly approximate the saddle point of the Lagrangian.<n>We numerically evaluate the framework on mixed-integer quadratic programs and power allocation in wireless networks.
  arXiv  Detail & Related papers  (2026-01-24T03:12:41Z)
• Fast State-Augmented Learning for Wireless Resource Allocation with Dual Variable Regression [83.27791109672927]
  We show how a state-augmented graph neural network (GNN) parametrization for the resource allocation policy circumvents the drawbacks of the ubiquitous dual subgradient methods.<n>Lagrangian maximizing state-augmented policies are learned during the offline training phase.<n>We prove a convergence result and an exponential probability bound on the excursions of the dual function (iterate) optimality gaps.
  arXiv  Detail & Related papers  (2025-06-23T15:20:58Z)
• Exploring the loss landscape of regularized neural networks via convex duality [42.48510370193192]
  We discuss several aspects of the loss landscape of regularized neural networks.<n>We first characterize the solution set of the convex problem using its dual and further characterize all stationary points.<n>We show that the solution set characterization and connectivity results can be extended to different architectures.
  arXiv  Detail & Related papers  (2024-11-12T11:41:38Z)
• Convergence of Implicit Gradient Descent for Training Two-Layer Physics-Informed Neural Networks [4.554284689395686]
  implicit gradient descent (IGD) outperforms the common gradient descent (GD) algorithm in handling certain multi-scale problems.<n>We show that IGD converges to a globally optimal solution at a linear convergence rate.
  arXiv  Detail & Related papers  (2024-07-03T06:10:41Z)
• Network Interdiction Goes Neural [26.308933674471895]
  Network interdiction problems are optimization problems involving two players. One aims to solve an optimization problem on a network, while the other seeks to modify the network to thwart the first player's objectives.
  arXiv  Detail & Related papers  (2024-05-26T02:34:26Z)
• Stochastic Unrolled Federated Learning [85.6993263983062]
  We introduce UnRolled Federated learning (SURF), a method that expands algorithm unrolling to federated learning. Our proposed method tackles two challenges of this expansion, namely the need to feed whole datasets to the unrolleds and the decentralized nature of federated learning.
  arXiv  Detail & Related papers  (2023-05-24T17:26:22Z)
• Lower Bounds and Optimal Algorithms for Smooth and Strongly Convex Decentralized Optimization Over Time-Varying Networks [79.16773494166644]
  We consider the task of minimizing the sum of smooth and strongly convex functions stored in a decentralized manner across the nodes of a communication network. We design two optimal algorithms that attain these lower bounds. We corroborate the theoretical efficiency of these algorithms by performing an experimental comparison with existing state-of-the-art methods.
  arXiv  Detail & Related papers  (2021-06-08T15:54:44Z)
• Communication-Efficient Distributed Stochastic AUC Maximization with Deep Neural Networks [50.42141893913188]
  We study a distributed variable for large-scale AUC for a neural network as with a deep neural network. Our model requires a much less number of communication rounds and still a number of communication rounds in theory. Our experiments on several datasets show the effectiveness of our theory and also confirm our theory.
  arXiv  Detail & Related papers  (2020-05-05T18:08:23Z)

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.