A Penalty Approach for Differentiation Through Black-Box Quadratic Programming Solvers

• URL: http://arxiv.org/abs/2602.14154v1
• Date: Sun, 15 Feb 2026 14:05:36 GMT
• Title: A Penalty Approach for Differentiation Through Black-Box Quadratic Programming Solvers
• Authors: Yuxuan Linghu, Zhiyuan Liu, Qi Deng,
• Abstract summary: dXPP is a penalty-based differentiation framework that decouples QP solving from differentiation.<n>We evaluate dXPP on various tasks, including randomly generated QPs, large-scale sparse projection problems, and a real-world portfolio optimization task.
• Score: 29.582959310549594
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Differentiating through the solution of a quadratic program (QP) is a central problem in differentiable optimization. Most existing approaches differentiate through the Karush--Kuhn--Tucker (KKT) system, but their computational cost and numerical robustness can degrade at scale. To address these limitations, we propose dXPP, a penalty-based differentiation framework that decouples QP solving from differentiation. In the solving step (forward pass), dXPP is solver-agnostic and can leverage any black-box QP solver. In the differentiation step (backward pass), we map the solution to a smooth approximate penalty problem and implicitly differentiate through it, requiring only the solution of a much smaller linear system in the primal variables. This approach bypasses the difficulties inherent in explicit KKT differentiation and significantly improves computational efficiency and robustness. We evaluate dXPP on various tasks, including randomly generated QPs, large-scale sparse projection problems, and a real-world multi-period portfolio optimization task. Empirical results demonstrate that dXPP is competitive with KKT-based differentiation methods and achieves substantial speedups on large-scale problems.

Related papers

• DInf-Grid: A Neural Differential Equation Solver with Differentiable Feature Grids [73.28614344779076]
  We present a differentiable grid-based representation for efficiently solving differential equations (DEs)<n>Our results demonstrate a 5-20x speed-up over coordinate-based methods, solving differential equations in seconds or minutes while maintaining comparable accuracy and compactness.
  arXiv  Detail & Related papers  (2026-01-15T18:59:57Z)
• Scalable h-adaptive probabilistic solver for time-independent and time-dependent systems [7.807210884802377]
  We develop an $h$-adaptive probabilistic solver that can scale to a large number of collocation points.<n>We demonstrate the efficacy of the proposed solver on benchmark PDEs, as well as a time-dependent parabolic PDE formulated in a space-time setting.
  arXiv  Detail & Related papers  (2025-08-13T08:54:18Z)
• Single-loop Algorithms for Stochastic Non-convex Optimization with Weakly-Convex Constraints [49.76332265680669]
  This paper examines a crucial subset of problems where both the objective and constraint functions are weakly convex.<n>Existing methods often face limitations, including slow convergence rates or reliance on double-loop designs.<n>We introduce a novel single-loop penalty-based algorithm to overcome these challenges.
  arXiv  Detail & Related papers  (2025-04-21T17:15:48Z)
• Differentiation Through Black-Box Quadratic Programming Solvers [21.717766458737426]
  Differentiable optimization has attracted significant research interest, particularly for quadratic programming (QP)<n>We introduce dQP, a modular and solver-agnostic framework for plug-and-play differentiation of virtually any QP solver.<n>Building on this result, we provide a minimal-overhead, open-source implementation that seamlessly integrates with over 15 state-of-the-art solvers.
  arXiv  Detail & Related papers  (2024-10-08T20:01:39Z)
• 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)
• 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)
• SCQPTH: an efficient differentiable splitting method for convex quadratic programming [1.3597551064547502]
  SCQPTH is a differentiable first-order splitting method for convex quadratic programs. The SCQPTH software is made available as an open-source python package. For large scale QPs, SCQPTH can provide a $1times - 10times$ improvement in computational efficiency.
  arXiv  Detail & Related papers  (2023-08-16T09:06:54Z)
• Unbalanced penalization: A new approach to encode inequality constraints of combinatorial problems for quantum optimization algorithms [42.29248343585333]
  We present an alternative method that does not require extra slack variables. We evaluate our approach on the traveling salesman problem, the bin packing problem, and the knapsack problem. This new approach can be used to solve problems with inequality constraints with a reduced number of resources.
  arXiv  Detail & Related papers  (2022-11-25T06:05:18Z)
• 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)
• Q-Match: Iterative Shape Matching via Quantum Annealing [64.74942589569596]
  Finding shape correspondences can be formulated as an NP-hard quadratic assignment problem (QAP) This paper proposes Q-Match, a new iterative quantum method for QAPs inspired by the alpha-expansion algorithm. Q-Match can be applied for shape matching problems iteratively, on a subset of well-chosen correspondences, allowing us to scale to real-world problems.
  arXiv  Detail & Related papers  (2021-05-06T17:59:38Z)
• Two-Stage Stochastic Optimization via Primal-Dual Decomposition and Deep Unrolling [86.85697555068168]
  Two-stage algorithmic optimization plays a critical role in various engineering and scientific applications. There still lack efficient algorithms, especially when the long-term and short-term variables are coupled in the constraints. We show that PDD-SSCA can achieve superior performance over existing solutions.
  arXiv  Detail & Related papers  (2021-05-05T03:36:00Z)
• GACEM: Generalized Autoregressive Cross Entropy Method for Multi-Modal Black Box Constraint Satisfaction [69.94831587339539]
  We present a modified Cross-Entropy Method (CEM) that uses a masked auto-regressive neural network for modeling uniform distributions over the solution space. Our algorithm is able to express complicated solution spaces, thus allowing it to track a variety of different solution regions.
  arXiv  Detail & Related papers  (2020-02-17T20:21:20Z)

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.