Source-linked AI summary
Efficient ADMM for Soft-Constrained Quadratic Programs via Generalized Slack Projections
Roland Schwan, Thomas Lew, Brian Plancher
TL;DR
Soft-constrained QPs use slack variables for feasibility, but standard lifting adds decision variables and can enlarge the optimization problem. The method handles unconditional convex slack penalties, including all ℓk-norms, by modifying only ADMM’s slack projection without adding decision variables. The proposed ADMM approach outperforms all lifted formulations by up to 3.4×; in the building problem, it takes 5.1 ms versus 14.5 ms with lifting (2.83× longer).
Problem
Soft-constrained QPs use slack variables for feasibility, but standard lifting adds decision variables and can enlarge the optimization problem.
Source: §I · p. 1Method
The method handles unconditional convex slack penalties, including all ℓk-norms, by modifying only ADMM’s slack projection without adding decision variables.
Source: §I · p. 2, §III · pp. 3–4Results
The proposed ADMM approach outperforms all lifted formulations by up to 3.4×; in the building problem, it takes 5.1 ms versus 14.5 ms with lifting (2.83× longer).
Source: A. Random Sparse QPs · p. 5, B. Building Energy Management with… · p. 6Takeaways & Limitations
The approach retains the hard QP’s size across penalties while supporting mixed penalty functions in a building energy management problem.
Source: §I · p. 2, B. Building Energy Management with… · p. 6
Abstract
from arXiv · showhide
Quadratic programs (QPs) are a core building block in many applications. In practice, constraints are often softened with slack variables to guarantee feasibility. The standard approach tackles this by introducing additional decision variables, growing the resulting optimization problem. In this paper, we propose an Alternating Direction Method of Multipliers (ADMM) scheme for a broad class of convex slack penalty functions, including all $\ell_k$-norms, without increasing the problem size. The only change to the ADMM scheme is a modified slack projection function, while the remaining algorithm stays the same. We demonstrate our approach on numerical examples, showing significant speedups, and show its flexibility on an energy optimization problem.
I. INTRODUCTION
Quadratic programs are widely used, but constraints may become infeasible under model inaccuracies or sensor noise, motivating soft constraints. Standard lifting can enlarge the optimization problem; this paper extends ADMM to handle broad convex slack penalties by changing only the projection step.
I. INTRODUCTION
- Soft constraints use slack variables to preserve feasibility when hard constraints may fail under model inaccuracies or sensor noise.The penalty function determines how constraint violations are traded off.Source: §I · p. 1
- Lifting soft constraints can increase the KKT system order from n + p to n + p + 4m for m soft rows.For non-separable penalties such as ℓ∞, a shared slack can also couple MPC stages; non-squared Euclidean penalties require reformulation as a second-order cone program.Source: §I · pp. 1–2
- The paper extends ADMM from squared two-norm penalties to unconditional convex penalties, including all ℓk-norms and separable penalties with even convex components.The method changes only the slack projection and avoids introducing additional decision variables.Source: §I · p. 2
- Up to 3.4× speedup over lifting is reported on random sparse QPs.The paper also applies the approach to building energy management, where different penalty functions model different soft-constraint behaviors.Source: §I · p. 2
II. SOLVING QP WITH ADMM
The section presents the ADMM splitting used to solve a QP. It separates the cost and linear equalities from inequality constraints, then applies iterative updates; the standard lifted alternative adds decision variables and constraint rows.
II. SOLVING QP WITH ADMM
- The ADMM formulation introduces auxiliary variables to separate the cost and linear equalities from inequality constraints.An indicator function represents the constraint set in the reformulation.Source: §II · p. 2
- Each ADMM iteration applies updates to the primal variables and associated multipliers.The stated update sequence includes an (x~, z~) update and an (x, z) update.Source: §II · p. 2
- Standard lifting adds decision variables and constraint rows, increasing the KKT matrix size.Table I summarizes the resulting problem sizes.Source: §II · pp. 2–3, Table I · p. 2
III. ADMM FOR QPSLACK
The section adapts ADMM to soft-constrained QPs by eliminating slack variables and changing only the projection step. Under an unconditional convex penalty, the update uses the penalty’s proximal operator applied to the box-projection residual.
III. ADMM FOR QPSLACK
- The method assumes an unconditional, proper, closed, convex slack penalty with Φ(0) = 0; unconditionality means invariance to coordinatewise sign changes.This includes ℓk-norms and separable penalties with even convex component functions.Source: §III · p. 3
- Slack elimination replaces the hard box indicator with a relaxed indicator that accounts for the penalty required to bring a point into the box.The resulting relaxed indicator is convex, so the proximal objective has a unique minimizer.Source: §III · pp. 3–4
- The generalized slack projection adds proxΦ/ρ of the box-projection residual to the ordinary box projection.The residual is defined relative to the box projection; this expression supplies the modified ADMM projection step.Source: §III · p. 4
- The ADMM iterations retain their original form except for the projection step, and the KKT matrix remains unchanged, allowing its factorization to be reused.The additional per-iteration cost is one evaluation of proxΦ/ρ; the standard ADMM convergence guarantees carry over unchanged.Source: §III · p. 4
- The generalized projection recovers the standard projection for hard constraints, the smoothed projection for quadratic penalties, and the distance-function proximal operator for ℓ2 penalties.Closed-form proximal operators for other listed penalties are provided in the appendix.Source: §III · p. 4
IV. NUMERICAL RESULTS
The numerical evaluation has two parts: benchmarking against lifted standard-QP formulations and applying the approach to building energy management. The supplied passages describe the evaluation setup but give no outcome comparisons.
IV. NUMERICAL RESULTS
- The evaluation benchmarks the approach against lifting on randomly generated sparse QPs with different penalty functions.A second part applies mixed penalty functions to a building energy management problem.Source: §IV · p. 4
- The experiments use a modified OSQP implementation with added support for the penalty functions listed in the appendix.The implementation is in Python interfacing with native C code and is evaluated on a MacBook Pro with an M5 Pro processor and 48 GB of RAM.Source: §IV · p. 4
A. Random Sparse QPs
The random sparse QP benchmarks compare the proposed approach with explicit lifting across penalty functions. The proposed method is up to 3.4× faster, with speedups shaped by problem size and penalty.
A. Random Sparse QPs
- Each problem size and penalty uses 100 random instances with p = n constraints; the benchmark excludes ℓ2-norm penalties because the lifted formulation requires a second-order cone solver.Instances are constructed to be feasible, with active constraints at the optimum.Source: A. Random Sparse QPs · pp. 4–5
- Up to 3.4× faster than lifted formulations, the proposed approach avoids KKT-system growth and uses fewer ADMM iterations for every penalty except the quadratic one.Proximal evaluation time is negligible; iteration counts differ because the formulations induce different splittings and conditioning.Source: A. Random Sparse QPs · p. 5
- For ℓ1, elastic net, and Huber penalties, speedup peaks at medium sizes as setup overhead dominates small cases and original-problem factorization dominates large ones.For ℓ∞, lifting adds only one variable, but its iteration count grows rapidly with n.Source: A. Random Sparse QPs · p. 5
B. Building Energy Management with Mixed Penalties
The building-energy MPC case assigns different penalties to four groups of soft constraints. The resulting schedule exhibits distinct violation patterns and solves faster than the lifted QP.
B. Building Energy Management with Mixed Penalties
- The case study schedules two coupled thermal zones, HVAC, battery storage, and grid imports over 96 fifteen-minute steps.The building has a 20 kWh battery and an 8 kW grid contract limit.Source: B. Building Energy Management with… · pp. 5–6
- Across one day, comfort violations spread over many timesteps, the grid pays a peak-demand charge once, and elastic net yields sparse battery-health violations.The four groups use quadratic comfort, ℓ∞ grid-contract, elastic-net battery-health, and Huber HVAC-ramp penalties.Source: B. Building Energy Management with… · p. 6
- The proposed approach solves the problem in 5.1 ms, compared with 14.5 ms for the standard approach of lifting it to a QP, which takes 2.83× longer.Source: B. Building Energy Management with… · p. 6
APPENDIX I COMMON SLACK PENALTIES
The appendix summarizes common slack penalties through their standard-QP liftings and proximal operators, which define the generalized slack projection.
APPENDIX I COMMON SLACK PENALTIES
- Common penalties are listed with their lifting to a standard QP and their proximal operator, which defines the generalized slack projection.Because the penalties are unconditional, Lemma 1 and Theorem 1 apply.Source: Appendix I · p. 7
- For separable penalties built from an even function ϕ, the proximal operator applies componentwise.Source: Appendix I · p. 7
- Each additional decision variable or constraint adds one to the order of the KKT matrix; m denotes the number of soft constraints.Source: Appendix I · p. 7
A. Quadratic Penalty
The quadratic-penalty lifting relaxes a soft constraint by introducing a nonnegative slack variable with a linear cost.
A. Quadratic Penalty
- Lifting a soft constraint introduces a nonnegative variable s_i with cost αs_i, relaxing both bounds around a_i^T x.Because s_i appears on both sides, the two-sided constraint is split into one-sided constraints; s_i ≥ 0 adds another constraint.Source: A. Quadratic Penalty · p. 7
- The lifted constraint uses one additional variable and two additional constraints.Source: A. Quadratic Penalty · p. 7
D. Huber Penalty
The Huber penalty is described through a lifting that relaxes a soft constraint using two nonnegative decision variables.
- The Huber lifting uses nonnegative variables w_i and t_i to relax each soft constraint, adding two variables and two constraints.Source: D. Huber Penalty · p. 7
E. Infinity-Norm Penalty
The infinity-norm lifting uses one shared slack variable, while the Euclidean-norm lifting uses per-constraint slack variables and a second-order cone constraint.
E. Infinity-Norm Penalty
- The parameter κ can be computed by bisection, sorting |r| in O(p log p), or expected O(p) median-based selection.The cited options apply because the left-hand side of (43d) is piecewise linear and strictly decreasing on [0, ∥r∥∞].Source: E. Infinity-Norm Penalty · p. 8
- The infinity-norm lifting uses one shared nonnegative slack s, adding one variable and m + 1 constraints.Each soft constraint is split into two one-sided constraints, and s ≥ 0 adds one constraint.Source: E. Infinity-Norm Penalty · p. 8
F. Euclidean-Norm Penalty
- The Euclidean-norm lifting adds m + 1 variables, but its second-order cone constraint cannot be expressed in a standard QP.It uses per-constraint variables ξ_i and an epigraph variable t with cost αt.Source: F. Euclidean-Norm Penalty · p. 8