Active-set method

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 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 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 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 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 1311.1839 §4.1 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 1311.1839 §4.2. Card: Efficiently Solvable Quadratic Program for Stabilizing Dynamic Locomotion.

The paper reports that about 97% of steps on flat-ground walking need one iteration, and an average solve of 0.2 ms 1311.1839 §1 1311.1839 tab. 1. These figures are author-reported and come from simulation on one 34-DOF humanoid model, on one laptop 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 2510.21773 tab. 1 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 2510.21773 tab. 1. Card: Real-Time QP Solvers: A Concise Review and Practical Guide Towards Legged Robots.

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 2510.21773 §3. In a WBC benchmark the review cites, Eiquadprog runs in under a millisecond on every tested platform 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.

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.

# 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 1311.1839 alg. 1. How to start the first step, and what to do with the active set after the fallback, are not stated 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 1311.1839 §5.1. The review's table lists Gurobi as an interior-point solver with warm start marked as not supported 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 1311.1839 §5.1. The review's dense-solver timings come from other benchmarks, with other problems and hardware 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: 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: a review of convex QP solver families for legged-robot control, with active-set solvers as one family and selection guidance.