Solving Quadratic Programs with Slack Variables via ADMM without Increasing the Problem Size

Brian Plancher; John Subosits; Marcus Greiff; Thomas Lew

arxiv: 2511.08451 · v2 · submitted 2025-11-11 · 🧮 math.OC · cs.SY· eess.SY

Solving Quadratic Programs with Slack Variables via ADMM without Increasing the Problem Size

Thomas Lew , Marcus Greiff , John Subosits , Brian Plancher This is my paper

Pith reviewed 2026-05-17 23:29 UTC · model grok-4.3

classification 🧮 math.OC cs.SYeess.SY

keywords ADMMquadratic programmingslack variablesproximal methodsconstrained optimizationfeasibilitynumerical algorithms

0 comments

The pith

A modified ADMM projection step solves quadratic programs with implicit slack variables without enlarging the problem.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper shows how to handle potentially infeasible quadratic programs inside the alternating direction method of multipliers by adjusting only the projection inside the z-update. Standard practice adds explicit slack variables to restore feasibility, but that enlarges the matrices and slows each iteration. The authors prove that the altered projection produces exactly the same sequence of iterates and the same convergence properties as the version that explicitly augments the problem with slacks. Because the original problem size stays unchanged, the method runs faster while retaining all theoretical guarantees of the slack-augmented formulation.

Core claim

Altering only the projection that appears in the z-update of the standard ADMM algorithm for a quadratic program makes the resulting iterates and convergence behavior identical to those of ADMM applied to the same program after slack variables have been added explicitly.

What carries the argument

A modified projection operator inside the z-update of ADMM that implicitly enforces the effect of slack variables.

If this is right

The new scheme produces exactly the same sequence of iterates as the slack-augmented ADMM.
All convergence guarantees already known for the augmented formulation transfer directly.
Problem dimension and matrix sizes remain those of the original QP.
Numerical experiments confirm measurable speedups on benchmark instances.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

Existing ADMM implementations can adopt the change with a single-line modification to the projection routine.
The same projection adjustment may extend to other proximal algorithms that currently rely on explicit slack augmentation.
Real-time applications such as model-predictive control could benefit from the reduced per-iteration cost.

Load-bearing premise

Changing only the z-update projection produces identical iterates and convergence behavior to the version of the algorithm that adds slack variables explicitly.

What would settle it

Run both the proposed method and standard ADMM on the same QP with added slacks and check whether every iterate matches to machine precision.

Figures

Figures reproduced from arXiv: 2511.08451 by Brian Plancher, John Subosits, Marcus Greiff, Thomas Lew.

**Figure 1.** Figure 1: Smoothed indicator function and projection operator. 3) dual update: update the KKT multipliers via µ = µ + ρ(Ax − z) = (8). This proposed ADMM scheme is more computationally and memory efficient than the standard ADMM scheme for solving QPslack (Section II-B), thanks to the xupdate. Indeed, the only difference with the ADMM scheme for solving QP (without slack variables ξ) is using a smoothed projection … view at source ↗

**Figure 2.** Figure 2: Residuals across ADMM iterates for the feasible (top) and infeasible QPs (bottom): median over 100 MPC problem instances, with ±2 standard deviations. • Feasible QPs: We sample the initial states xs strictly inside the box constraints [x, x] as in [10]. • Infeasible QPs: We sample the initial states xs strictly outside the box constraints [x, x] as xs ∼ (1 + w)x with w uniformly-distributed in [0, 1]. Thes… view at source ↗

**Figure 3.** Figure 3: Solve times and speedups (ratio SolveTime(ADMM) / SolveTime(ADMMSlack) ) for the feasible (top) and infeasible QPs (bottom) for different exit tolerances: median over 100 MPC problem instances with ±2 standard deviations. a similar number of iterations to reach a desired exit tolerance for these problems. B. ADMMSlack is faster We vary the exit tolerance ϵ and the state and control dimensions dim(xk) = … view at source ↗

read the original abstract

Proximal methods such as the Alternating Direction Method of Multipliers (ADMM) are effective at solving constrained quadratic programs (QPs). To tackle infeasible QPs, slack variables are often introduced to ensure feasibility, which changes the structure of the problem, increases its size, and slows down numerical resolution. In this letter, we propose a simple ADMM scheme to tackle QPs with slack variables without increasing the size of the original problem. The only modification is a slightly different projection in the z-update, while the rest of the algorithm remains standard. We prove that the method is equivalent to applying ADMM to the QP with additional slack variables, even though slack variables are not added. Numerical experiments show speedups of the approach.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The paper gives a modified ADMM for QPs that handles slack variables implicitly by changing only the z-projection step and claims this is equivalent to the standard augmented formulation without growing the problem size.

read the letter

The main thing to know is that this work shows how to run ADMM on a QP with implicit slack handling for infeasibility by altering just the projection in the z-update while leaving the x-update and dual step standard. They prove equivalence to the version that explicitly adds slacks, which avoids the usual increase in dimension and matrix size. That is the concrete contribution here, and it lines up with the numerical speedups they report in the experiments. The approach stays close to existing ADMM code, so the implementation change is small. This is useful for settings like real-time control where QPs need to stay compact. The proof of equivalence is the part that carries the weight, and the experiments give some evidence that the speed gain is real on the test cases they chose. The soft spot is whether the modified projection preserves the exact sequence of primal and dual iterates all the way through, not just the limit point. The derivation needs to be checked for how it interacts with the dual ascent when inequalities are present; if any step in that chain is approximate, the iterates could drift even if the fixed point matches. The abstract presents the proof as direct, so the paper stands or falls on the details of that argument. This is aimed at readers who already implement or tune ADMM solvers for constrained quadratic programs in robotics or embedded optimization. Someone looking for a drop-in change to reduce problem size would find it practical. It has enough of a proof and some reproducible speed claims to merit sending to referees rather than a desk reject, even if the equivalence needs careful verification in review.

Referee Report

2 major / 2 minor

Summary. The manuscript proposes an ADMM variant for quadratic programs (QPs) that handles infeasibility via slack variables without augmenting the problem dimension. The sole algorithmic change is a modified projection operator in the z-update; the x-update and dual update remain standard. The central claim is a proof that this yields iterates and convergence behavior identical to those of ADMM applied to the explicitly slack-augmented QP. Numerical experiments report speedups relative to the augmented formulation.

Significance. If the equivalence holds for both equality and inequality constraints and the full primal-dual trajectories match, the result would allow practitioners to obtain the benefits of slack variables (feasibility recovery) at the computational cost of the original-sized QP. This is particularly relevant for large-scale or real-time QP solvers where dimension increase is prohibitive. The parameter-free nature of the modification and the reported speedups strengthen its practical value.

major comments (2)

[§3] §3 (Equivalence proof): The derivation of the modified z-projection must explicitly verify that the dual-ascent step produces identical multipliers to the augmented formulation. Because the slack variables are eliminated analytically, the interaction between the augmented quadratic term and the dual update must be shown to cancel exactly; otherwise the sequences diverge even if the fixed point is the same.
[§4.2] §4.2 (Numerical validation): The experiments compare solve times and final objective values but do not report the norm of the difference between the proposed iterates and those of the slack-augmented ADMM at each iteration. Without this check, it remains unclear whether the claimed equivalence holds throughout the trajectory or only at convergence.

minor comments (2)

[§2.3] The projection formula in the z-update should be stated as an explicit operator (e.g., Eq. (12)) rather than described only in prose, to facilitate direct implementation and verification.
[§3] Clarify whether the equivalence extends to the case of inequality constraints with nonzero lower bounds; the current statement appears to assume the standard nonnegativity slack form.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We are grateful to the referee for the insightful comments on the equivalence proof and numerical experiments. Below we address each point and outline the planned revisions to the manuscript.

read point-by-point responses

Referee: §3 (Equivalence proof): The derivation of the modified z-projection must explicitly verify that the dual-ascent step produces identical multipliers to the augmented formulation. Because the slack variables are eliminated analytically, the interaction between the augmented quadratic term and the dual update must be shown to cancel exactly; otherwise the sequences diverge even if the fixed point is the same.

Authors: In our proof of equivalence (Theorem 1), we show that the modified projection in the z-update exactly replicates the effect of the slack variables in the augmented QP. Because the x- and dual-updates are identical to those in the augmented formulation, and the z-update is constructed to yield the same z (after analytic elimination of slacks), the dual variables are identical by construction at every iteration. The cancellation of the augmented quadratic term with the projection adjustment is implicit in the derivation. To make this explicit as suggested, we will revise Section 3 to include a dedicated paragraph verifying the dual-ascent step. revision: yes
Referee: §4.2 (Numerical validation): The experiments compare solve times and final objective values but do not report the norm of the difference between the proposed iterates and those of the slack-augmented ADMM at each iteration. Without this check, it remains unclear whether the claimed equivalence holds throughout the trajectory or only at convergence.

Authors: We agree that an explicit comparison of the full trajectories would strengthen the validation of the equivalence claim. In the revised manuscript, we will include plots or tables reporting the norm of the difference between the iterates (including primal and dual variables) of the proposed method and the standard slack-augmented ADMM at each iteration for the numerical examples in Section 4.2. revision: yes

Circularity Check

0 steps flagged

No circularity: direct equivalence proof via modified projection operator

full rationale

The paper derives an equivalence between standard ADMM on the original QP and ADMM on the slack-augmented QP by analytically eliminating the slack variables from the z-update projection step. This is a self-contained algebraic reduction shown against the explicit augmented formulation; the iterates, dual updates, and fixed points are shown to match by direct substitution into the standard ADMM loop rather than by fitting parameters or invoking self-citations. No load-bearing step reduces to a definition of the target result or to a prior result by the same authors. The derivation is therefore independent of the claimed outcome.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The work rests on standard ADMM theory for quadratic programs and introduces a targeted modification to the projection operator; no new free parameters, invented entities, or ad-hoc axioms are introduced beyond the algorithmic change.

axioms (1)

standard math Standard convergence properties of ADMM for convex quadratic programs
The equivalence proof relies on known ADMM theory for QPs.

pith-pipeline@v0.9.0 · 5432 in / 1058 out tokens · 25976 ms · 2026-05-17T23:29:30.825883+00:00 · methodology

discussion (0)

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

IndisputableMonolith/Cost/FunctionalEquation.lean washburn_uniqueness_aczel unclear

?

unclear
Relation between the paper passage and the cited Recognition theorem.

The only modification is a slightly different projection in the z-update... z = gProj[ℓ,u](Ax + μ/ρ)

What do these tags mean?

matches: The paper's claim is directly supported by a theorem in the formal canon.
supports: The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends: The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses: The paper appears to rely on the theorem as machinery.
contradicts: The paper's claim conflicts with a theorem or certificate in the canon.
unclear: Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

15 extracted references · 15 canonical work pages

[1]

Robust optimization for MPC,

B. Houska and M. E. Villanueva, “Robust optimization for MPC,” inHandbook of Model Predictive Control. Springer International Publishing, 2018, pp. 413–443

work page 2018
[2]

Cerberus in the DARPA Subterranean Challenge,

M. Tranzatto, T. Miki, M. Dharmadhikari, L. Bernreiter, M. Kulkarni, F. Mascarich, O. Andersson, S. Khattak, M. Hut- ter, R. Siegwartet al., “Cerberus in the DARPA Subterranean Challenge,”Science Robotics, vol. 7, no. 66, p. eabp9742, 2022

work page 2022
[3]

Optimization-based control for dynamic legged robots,

P. M. Wensing, M. Posa, Y . Hu, A. Escande, N. Mansard, and A. Del Prete, “Optimization-based control for dynamic legged robots,”IEEE Transactions on Robotics, 2023

work page 2023
[4]

MPCGPU: Real-time nonlinear model predictive control through precondi- tioned conjugate gradient on the GPU,

E. Adabag, M. Atal, W. Gerard, and B. Plancher, “MPCGPU: Real-time nonlinear model predictive control through precondi- tioned conjugate gradient on the GPU,” inProc. IEEE Conf. on Robotics and Automation, 2024

work page 2024
[5]

Del Re, F

L. Del Re, F. Allgower, L. Glielmo, C. Guardiola, and I. Kol- manovsky,Automotive model predictive control. Springer, 2010

work page 2010
[6]

Risk-averse model predictive control for racing in adverse conditions,

T. Lew, M. Greiff, F. Djeumou, M. Suminaka, M. Thompson, and J. Subosits, “Risk-averse model predictive control for racing in adverse conditions,” inProc. IEEE Conf. on Robotics and Automation, 2025

work page 2025
[7]

Distributed MPC strategies with application to power system automatic generation control,

A. N. Venkat, I. A. Hiskens, J. B. Rawlings, and S. J. Wright, “Distributed MPC strategies with application to power system automatic generation control,”IEEE transactions on control systems technology, vol. 16, no. 6, pp. 1192–1206, 2008

work page 2008
[8]

Model predictive con- trol: A review of its applications in power electronics,

S. Vazquez, J. I. Leon, L. G. Franquelo, J. Rodriguez, H. A. Young, A. Marquez, and P. Zanchetta, “Model predictive con- trol: A review of its applications in power electronics,”IEEE industrial electronics magazine, vol. 8, no. 1, pp. 16–31, 2014

work page 2014
[9]

Dis- tributed optimization and statistical learning via the alternating direction method of multipliers,

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Dis- tributed optimization and statistical learning via the alternating direction method of multipliers,”Foundations and Trends® in Machine Learning, vol. 3, no. 1, pp. 1–122, 2011

work page 2011
[10]

OSQP: an operator splitting solver for quadratic programs,

B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, “OSQP: an operator splitting solver for quadratic programs,” Mathematical Programming Computation, vol. 12, no. 4, pp. 637–672, 2020

work page 2020
[11]

Conic opti- mization via operator splitting and homogeneous self-dual em- bedding,

B. O’donoghue, E. Chu, N. Parikh, and S. Boyd, “Conic opti- mization via operator splitting and homogeneous self-dual em- bedding,”Journal of Optimization Theory and Applications, vol. 169, no. 3, pp. 1042–1068, 2016

work page 2016
[12]

Relaxed logarithmic barrier function based model predictive control of linear systems,

C. Feller and C. Ebenbauer, “Relaxed logarithmic barrier function based model predictive control of linear systems,”IEEE Trans- actions on Automatic Control, vol. 62, no. 3, pp. 1223–1238, 2017

work page 2017
[13]

Relaxed recentered log-barrier function based nonlinear model predictive control,

T. A. Oancea, Y . Jiang, and C. N. Jones, “Relaxed recentered log-barrier function based nonlinear model predictive control,” inEuropean Control Conference, 2023

work page 2023
[14]

Proximal algorithms,

N. Parikh and S. Boyd, “Proximal algorithms,”Foundations and Trends in Optimization, vol. 1, no. 3, pp. 127–239, 2014

work page 2014
[15]

On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators,

J. Eckstein and D. P. Bertsekas, “On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators,”Mathematical Programming, vol. 55, no. 1-3, pp. 293–318, 1992

work page 1992

[1] [1]

Robust optimization for MPC,

B. Houska and M. E. Villanueva, “Robust optimization for MPC,” inHandbook of Model Predictive Control. Springer International Publishing, 2018, pp. 413–443

work page 2018

[2] [2]

Cerberus in the DARPA Subterranean Challenge,

M. Tranzatto, T. Miki, M. Dharmadhikari, L. Bernreiter, M. Kulkarni, F. Mascarich, O. Andersson, S. Khattak, M. Hut- ter, R. Siegwartet al., “Cerberus in the DARPA Subterranean Challenge,”Science Robotics, vol. 7, no. 66, p. eabp9742, 2022

work page 2022

[3] [3]

Optimization-based control for dynamic legged robots,

P. M. Wensing, M. Posa, Y . Hu, A. Escande, N. Mansard, and A. Del Prete, “Optimization-based control for dynamic legged robots,”IEEE Transactions on Robotics, 2023

work page 2023

[4] [4]

MPCGPU: Real-time nonlinear model predictive control through precondi- tioned conjugate gradient on the GPU,

E. Adabag, M. Atal, W. Gerard, and B. Plancher, “MPCGPU: Real-time nonlinear model predictive control through precondi- tioned conjugate gradient on the GPU,” inProc. IEEE Conf. on Robotics and Automation, 2024

work page 2024

[5] [5]

Del Re, F

L. Del Re, F. Allgower, L. Glielmo, C. Guardiola, and I. Kol- manovsky,Automotive model predictive control. Springer, 2010

work page 2010

[6] [6]

Risk-averse model predictive control for racing in adverse conditions,

T. Lew, M. Greiff, F. Djeumou, M. Suminaka, M. Thompson, and J. Subosits, “Risk-averse model predictive control for racing in adverse conditions,” inProc. IEEE Conf. on Robotics and Automation, 2025

work page 2025

[7] [7]

Distributed MPC strategies with application to power system automatic generation control,

A. N. Venkat, I. A. Hiskens, J. B. Rawlings, and S. J. Wright, “Distributed MPC strategies with application to power system automatic generation control,”IEEE transactions on control systems technology, vol. 16, no. 6, pp. 1192–1206, 2008

work page 2008

[8] [8]

Model predictive con- trol: A review of its applications in power electronics,

S. Vazquez, J. I. Leon, L. G. Franquelo, J. Rodriguez, H. A. Young, A. Marquez, and P. Zanchetta, “Model predictive con- trol: A review of its applications in power electronics,”IEEE industrial electronics magazine, vol. 8, no. 1, pp. 16–31, 2014

work page 2014

[9] [9]

Dis- tributed optimization and statistical learning via the alternating direction method of multipliers,

S. Boyd, N. Parikh, E. Chu, B. Peleato, and J. Eckstein, “Dis- tributed optimization and statistical learning via the alternating direction method of multipliers,”Foundations and Trends® in Machine Learning, vol. 3, no. 1, pp. 1–122, 2011

work page 2011

[10] [10]

OSQP: an operator splitting solver for quadratic programs,

B. Stellato, G. Banjac, P. Goulart, A. Bemporad, and S. Boyd, “OSQP: an operator splitting solver for quadratic programs,” Mathematical Programming Computation, vol. 12, no. 4, pp. 637–672, 2020

work page 2020

[11] [11]

Conic opti- mization via operator splitting and homogeneous self-dual em- bedding,

B. O’donoghue, E. Chu, N. Parikh, and S. Boyd, “Conic opti- mization via operator splitting and homogeneous self-dual em- bedding,”Journal of Optimization Theory and Applications, vol. 169, no. 3, pp. 1042–1068, 2016

work page 2016

[12] [12]

Relaxed logarithmic barrier function based model predictive control of linear systems,

C. Feller and C. Ebenbauer, “Relaxed logarithmic barrier function based model predictive control of linear systems,”IEEE Trans- actions on Automatic Control, vol. 62, no. 3, pp. 1223–1238, 2017

work page 2017

[13] [13]

Relaxed recentered log-barrier function based nonlinear model predictive control,

T. A. Oancea, Y . Jiang, and C. N. Jones, “Relaxed recentered log-barrier function based nonlinear model predictive control,” inEuropean Control Conference, 2023

work page 2023

[14] [14]

Proximal algorithms,

N. Parikh and S. Boyd, “Proximal algorithms,”Foundations and Trends in Optimization, vol. 1, no. 3, pp. 127–239, 2014

work page 2014

[15] [15]

On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators,

J. Eckstein and D. P. Bertsekas, “On the Douglas-Rachford splitting method and the proximal point algorithm for maximal monotone operators,”Mathematical Programming, vol. 55, no. 1-3, pp. 293–318, 1992

work page 1992