Differentiation Through Black-Box Quadratic Programming Solvers

• URL: http://arxiv.org/abs/2410.06324v2
• Date: Thu, 10 Oct 2024 14:56:48 GMT
• Title: Differentiation Through Black-Box Quadratic Programming Solvers
• Authors: Connor W. Magoon, Fengyu Yang, Noam Aigerman, Shahar Z. Kovalsky,
• Abstract summary: We introduce dQP, a modular framework that enables plug-and-play differentiation for any quadratic programming (QP) solver. Our solution is based on the core theoretical insight that knowledge of the active constraint set at the QP optimum allows for explicit differentiation. Our implementation, which will be made publicly available, interfaces with an existing framework that supports over 15 state-of-the-art QP solvers.
• Score: 16.543673072027136
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In recent years, many deep learning approaches have incorporated layers that solve optimization problems (e.g., linear, quadratic, and semidefinite programs). Integrating these optimization problems as differentiable layers requires computing the derivatives of the optimization problem's solution with respect to its objective and constraints. This has so far prevented the use of state-of-the-art black-box numerical solvers within neural networks, as they lack a differentiable interface. To address this issue for one of the most common convex optimization problems -- quadratic programming (QP) -- we introduce dQP, a modular framework that enables plug-and-play differentiation for any QP solver, allowing seamless integration into neural networks and bi-level optimization tasks. Our solution is based on the core theoretical insight that knowledge of the active constraint set at the QP optimum allows for explicit differentiation. This insight reveals a unique relationship between the computation of the solution and its derivative, enabling efficient differentiation of any solver, that only requires the primal solution. Our implementation, which will be made publicly available, interfaces with an existing framework that supports over 15 state-of-the-art QP solvers, providing each with a fully differentiable backbone for immediate use as a differentiable layer in learning setups. To demonstrate the scalability and effectiveness of dQP, we evaluate it on a large benchmark dataset of QPs with varying structures. We compare dQP with existing differentiable QP methods, demonstrating its advantages across a range of problems, from challenging small and dense problems to large-scale sparse ones, including a novel bi-level geometry optimization problem.

Related papers

• WANCO: Weak Adversarial Networks for Constrained Optimization problems [5.257895611010853]
  We first transform minimax problems into minimax problems using the augmented Lagrangian method. We then use two (or several) deep neural networks to represent the primal and dual variables respectively. The parameters in the neural networks are then trained by an adversarial process.
  arXiv  Detail & Related papers  (2024-07-04T05:37:48Z)
• Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem [27.33966993065248]
  This work focuses on learning-based solutions for efficiently solving the Quadratic Assignment Problem (QAPs) Current research on QAPs suffer from limited scale and inefficiency. We propose the first solution of its kind for QAP in the learn-to-improve category.
  arXiv  Detail & Related papers  (2024-06-14T10:15:03Z)
• Optimized QUBO formulation methods for quantum computing [0.4999814847776097]
  We show how to apply our techniques in case of an NP-hard optimization problem inspired by a real-world financial scenario. We follow by submitting instances of this problem to two D-wave quantum annealers, comparing the performances of our novel approach with the standard methods used in these scenarios.
  arXiv  Detail & Related papers  (2024-06-11T19:59:05Z)
• 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)
• Backpropagation of Unrolled Solvers with Folded Optimization [55.04219793298687]
  The integration of constrained optimization models as components in deep networks has led to promising advances on many specialized learning tasks. One typical strategy is algorithm unrolling, which relies on automatic differentiation through the operations of an iterative solver. This paper provides theoretical insights into the backward pass of unrolled optimization, leading to a system for generating efficiently solvable analytical models of backpropagation.
  arXiv  Detail & Related papers  (2023-01-28T01:50:42Z)
• Learning differentiable solvers for systems with hard constraints [48.54197776363251]
  We introduce a practical method to enforce partial differential equation (PDE) constraints for functions defined by neural networks (NNs) We develop a differentiable PDE-constrained layer that can be incorporated into any NN architecture. Our results show that incorporating hard constraints directly into the NN architecture achieves much lower test error when compared to training on an unconstrained objective.
  arXiv  Detail & Related papers  (2022-07-18T15:11:43Z)
• A Constrained Optimization Approach to Bilevel Optimization with Multiple Inner Minima [49.320758794766185]
  We propose a new approach, which convert the bilevel problem to an equivalent constrained optimization, and then the primal-dual algorithm can be used to solve the problem. Such an approach enjoys a few advantages including (a) addresses the multiple inner minima challenge; (b) fully first-order efficiency without Jacobian computations.
  arXiv  Detail & Related papers  (2022-03-01T18:20:01Z)
• Message Passing Neural PDE Solvers [60.77761603258397]
  We build a neural message passing solver, replacing allally designed components in the graph with backprop-optimized neural function approximators. We show that neural message passing solvers representationally contain some classical methods, such as finite differences, finite volumes, and WENO schemes. We validate our method on various fluid-like flow problems, demonstrating fast, stable, and accurate performance across different domain topologies, equation parameters, discretizations, etc., in 1D and 2D.
  arXiv  Detail & Related papers  (2022-02-07T17:47:46Z)
• Efficient differentiable quadratic programming layers: an ADMM approach [0.0]
  We present an alternative network layer architecture based on the alternating direction method of multipliers (ADMM) Backward differentiation is performed by implicit differentiation of the residual map of a modified fixed-point iteration. Simulated results demonstrate the computational advantage of the ADMM layer, which for medium scaled problems is approximately an order of magnitude faster than the OptNet quadratic programming layer.
  arXiv  Detail & Related papers  (2021-12-14T15:25:07Z)
• Physics and Equality Constrained Artificial Neural Networks: Application to Partial Differential Equations [1.370633147306388]
  Physics-informed neural networks (PINNs) have been proposed to learn the solution of partial differential equations (PDE) Here, we show that this specific way of formulating the objective function is the source of severe limitations in the PINN approach. We propose a versatile framework that can tackle both inverse and forward problems.
  arXiv  Detail & Related papers  (2021-09-30T05:55:35Z)
• Efficient and Modular Implicit Differentiation [68.74748174316989]
  We propose a unified, efficient and modular approach for implicit differentiation of optimization problems. We show that seemingly simple principles allow to recover many recently proposed implicit differentiation methods and create new ones easily.
  arXiv  Detail & Related papers  (2021-05-31T17:45:58Z)

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.