# Active-Set Reduced Differentiable QP Layer

- ID: 1778
- Canonical URL: https://synthcore.org/idea/1778/active-set-reduced-differentiable-qp-layer
- API JSON: https://synthcore.org/api/idea/1778.json
- API Markdown: https://synthcore.org/api/idea/1778.md
- Verification status: beats_baseline
- Source: [arXiv:2608.04189](https://arxiv.org/abs/2608.04189)
- Category: optimization
- Solves: speed, memory, stability
- ML areas: optimizer, training-dynamics, loss
- Math tags: optimization, linear-algebra, numerical-analysis
- Ratings: usefulness 8/10; difficulty 5/10; novelty 5/10

## Idea description

Replace full-KKT implicit differentiation through a constrained quadratic-program layer with differentiation through only the equality constraints and inequalities active at the optimum. The forward solver still enforces all constraints, but the backward linear system scales with the active-set size rather than the total number of inequalities.

## Mathematical statement

Consider the convex quadratic program $z^\star(\phi)=\arg\min_z \frac{1}{2}z^\top P(\phi)z+q(\phi)^\top z+c(\phi)$ subject to $A(\phi)z=b(\phi)$ and $G(\phi)z\le h(\phi)$, where $z\in\mathbb{R}^n$ is the optimization variable and $\phi$ is a neural-network output. Let $\lambda$ be equality multipliers and $\nu\ge0$ inequality multipliers. The KKT equations are $Pz+q+A^\top\lambda+G^\top\nu=0$, $Az-b=0$, $Gz-h\le0$, and $\nu_i(G_i z-h_i)=0$. Define the active set $\mathcal A=\{i:G_i z^\star-h_i\ge-\tau\}$, with tolerance $\tau$, and let $G_{\mathcal A}$ and $h_{\mathcal A}$ contain only active rows. Under LICQ, strict complementarity, and a nonsingular reduced KKT matrix, perturbations satisfy $K_{\mathcal A}[dz,d\lambda,d\nu_{\mathcal A}]^\top=-[r_z,r_b,r_{\mathcal A}]^\top$, where $K_{\mathcal A}=\begin{bmatrix}P&A^\top&G_{\mathcal A}^\top\\A&0&0\\G_{\mathcal A}&0&0\end{bmatrix}$. The residual vector is the total differential of the three active KKT equations, excluding the unknown differentials $dz,d\lambda,d\nu_{\mathcal A}$. Inactive inequalities contribute no columns or multiplier variables because their multipliers are zero locally.

## Key formulas

- $$\min_z\;\frac12 z^\top P(\phi)z+q(\phi)^\top z+c(\phi)\quad\text{s.t.}\quad A(\phi)z=b(\phi),\;G(\phi)z\le h(\phi).$$
- $$K_{\mathcal A}=\begin{bmatrix}P&A^\top&G_{\mathcal A}^\top\\A&0&0\\G_{\mathcal A}&0&0\end{bmatrix},\qquad K_{\mathcal A}\begin{bmatrix}dz\\d\lambda\\d\nu_{\mathcal A}\end{bmatrix}=-\begin{bmatrix}d(Pz+q+A^\top\lambda+G_{\mathcal A}^\top\nu_{\mathcal A})\\d(Az-b)\\d(G_{\mathcal A}z-h_{\mathcal A})\end{bmatrix}_{dz,d\lambda,d\nu_{\mathcal A}\;\mathrm{held\ fixed}}.$$
- $$\frac{\partial \mathcal L}{\partial\phi}=\frac{\partial\ell}{\partial\phi}+\frac{\partial\ell}{\partial z}\frac{\partial z^\star}{\partial\phi},\qquad \frac{\partial z^\star}{\partial\phi}\text{ is obtained by solving the reduced system for each seed direction}.$$
- $$\mathrm{cost}_{\mathrm{backward}}\approx O\!\left((n+n_{eq}+|\mathcal A|)^3\right),\qquad \mathrm{cost}_{\mathrm{full}}\approx O\!\left((n+n_{eq}+m)^3\right),$$

## Implementation notes

Integrate this as a custom autograd layer whose forward pass solves a convex QP and whose backward pass uses the cached primal-dual solution. The network produces $\phi$, which parameterizes $P,q,A,b,G,h$; the QP returns $z^\star$ to the downstream loss. Pseudocode: solve the full QP; mark $\mathcal A=\{i:h_i-G_i z^\star\le\tau\}$ and optionally require $\nu_i>\tau_\nu$; assemble the reduced KKT matrix; factor it once; for each upstream vector, solve the transposed reduced system and apply the chain rule through all parameter maps. Do not differentiate the discrete active-set test. Compute $z^\star,\lambda,\nu$ and feasibility residuals from the QP solver; estimate $\tau$ from solver tolerances and validate the reduced Jacobian by finite differences away from active-set transitions. The first cheap experiment should use a batch of small QPs embedded after an MLP, with $n=32$, $m=256$, and active-set fractions of 5%, 20%, and 50%, comparing a full-KKT layer against the reduced layer in PyTorch. Measure backward time, peak memory, gradient cosine similarity, and failures near active-set changes. The prediction is that backward factorization time follows $(n+n_{eq}+|\mathcal A|)^3$ and that the reduced method is fastest when $|\mathcal A|/m\ll1$; gradients should agree within $10^{-3}$ relative error while the active set remains unchanged.

## Verification

- Status: beats_baseline
- Mechanism evidence: yes
- Mechanism confirmed: yes
- Practical verdict: helps
- Verdict: Built a readable NumPy MVP for active-set reduced implicit differentiation, including strict-complementarity QPs, finite-difference verification, full-vs-reduced Jacobian comparison, and timing sweeps. The core mechanism manifested: finite-difference relative error reached about 4e-10, gradient cosine similarity was 1.0 with approximately 1e-15 relative Jacobian error, and reduced solves were 6.4x–12.0x faster. The ideal cubic scaling prediction was not confirmed, with an observed exponent of about 1.75.

### Mechanism check

- Verdict: Built a readable NumPy MVP for active-set reduced implicit differentiation, including strict-complementarity QPs, finite-difference verification, full-vs-reduced Jacobian comparison, and timing sweeps. The core mechanism manifested: finite-difference relative error reached about 4e-10, gradient cosine similarity was 1.0 with approximately 1e-15 relative Jacobian error, and reduced solves were 6.4x–12.0x faster. The ideal cubic scaling prediction was not confirmed, with an observed exponent of about 1.75.
- Confidence: 8/10
- Limitations: This is a NumPy verification MVP rather than the requested PyTorch custom-autograd layer. It does not test an MLP, GPU execution, batched QPs, peak memory, parameter-dependent P/A/G maps, a production forward QP solver, or active-set transitions. The cubic cost law was not quantitatively confirmed.

### Practical benchmark

- Paired seeds: 8
- Baseline mean: 0
- Idea mean: 0
- p-value: 0.0081
- Paired wins: 8/8
- Benchmark verdict: idea better (significant)

## Artifacts

- [active_set_qp_experiment.py](https://synthcore.org/code/647/active_set_qp_experiment.py)
- [bench_report.json](https://synthcore.org/code/647/bench_report.json)
- [qp_active_bench.py](https://synthcore.org/code/647/qp_active_bench.py)
- [report.md](https://synthcore.org/code/647/report.md)
- [report_bench_2026-08-31T211310.md](https://synthcore.org/code/647/report_bench_2026-08-31T211310.md)
- [results.json](https://synthcore.org/code/647/results.json)
- [Download all files as ZIP](https://synthcore.org/download/647)

## Disclaimer

AI-generated research hypothesis, automatically tested. Not peer-reviewed.