Research map / Learning theory and algorithms / Combinatorial and search optimization
Differentiation Through Black-Box Quadratic Programming Solvers
Read the paperCheck your idea against 108,967 papers
AI-extracted summary. Written by AI from the paper's full text. Numbers and claims can be wrong or missing context, so check the paper before you cite or build on it.
Introduces dQP, a solver-agnostic differentiable QP layer that uses the active set to reduce the KKT system to a symmetric equality-constrained solve for both solution and derivatives, usable with any black-box QP solver via qpsolvers.
Problem
Differentiating the solution of quadratic programs with respect to their parameters is tied to specific integrated solvers, limiting use in neural layers and bi-level optimization, especially for large sparse problems.
Approach
Once the active inequality set is identified from any solver's primal solution, the QP is locally equivalent to an equality-constrained QP, so both the primal-dual solution and its derivatives follow from explicit linear systems sharing one symmetric KKT matrix; this decouples solving from differentiation.
Key results
- On 129 Maros-Meszaros problems, dQP (QPBenchmark-selected solver) solved all 129 with average total time 1467 ms and duality gap 7.39e-6, versus 77 for QPLayer and 38 for OptNet.
- On simplex projection at dimension 100000, dQP (Gurobi) total time 476.64 ms with duality gap 6.67e-10, while OptNet and QPLayer fail or are intractable at large sizes.
- dQP was fastest and most accurate in 97% and 93% of problems with dimension over 1000 on the Maros-Meszaros comparison.
Measured effects reported in the paper
| What was changed | Where | Measured | Effect |
|---|---|---|---|
| Use dQP with the best-performing QP solver selected per problem instead of the compared differentiable QP methods | Differentiable QP solving on the Maros-Meszaros dataset · Maros-Meszaros (MM), 129 sparse problems | problems solved: 129 vs 77 (QPLayer), 55 (SCQPTH), and 38 (OptNet) | Helped |
| Use dQP with the best-performing QP solver selected per problem instead of the compared differentiable QP methods | Differentiable QP solving on the Maros-Meszaros dataset · Maros-Meszaros (MM), full dataset | Avg Total [ms]: 1467 vs 15721 (QPLayer), 22895 (SCQPTH), and 41468 (OptNet) | Helped |
| Use dQP with the best-performing QP solver selected per problem instead of the compared differentiable QP methods | Differentiable QP solving on the Maros-Meszaros dataset · Maros-Meszaros (MM), full dataset | duality gap: 7.39 \times 10^{-6} vs 2.21 \times 10^{-2} (QPLayer), 2.36 \times 10^{-3} (OptNet), and 1.81 \times 10^{-2} (SCQPTH) | Helped |
| Use dQP instead of OptNet for probability simplex projection | Differentiable QP projection · Probability simplex projection, large problem sizes | Time [ms]: 476.64 vs 70856.43 at size 10000 (OptNet); OptNet failed at size 100000 | Helped |
| Use dQP instead of OptNet for chains projection | Differentiable QP projection · Chains projection, size 10000 | Time [ms]: 224.89 vs 571710.06 | Helped |
| Use dQP instead of OptNet for chains projection | Differentiable QP projection · Chains projection, size 10000 | Accuracy: 4.29 \times 10^{-5} vs 1.98 \times 10^{-7} | Mixed |
Surprising findings
- The reduced linear system after removing inactive constraints is often significantly better conditioned than the full KKT system.
Limitations
- No support for full parallelization or GPU acceleration.
- No special handling of infeasible QPs, unlike QPLayer.
- Active set identification via thresholding can be unstable near weakly active constraints; differentiation is ill-conditioned near non-differentiable points.
Experimental setup
Datasets: Maros-Meszaros
Benchmarks: Maros-Meszaros QP Benchmark
Metrics: total forward+backward time duality gap solved count
Baselines: OptNet QPLayer SCQPTH CVXPYLayers BPQP
Builds on: OptNet qpsolvers CVXPYLayers QPLayer BPQP
Closest papers by meaning
- Deep Distributed Optimization for Large-Scale Quadratic Programming (ICLR 2025 · similarity 0.88)
- Expressive Power of Graph Neural Networks for (Mixed-Integer) Quadratic Programs (ICML 2025 · similarity 0.86)
- DiLQR: Differentiable Iterative Linear Quadratic Regulator via Implicit Differentiation (ICML 2025 · similarity 0.85)
- BPQP: A Differentiable Convex Optimization Framework for Efficient End-to-End Learning (NeurIPS 2024 · similarity 0.85)
- Principled Data Augmentation for Learning to Solve Quadratic Programming Problems (NeurIPS 2025 · similarity 0.84)
- Learning Solution-Aware Transformers for Efficiently Solving Quadratic Assignment Problem (ICML 2024 · similarity 0.84)
Writing a paper in this area? scime draft is a free LaTeX editor with AI included, real-time co-authors and a check of your references and venue rules before you submit. It also imports OpenAI Prism projects.