---
kind: concept
slug: active-set-method
title: Active-set method
summary: >-
  Solve a convex QP by guessing its tight inequality constraints, solving the equality-constrained system and correcting the guess. Warm-starting from the previous step's active set needs one linear solve in most steps of one walking controller. Dense active-set solvers such as qpOASES and qpmad suit whole-body control; benchmark claims are relayed.
tags: [optimization, quadratic-programming, control, real-time]
papers: ["1311.1839", "2510.21773"]
related: [model-predictive-control]
status: draft
updated_at: 2026-10-25
---

## Overview

An active-set method solves a constrained optimisation problem by tracking
which inequality constraints are active, meaning they hold with equality at
the solution. Fixing that set turns the problem into an equality-constrained
linear system. The method then checks whether the candidate is optimal and,
if not, adds or removes one constraint and solves again [arxiv:1311.1839 §4.1].
A review of real-time QP solvers describes the family the same way, and notes
that active-set solvers warm-start well when the set changes slowly
[arxiv:2510.21773 §2].

This page covers two groups of variants. The first is a custom warm-started
solver for a humanoid walking QP. The second is the general dense active-set
solvers that the review names for whole-body control and condensed MPC. Interior-point,
operator-splitting and augmented-Lagrangian solvers are other families. The
review names them [arxiv:2510.21773 §2], but this page does not describe them.

## Variants

### Warm-started active set for a walking QP

This variant is for convex quadratic programs in the form P z ≤ f. Its
specific idea is to assume that the active set at the next control step equals
the active set at the optimum of the previous step. The first candidate is then
one linear solve, and the loop only adjusts when that guess is wrong
[arxiv:1311.1839 §4.1].

The solver is custom to the paper. It starts from the previous step's active
set, solves the KKT system on that set, and adds a violated inequality or
drops one with a negative multiplier. It stops when the candidate satisfies
the feasibility and multiplier conditions. A fixed iteration limit guards
against cycling, and an interior-point solver is used when that limit is hit
[arxiv:1311.1839 §4.1] [arxiv:1311.1839 alg. 1].

The paper makes the linear algebra cheaper. The matrix W is block-diagonal,
and its inverse is computed once per control step rather than once per
iteration, because it does not depend on the active set. The inversion uses
the matrix inversion lemma, so only small matrices are inverted
[arxiv:1311.1839 §4.2]. Card: [Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion](/papers/1311.1839).

The paper reports that about 97% of steps on flat-ground walking need one
iteration, and an average solve of 0.2 ms [arxiv:1311.1839 §1]
[arxiv:1311.1839 tab. 1]. These figures are author-reported and come from
simulation on one 34-DOF humanoid model, on one laptop [arxiv:1311.1839 §5.1].

### Dense active-set solvers for WBC and condensed MPC

The review lists several active-set solvers and rates the family in one
overview table. In that table, qpOASES is a parametric active-set solver, qpmad
and DAQP are dual active-set solvers, and Eiquadprog is a dense active-set
solver [arxiv:2510.21773 tab. 1] [arxiv:2510.21773 tab. 2]. The review rates
the family as suited to small and medium dense QPs, such as whole-body control
(WBC) or condensed model predictive control (MPC), and it marks warm-starting
as supported [arxiv:2510.21773 tab. 1]. Card: [Real-Time QP Solvers: A Concise Review and Practical Guide Towards Legged Robots](/papers/2510.21773).

The review's timing claims are relayed from other benchmarks. qpmad is reported
up to twofold faster than Eiquadprog on small and medium dense problems, and
qpOASES is competitive when warm-started [arxiv:2510.21773 §3]. In a WBC
benchmark the review cites, Eiquadprog runs in under a millisecond on every
tested platform [arxiv:2510.21773 §3]. The review does not measure these itself.

## When to use which

There are two documented variant groups. The table records what the cited
results support.

| Situation | Use | Why |
|---|---|---|
| Convex QP inside a fast control loop, where consecutive problems are similar and dense | Warm-started active set | The walking QP changes little between steps. The paper reports one solve in most steps and faster solves than Gurobi and CVXGEN on its test [arxiv:1311.1839 §5.1] [arxiv:1311.1839 tab. 1]. The review rates active-set solvers as suited to small–medium dense QPs [arxiv:2510.21773 tab. 1]. |
| Dense whole-body control or condensed dense MPC | A named dense active-set solver, such as qpmad, DAQP or qpOASES | The review rates these as warm-start capable and suited to this shape. Its ratings are its own judgements, not measurements [arxiv:2510.21773 tab. 1]. Timings are relayed from other benchmarks [arxiv:2510.21773 §3]. |
| Long-horizon sparse optimal-control QP | A structure-exploiting interior-point solver, such as HPIPM | The review recommends HPIPM for long-horizon MPC and reports it fastest on sparse QPs in a relayed benchmark [arxiv:2510.21773 §3] [arxiv:2510.21773 §4]. Active-set solvers are not its pick for this shape. |
| Problems that change a lot between solves, or contacts that switch often | Test before adopting | Contact changes alter the constraint set, which is where warm starts fail. The paper does not measure this separately [arxiv:1311.1839 §5]. The review notes that active-set timing can jitter when the set switches [arxiv:2510.21773 §2]. |
| Need a bounded worst-case time | Plan a fallback | The paper says finite termination cannot be guaranteed, so it keeps an interior-point fallback [arxiv:1311.1839 §4]. The review's table marks early termination as unavailable for the active-set family and for qpOASES [arxiv:2510.21773 tab. 1]. |
| You want an off-the-shelf general solver and can accept slower timings | A general solver, such as Gurobi or CVXGEN | On its own setup the paper reports Gurobi at 1.0 to 3.1 ms and CVXGEN at 2.2 ms, against 0.2 ms for its solver [arxiv:1311.1839 tab. 1]. The CVXGEN formulation omits the torque-limit inequalities [arxiv:1311.1839 §5.1], so the comparison is not like-for-like. |

## Implementation sketch

The loop below follows the paper's method in outline. The paper does not
state an iteration limit, a fallback solver or how the first step starts, so
those lines are marked as choices for you to make.

```pseudocode
# Warm-started active-set loop for a convex QP  [arxiv:1311.1839 §4.1]
# Inputs: P, f (constraints), W, g (objective), active set from last step

def active_set_solve(P, f, W, g, active_prev):
    # Invert the objective matrix once per step, not per iteration  [§4.2]
    w_inv = invert_objective(W)
    # Assume the active set is unchanged from the previous optimum  [§4.1]
    active = active_prev
    # Iteration limit is not stated in the paper; choose one  [alg. 1]
    for _ in range(MAX_ITER):
        # Solve the equality-constrained KKT system on the active set  [eq. 18]
        z, mult = solve_kkt(P, f, w_inv, g, active)
        # Add the most violated inequality, if any  [alg. 1]
        violated = most_violated(P, f, z)
        if violated is not None:
            active = active + [violated]
            continue
        # Drop an index whose multiplier is negative  [§4.1]
        negative = first_negative(mult, active)
        if negative is None:
            return z  # optimal: feasible and all multipliers >= 0  [eq. 19]
        active = [i for i in active if i != negative]
    # Limit reached: fall back to a general solver  [§4]
    return interior_point_solve(P, f, W, g)
```

Notes on the sketch. The paper's add rule and drop rule are written as bare
checks and do not say whether they apply to one index or to all violated
indices at once. The sketch picks one index per pass, which is a choice you
should test [arxiv:1311.1839 alg. 1]. How to start the first step, and what
to do with the active set after the fallback, are not stated
[arxiv:1311.1839 §4.1].

## Contradictions

- **Gurobi warm start.** The walking paper reports its Gurobi baselines as
  using warm starts, for both the barrier and the dual simplex method
  [arxiv:1311.1839 §5.1]. The review's table lists Gurobi as an interior-point
  solver with warm start marked as not supported [arxiv:2510.21773 tab. 2]. The
  two sources describe the same solver differently. This page does not resolve
  it. Check the solver version and settings before comparing timings.
- **Timings are not comparable.** The walking paper's 0.2 ms solve time comes from
  one laptop and one humanoid model [arxiv:1311.1839 §5.1]. The review's dense-solver
  timings come from other benchmarks, with other problems and hardware
  [arxiv:2510.21773 §3]. The two do not conflict, but they cannot be ranked
  against each other.

## Papers

- [An Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion](/papers/1311.1839): a warm-started active-set solver for a humanoid walking QP, reporting about 1 kHz control with author-reported solve times.
- [Real-Time QP Solvers: A Concise Review and Practical Guide Towards Legged Robots](/papers/2510.21773): a review of convex QP solver families for legged-robot control, with active-set solvers as one family and selection guidance.