🔢 mathematics

ElastiQP: An Always-Feasible QP Solver for Constrained Robot Control

ElastiQP is an open-source, always-feasible QP solver that analytically integrates slack variables to relax inequality constraints while preserving hard equality dynamics, enabling microsecond-level performance and graceful handling of infeasible problems in constrained robot control.

Original authors: Daniel Morton, Jon Arrizabalaga, Zachary Manchester, Marco Pavone

Published 2026-09-17

📖 5 min read🧠 Deep dive

CC BY 4.0

Original authors: Daniel Morton, Jon Arrizabalaga, Zachary Manchester, Marco Pavone

Original paper licensed under CC BY 4.0 (http://creativecommons.org/licenses/by/4.0/). ✨ This is an AI-generated explanation of the paper below. It is not written or endorsed by the authors. For technical accuracy, refer to the original paper. Read full disclaimer

Robots are becoming increasingly capable, moving from simple, repetitive tasks in factories to navigating complex, unpredictable environments alongside humans. To make these machines move safely and reliably, engineers rely on a mathematical tool called a quadratic program. Think of this as a sophisticated decision-making engine that constantly calculates the best possible set of commands for a robot's motors. It must balance many competing demands at once: keeping the robot upright, reaching for an object, avoiding a wall, and staying within the physical limits of its own joints. The engine works by finding a solution that satisfies all these rules simultaneously. However, in the chaotic real world, these rules can sometimes clash. A sudden gust of wind might push a drone so hard that it cannot simultaneously stay within its safety zone and obey its motor limits. In such a moment of conflict, traditional decision engines often simply stop working, returning an error that leaves the robot frozen and vulnerable.

This is the problem that a team of researchers at Stanford University and the Massachusetts Institute of Technology set out to solve. They developed a new computational method called ElastiQP, designed specifically to keep robots moving even when their instructions contradict each other. Instead of freezing when a conflict arises, this new solver treats the robot's safety and task limits as slightly flexible. It allows the robot to bend a rule just enough to keep moving, but only the specific rule that is causing the trouble, while keeping all other rules perfectly rigid. The researchers found that this approach not only prevents the robot from stopping but does so with incredible speed, solving these complex problems in microseconds. This means a robot can make these split-second decisions thousands of times per second, ensuring it remains stable and safe even when pushed to its absolute limits.

The core innovation lies in how the solver handles the math behind these decisions. In standard approaches, when a conflict occurs, the system often tries to find a compromise that slightly violates every single rule a tiny bit, or it gives up entirely. The new method, however, is designed to be "always feasible," meaning it always produces a usable command. It achieves this by introducing a concept of "elasticity" to the inequality constraints—the rules that say things like "do not go faster than this" or "stay inside this box." When the robot faces a situation where it cannot obey all these rules at once, the solver identifies exactly which rule is the source of the conflict. It then relaxes only that specific rule, allowing a small violation, while keeping every other rule, especially the laws of physics that govern the robot's motion, completely strict. This is crucial because a robot that ignores the laws of physics, such as the relationship between force and acceleration, would simply fall over or break.

To make this work fast enough for real-time control, the researchers had to overcome a significant computational hurdle. Usually, adding flexibility to a problem requires adding extra variables to the calculation, which makes the math much slower and heavier. The team discovered a way to fold these extra variables directly into the calculation without expanding the size of the problem. By doing this, they kept the computational load constant, regardless of how many rules the robot was trying to follow. This allowed their solver to run at speeds that match or even beat the fastest existing tools when everything is working smoothly, but with a massive advantage when things go wrong. In tests involving a 28-joint humanoid robot, the new solver was able to find a solution up to 40 times faster than the best alternative methods when faced with impossible situations.

The researchers tested their system on a variety of robotic challenges, from a single robotic arm to a full-sized humanoid robot. They simulated scenarios where the robot was pushed into corners or faced with moving obstacles that made its instructions impossible to follow perfectly. In every case, the new solver provided a "best effort" command that kept the robot moving safely. It ensured that if a violation was necessary, it happened only where it was absolutely required, such as accepting a minor collision with a dynamic obstacle to avoid crashing into a solid wall, rather than spreading the error across all its movements. This precision is vital for safety; a robot that slightly bends its speed limit to avoid a person is safe, but a robot that slightly bends its balance equations is dangerous. The team confirmed that their method keeps the physics equations perfectly accurate while only relaxing the safety and task limits.

The implications of this work extend beyond just making robots faster. It provides a new level of reliability for machines operating in unstructured environments. By guaranteeing that a solution always exists, even in the face of conflicting constraints, engineers can deploy robots in situations where they might encounter unexpected disturbances without fear of the control system failing. The researchers have made their software available as an open-source tool, allowing other scientists and engineers to integrate this always-feasible approach into their own systems. While the method was designed for robotics, the underlying math is robust enough to handle a wide range of complex optimization problems, suggesting that this way of thinking about flexibility and constraints could improve decision-making in many other fields where reliability is paramount. The work represents a shift from hoping that a robot's instructions will always be possible, to building systems that can gracefully handle the impossible.

Technical Summary: ElastiQP: An Always-Feasible QP Solver for Constrained Robot Control

Problem Statement

Quadratic programming (QP) is a cornerstone of model-based robot control, utilized in whole-body control, safety filters, and locomotion. As robot capabilities and environmental complexity increase, the number of constraints in these QPs grows, often leading to momentary conflicts where constraints become instantaneously inconsistent (infeasible). Standard QP solvers return an "infeasible" status in these scenarios, leaving the robot controller with no executable command—a potentially dangerous state.

Existing approaches to handle infeasibility face significant trade-offs:

Hard Solvers: Return no solution upon infeasibility.
$\ell_2$ Relaxation (Soft Constraints): Spreads violations across all constraints, including those not in conflict, leading to undesirable trade-offs and loss of sparsity.
Expanded $\ell_1$ Relaxation: Introduces a slack variable for every inequality constraint. While this ensures feasibility and sparsity, it expands the decision vector significantly. For solvers like ProxQP, PIQP, and DAQP, the factorization cost becomes dominated by these slack variables, often failing to meet the strict 1 ms time budget required for high-frequency (1 kHz) control.
Existing Elastic Solvers: Methods like qpax offer condensed elastic modes but lack support for hard equality constraints, warm-starting, or sufficient speed on high-degree-of-freedom (DoF) systems.

Methodology

The authors introduce ElastiQP, a modified dual active-set QP solver designed to guarantee feasibility while maintaining microsecond-level performance. The core innovation lies in the analytical condensation of elastic slack variables.

1. The Elastic QP Formulation

ElastiQP solves an elastic QP where inequality constraints are relaxed with an exact $\ell_1$ penalty, while equality constraints (typically dynamics) remain hard:
$\begin{aligned} \min_{x,t} \quad & \frac{1}{2}x^\top Qx + q^\top x + w^\top t \\ \text{s.t.} \quad & Ax = b \\ & Gx - t \leq h \\ & t \geq 0 \end{aligned}$
Here, $t$ represents the slack variables. Crucially, the inner minimization over $t$ can be solved analytically ( $t_i = \max(0, [Gx-h]_i)$ ), reducing the problem to an exact $\ell_1$ penalty formulation on $x$ alone.

2. Elastic Condensation in Dual Active-Set Methods

Traditional solvers treat slacks $t$ as decision variables, expanding the problem size. ElastiQP eliminates $t$ analytically. In the context of Dual Active-Set Methods (ASM), this condensation transforms the problem into a simple modification of the dual constraints:

Bounded Multipliers: The inequality multipliers $z$ are constrained to a box $[0, w]$ rather than the standard non-negative half-line $[0, \infty)$ .
Three States: The algorithm manages three states for inequality constraints:
1. Inactive: $z_i = 0$ (satisfied).
2. Active: $0 < z_i < w_i$ (tight).
3. Saturated: $z_i = w_i$ (violated, with slack $t_i > 0$ ).
Linear System: The condensation results in a linear system of size $n \times n$ (where $n$ is the number of decision variables), independent of the number of inequality constraints $p$ . This maintains the computational efficiency of standard ASMs even when $p \gg n$ .

3. Algorithmic Adjustments

The solver modifies the standard dual ASM iteration:

The working set solve includes a term accounting for saturated constraints ( $M_S w_S$ ).
The update logic handles the "saturated" state, adding constraints to the working set if they are violated or removing them if they become strictly satisfied.
Because equality constraints are hard and consistent by construction in robot dynamics, the elastic dual ASM is guaranteed to always return a solution, provided the equality constraints are consistent.

Key Contributions

ElastiQP Solver: A header-only C++ library (with Python/JAX interfaces) that implements a dual active-set method with analytical slack condensation.
Always-Feasible Guarantee: By using $\ell_1$ relaxation on inequalities and hard constraints on equalities, the solver never returns infeasible, ensuring the robot always has a control command.
Performance: The analytical elimination of slack variables allows the solver to match or exceed the speed of leading solvers on feasible problems and handle infeasible problems up to 40x faster than the best alternatives.
Sparsity Preservation: Unlike $\ell_2$ relaxations, the $\ell_1$ structure ensures that violations are sparse, affecting only the conflicting constraints.

Results

Robot Control Benchmarks

The authors evaluated ElastiQP on three robot control scenarios: a 6-DoF arm, a 12-DoF bimanual system, and a 28-DoF humanoid.

Feasible Loops: ElastiQP achieves microsecond-level solve times (e.g., 52 $\mu$ s for the 28-DoF humanoid cold start), comfortably meeting the 1 ms budget. It performs comparably to DAQP (the fastest hard solver) on feasible problems.
Infeasible Loops: On infeasible problems, hard solvers (DAQP, PIQP, ProxQP) fail or take excessive time to report infeasibility. ElastiQP returns a minimally-violating solution in microseconds.
- Speed: ElastiQP is up to 40x faster than the next best alternative (ProxQP sparse backend) on infeasible humanoid problems.
- Quality: ElastiQP violates only the conflicting constraints (1 row in the test case), whereas $\ell_2$ solvers (DAQP-soft, ProxQP-closest) spread violations across 28–29 rows.
- Equality Consistency: ElastiQP maintains equality constraints (dynamics) to tight tolerances ( $10^{-8}$ ), whereas $\ell_2$ soft modes can degrade equality satisfaction significantly.

Maros–Mészáros Benchmarks

Evaluated on a broader suite of general-purpose, ill-conditioned problems:

ElastiQP is competitive with the best general-purpose solvers (DAQP for small problems, PIQP for large sparse problems).
The elastic condensation does not degrade performance on general problems; ElastiQP solves some instances that other solvers fail to converge on.
It significantly outperforms qpax, the only other solver offering a condensed elastic mode, in both speed and reliability.

Significance and Claims

The paper claims that ElastiQP addresses a critical gap in robot control: the need for a solver that is both fast enough for high-frequency control and robust enough to handle inevitable constraint conflicts without leaving the robot without a command.

Reliability: It provides an "always-feasible" solution, preventing the dangerous state of a controller having no output.
Efficiency: By analytically condensing slack variables, it avoids the computational penalty typically associated with elastic formulations, making it viable for high-DoF systems.
Practicality: The $\ell_1$ penalty structure allows for hierarchical relaxation (e.g., prioritizing safety over task completion) without the diffuse trade-offs of $\ell_2$ methods.
Deployment: The authors position ElastiQP as ready for immediate integration into existing safety filters and controllers, with open-source availability.

The authors remain modest regarding future work, noting that while the current focus is on CPU-based real-time control, future directions include differentiability, GPU acceleration for batched solves, and application as an inner solver for SQP pipelines in global inverse kinematics.