Skip to article frontmatterSkip to article content
Site not loading correctly?

This may be due to an incorrect BASE_URL configuration. See the MyST Documentation for reference.

QpProblem

Overview

QpProblem represents a quadratic program over direct Vector and Matrix entries in Values. It combines affine quadratic costs with linear equality and inequality constraints, then solves them with an active-set method.

The default QP path uses sparse active-set subproblems. Dense active-set subproblems are available explicitly through QpSolverType::Dense or ActiveSetSolverParams::QpSubproblemSolver::Dense. QpSolverType::AugmentedLagrangian selects the direct Gaussian ALM solver with native defaults. See the Gaussian ALM guide for parameters, status, multiplier units, and a small QP driver.

For explicit ALM options, pass AugmentedLagrangianParams directly to problem.optimize(params) or problem.optimize(initial, params). The existing params.lmParams.multifrontalParams.qrMode setting accepts gtsam.MultifrontalParameters.QRMode.Off, Allow (default), or Force; the shared Gaussian ALM guide shows how to disable QR for benchmarking.

Open In Colab

Objective representation

A QP combines quadratic costs, affine equalities, and affine inequalities over direct Vector or Matrix entries in Values. Matrix values use column-major vectorization.

Add original JacobianFactor costs when the problem comes from least squares. For a factor with residual Ax−bA x-b and diagonal noise sigmas, GTSAM minimizes 12∥diag⁡(1/σ)(Ax−b)∥2\tfrac12\|\operatorname{diag}(1/\sigma)(Ax-b)\|^2. QpCost retains this square-root representation for evaluation, gradients, and sparse elimination. Jacobian-native QPs use QR throughout elimination, including separator factors; they do not first form global normal equations.

Hessian-native costs remain supported. To represent the standard objective 12xTPx+qTx\tfrac12 x^T P x+q^T x, pass quadratic term P and linear term -q to HessianFactor. Its scalar constant is twice the desired additive objective constant. Do not manufacture Hessians from least-squares factors merely to call the QP solver: that can lose weak directions through normal-equation rounding.

Use LinearConstraint.Equal, LessEqual, and GreaterEqual to represent the original affine rows. Constraint row order determines the public multiplier and working-set order.

Minimal C++ Example

using namespace gtsam;

const Key x = Symbol('x', 0);

QpProblem problem;
problem.addCost(HessianFactor(
    x, Matrix::Identity(2, 2),
    (Vector(2) << 2.0, 3.0).finished(), 13.0));
problem.addConstraint(LinearConstraint::LessEqual(JacobianFactor(
    x, Matrix::Identity(2, 2),
    (Vector(2) << 1.0, 1.0).finished())));

Values initial;
initial.insert(x, (Vector(2) << 0.0, 0.0).finished());
Values result = problem.optimize(initial);

problem.optimize(initial) uses the sparse active-set QP mode by default. Without supplied values, sparse QPs first try a minimum-norm equality projection and check every inequality. If that fails, the solver runs a phase-I LP. Supplied values bypass this feasibility search.

Minimal Python Example

array([1., 1.])

Sparse and dense subproblems

The convenience calls select the QP subproblem backend:

Values sparse = problem.optimize(initial, QpSolverType::Sparse);
Values dense = problem.optimize(initial, QpSolverType::Dense);

Both use an active-set method. Sparse mode builds a working factor graph from the costs, equalities, and active inequality rows. Dense mode packs contiguous objective and constraint blocks and eliminates permanent equalities before exploring inequality working sets. It caches an objective QR factorization and lazily transformed constraint normals, then updates working LDLᵀ factors when rows enter or leave. The primal and retained equality factors also supply multipliers, checked against the original objective. Exact diagonal Hessians use direct square roots; equality QR omits only exactly zero substituted rows, retaining all original checks and multiplier indices. A rank-aware null-space QR path handles singular curvature and dependent exact boundaries. Every original selected row retains its identity and is checked. Mutable caches belong to one optimization call. Dense reuses its permanent equality preparation for cold feasibility, projected-gradient initialization, and the main solve. Each original cone component keeps its gradient scale and iteration budget; lifted tangent directions are checked against the original rows, and phase one remains available when the affine equality point is infeasible. Changing only a proximal center uses cached RHS solves with zero numerical factorizations. Dense mode is useful for small, dense, fixed-structure control-allocation QPs; sparse mode preserves chain, grid, and arbitrary factor-graph structure.

ActiveSetSolver exposes the full options. Its constructor copies and validates the parameters; changing a parameter object afterward does not change an existing solver. The problem must outlive the solver.

auto params = std::make_shared<ActiveSetSolverParams>();
params->qpSubproblemSolver =
    ActiveSetSolverParams::QpSubproblemSolver::Sparse;
Values result = ActiveSetSolver(problem, params).optimize(initial);

Incremental sparse elimination and ordering

With useIncrementalSparseQp = true (the default), each sparse QP optimization call retains a GaussianISAM2 working tree, including when proximal regularization is positive. Activating or releasing an inequality adds or removes its factor; the solver re-eliminates the affected cliques and ancestor paths while retaining untouched subtrees. Changing the proximal center with fixed curvature and working constraints changes only the objective forcing. The solver uses cached triangular solves for that change, with zero numerical eliminations. Exact affine constraints retain their right-hand sides. Back-substitution remains exact, and multiplier recovery is a separate factor-graph solve.

The solver caches elimination orderings while the exact working-variable key set stays unchanged. If a constraint-only variable enters or leaves the graph, it rebuilds the incremental instance with an ordering for the new key set. Setting useIncrementalSparseQp = false selects the batch comparison path without changing the sparse numerical backend.

An explicit ordering must contain every problem variable key exactly once. The solver preserves its relative order in working graphs and auxiliary projections, restricts it to their keys, and appends the synthetic slack key for phase one. Internal multiplier keys use a separate ordering.

params->setOrdering(Ordering{x0, x1, x2});
// params->clearOrdering();  // Return to automatic COLAMD.

Positive-regularization QPs and LPs retain the batch path. Workspace reuse is scoped to one public solver call; separate calls do not retain a Bayes tree, even if the same solver object is reused.

GaussianISAM2::optimize(linearTermDelta) is a general linear-algebra query: it minimizes the registered factor objective minus the supplied linear term, subject to the same exact constraints. The forcing is relative to the registered factors, not the previous query. The query leaves original factors, conditionals, and separator messages unchanged. ActiveSetSolver alone interprets a proximal-center change as regularization * (center - referenceCenter); its registered proximal factors keep that reference center across working-set updates. This keeps later additions and removals consistent without reinserting proximal factors.

Cold QP initialization

ActiveSetSolverParams::QpInitialization makes the initialization policy explicit:

ModeStarting pointInitial working set
TightConstraints (default)PreservedEvery tight inequality
ProjectedGradientPreservedTight rows with strictly inward projected derivatives released
FeasibleStepThenProjectedGradientOne feasible descent attemptTight-row selection and projection at the accepted point

The two-stage mode makes one working-face solve attempt without projection, truncates at the first blocking inequality, and accepts only useful descent of the original objective. An unhelpful step retains the supplied point. It then projects the negative gradient at the resulting point onto independent tangent-cone components. Numerical failures propagate; the method never adds all violated affine boundaries as simultaneous equalities.

Supplied values are the starting point; they are not replaced with zero. The two-stage mode requires those values to satisfy both equalities and inequalities. The other full-optimization modes can enforce initially unsatisfied equalities in their working subproblems, but still require inequality-feasible supplied values.

An explicit working-set warm start takes precedence and bypasses all cold initialization, including the preliminary step. Providing values alone does not bypass the selected strategy. LPs accept only TightConstraints.

The preliminary attempt shares maxIterations and the sparse workspace with full refinement. Auxiliary projection iterations have their own per-component budget and are excluded from the main iteration count; their runtime is included in the public call. This enum replaces the experimental useProjectedGradientInitialization boolean.

Regularization and stopping checks

QP regularization is a recentered proximal weight for working subproblems in both backends. Full optimization checks the original problem’s feasibility, multiplier signs, absolute stationarity, and a constant-free, scale-aware duality gap with a floating-point allowance. This is not permanent objective damping. Both backends share equality-first feasibility search with phase-one fallback, initialization strategies, warm-start precedence, blocking, row release, multiplier recovery, and the original-QP certificates. Dense does not add a permanent target penalty or silently raise the requested regularization. Releasing a basis row while redundant active rows remain may trigger a controlled numerical rebuild; the original constraints are preserved.

If the original objective already contains LM damping and the QP subproblems are sufficiently determined, use regularization = 0 to avoid adding more. Incremental sparse elimination also supports positive regularization. Keep the original damping factors in the model. The solver does not infer this setting from the factors or silently switch numerical backends.

activeTolerance selects tight rows; stepTolerance defines useful displacement; feasibilityTolerance checks primal constraints; and multiplierTolerance checks multiplier signs and stationarity and supplies the absolute/relative constant-free gap tolerances. Tolerances and regularization must be finite and nonnegative. Exceeding maxIterations in full optimization throws rather than returning a merely feasible point as optimal.

Python: selecting initialization

This least-squares QP has a tight lower bound on its first coordinate. The first working-face minimum is [0, 3]; full optimization can release that bound and reach [2, 3]. The problem is already positive definite, so this example needs no additional regularization.

array([2., 3.])

A feasible step is not an optimal solution

computeFeasibleStep(initialValues) is a separate QP API. It requires a finite point satisfying every original equality and inequality. It seeks feasible descent without multiplier refinement or a QP optimality certificate. The caller still owns any nonlinear retraction and LM acceptance decision.

The result contains values, status, attempted main iterations, initialObjective, objective, a stable objectiveDecrease, constraintViolation, and the row-ordered activeInequalityMask().

  • FeasibleProgress: useful original-objective descent while feasible.

  • NoProgress: no useful displacement on the selected face; not proof of optimality.

  • NumericalFailure: a numerical check or solve failed.

  • IterationLimit: the main or auxiliary initialization budget was exhausted.

Non-progress, failure, and exhaustion retain the supplied point. Invalid inputs throw. Zero-length blockers update the working set or lead to an explicit non-progress/exhaustion result. objectiveDecrease avoids cancellation from large additive constants.

The selected initialization applies to this API too. With the two-stage mode, it completes the preliminary attempt and projected working-set selection, then returns descent already obtained there. It does not continue to optimality. The following is an independent feasible-step call, not a cached continuation of the full solve above.

{'status': 'Status.FeasibleProgress', 'main_iterations': 1, 'objective_decrease': 4.5, 'point': array([0., 3.])}

Benchmark comparison

The QP benchmark report compares GTSAM Sparse and Dense with this initialization, and GTSAM ALM with its native initialization, against DAQP, Clarabel, OSQP, and ProxQP on all 64 MPC QPs at four accuracy settings. Both current active-set entries retain the same proximal semantics. Sparse uses incremental factor updates and cached RHS solves; Dense uses cached objective QR, working LDLᵀ updates, and shared primal/multiplier factors. Dense eliminates permanent equalities before exploring inequality working sets. GTSAM timings start with assembled factors and include solver construction, Dense packing, ordering, initialization, and optimization; matrix-to-factor translation is excluded. The published report shows one current entry per backend. G1 compares GTSAM Sparse with automatic COLAMD, chronological ordering, and chronological slice groups with COLAMD inside each group, plus GTSAM ALM, against Clarabel, OSQP, and ProxQP; Dense and DAQP are excluded from the captured G1 QPs. All sparse active-set ordering variants use FeasibleStepThenProjectedGradient. ALM starts from zero with native BCL penalty updates and Levenberg–Marquardt inner solves; it receives no active-set initializer or extra objective damping. Its native convergence flag is checked independently against the same original-input metrics. The downloadable HTML uses the version-pinned Plotly CDN, so charts require an internet connection. It includes current summaries, original-input checks, timing boundaries, and software versions. The detailed sortable table and full measurements remain in the ignored local benchmark folder.

MPC includes 60 small dense-Hessian cases and four larger sparse-Hessian quadruped centroidal-control cases. G1 uses original Jacobian factors for GTSAM and sparse Hessians for the other solvers, with normal-equation conversion reported separately. The captured G1 damping remains part of the input. No full trajectory is run or published.

Initialization and backend choices have workload-dependent costs. The report distinguishes converged solutions from feasible steps, successful solves from native success flags that miss common tolerances, and watchdog limits from numerical or iteration failures.

State, Multipliers, and Warm Starts

In C++, optimizeWithState returns the optimized values and an ActiveSetSolverState. Equality and inequality multipliers are grouped by original constraint, with rows in the same order as the input constraint rows. activeInequalityRows stores the flattened row-level active set and can be passed back as a warm start:

ActiveSetSolver solver(problem, params);
auto [firstValues, firstState] = solver.optimizeWithState(initial);
auto [secondValues, secondState] =
    solver.optimizeWithState(firstState.values, firstState);

Warm starts are most useful when solving related QPs with the same constraint layout. Supplying that state bypasses qpInitialization; values alone retain cold working-set selection. Full-state and working-set warm-start overloads are currently C++ APIs. Python exposes optimize() and the explicit feasible-step result.

Primal, dual, and automatic formulations

ActiveSetSolverParams.qpFormulation selects Automatic (the default), Primal, or Dual, independently of qpSubproblemSolver (Sparse by default, or Dense). Automatic selects Dual for cold starts with inequalities, regardless of the inequality-to-variable ratio. A converged C++ warm start retains its previous formulation when the supplied point is feasible. A nonconverged warm start or an infeasible supplied point selects Dual. Values supplied without a state are a cold proximal center. Equality-only and fully fixed problems use Primal directly. Selection happens once during setup; the policy is a heuristic, not a speed guarantee.

Dual uses a nonnegative-multiplier active set inspired by Arnström, Bemporad, and Axehill (2022). Dense projects permanent equalities by default. Set params.projectDenseQpEqualities = False to keep the original coordinates and enforce equalities in the factorization, for either Primal or Dual. This option leaves Sparse unchanged. Disabling projection may avoid its setup cost, but retains more variables in subsequent solves; benchmark both choices. Dense preserves supplied square-root costs in either mode. For a positive-definite Hessian-only objective without equalities, it uses cached Cholesky solves when the native Hessian is sufficiently well conditioned. Other cases retain the rank-aware square-root path. This changes no tolerances or proximal weight. Sparse applies the cached equality-constrained inverse without a dense nullspace or global inverse; only the dual working system is dense. Its fixed-factorization cache is independent of the primal-only useIncrementalSparseQp option.

Dual bypasses phase one and qpInitialization. Supplied finite values provide the proximal center and result shapes and may violate primal constraints. Without supplied values it starts with a zero center, zero multipliers and no working rows. C++ state warm starts reuse row masks and multipliers; absent multipliers start at zero and inequality multipliers are projected onto the valid sign. Public inequality multipliers keep GTSAM’s existing nonpositive sign convention.

The requested regularization is a recentered proximal weight, never a permanent objective penalty. Dual requires invertible curvature after equality elimination. With singular curvature and zero regularization, Automatic selects Primal and explicit Dual throws an explanatory error. Numerical failures after selection do not trigger a switch. Convergence is certified against the original QP; the shared maxIterations budget counts dual working solves across proximal iterations. The C++ result state’s qpFormulation records the resolved formulation.

computeFeasibleStep() always uses primal feasible descent, retaining its existing initialization and feasibility requirements. LPs resolve Automatic to Primal and reject Dual.

params = gtsam.ActiveSetSolverParams()
params.qpFormulation = gtsam.ActiveSetSolverParams.QpFormulation.Automatic
params.qpSubproblemSolver = gtsam.ActiveSetSolverParams.QpSubproblemSolver.Sparse
result = gtsam.ActiveSetSolver(problem, params).optimize()