Quadratic Programming (QP) Solver

A QP solver is specialized for the convex quadratic programming problem. The canonical form for Linear MPC is:

codeCopy
minimize   (1/2) x^T H x + f^T x
subject to  A x ≤ b
            A_eq x = b_eq
            lb ≤ x ≤ ub

• H (Hessian): A positive semi-definite matrix defining the quadratic cost (e.g., tracking error, control effort). Convexity guarantees a global minimum.
• Linear Constraints: Model physical limits (actuator saturation, safety boundaries) and system dynamics (equality constraints from the discretized model).
• The solver's efficiency hinges on exploiting this specific, highly structured mathematical form.

Different algorithmic families are chosen based on problem scale, hardware, and need for warm starts.

• Active-Set Methods: Iteratively identify which constraints are 'active' (tight) at the solution. Excellent for warm-starting, making them ideal for MPC where the solution changes incrementally between time steps.
• Interior-Point Methods: Approach the optimum from within the feasible region. Often have better worst-case complexity for large, dense problems but can be less efficient for warm-started sequences.
• First-Order Methods (e.g., ADMM, Projected Gradient): Use only gradient information. Lower per-iteration cost, suited for very large-scale or embedded problems where approximate solutions are acceptable. Often used in real-time MPC for fast but less precise solves.

The solver must produce reliable solutions despite finite-precision arithmetic and ill-conditioned matrices.

• Conditioning: The Hessian matrix H can be poorly conditioned (e.g., when penalizing states and inputs at vastly different scales), causing slow convergence or numerical errors. Solvers employ scaling and pre-conditioning.
• Feasibility Handling: Real-world measurements can make the QP infeasible. Advanced solvers support soft constraints via slack variables, automatically relaxing constraints with a penalty to guarantee a solution.
• Failure Modes: A robust solver provides clear exit statuses (optimal, infeasible, max iterations reached) and fallback strategies, such as returning the best feasible iterate, which is critical for safety in control systems.

For embedded MPC, the solver must have a bounded, predictable worst-case execution time (WCET).

• Fixed-Iteration Limits: Solvers are often configured with a maximum number of iterations to guarantee completion within the control sample period (e.g., 1-10 ms).
• Code Generation: Tools like ACADO Toolkit, FORCES Pro, or CVXGEN generate tailored, library-free C code for a specific QP problem structure. This eliminates dynamic memory allocation and branches, maximizing speed and determinism.
• Hardware Acceleration: Solvers can be deployed on FPGAs or GPUs for microsecond-scale solving, enabling high-frequency control (e.g., for drones or automotive steering).

The QP from MPC has a highly block-structured, sparse pattern due to the time-discretized prediction horizon.

• Structure: The Hessian H is often block-diagonal, and the constraint matrix A has a banded structure. A generic dense solver would be prohibitively slow.
• Efficient Algorithms: High-performance solvers (e.g., OSQP, qpOASES) explicitly exploit this sparsity, using specialized linear algebra (e.g., sparse LDL^T factorization) to solve the underlying Karush–Kuhn–Tucker (KKT) system.
• Memory and Speed: Sparsity exploitation reduces memory footprint and computational complexity from O(N^3) to nearly O(N), where N is the horizon length, enabling long prediction horizons.

The solver is not standalone; it is a component within a larger real-time control pipeline.

• Inputs: At each control step, the MPC framework forms the QP parameters: H, f, A, b. This is based on the current state estimate, reference trajectory, and linearized/updated model.
• Warm Start: The optimal solution vector (primal and dual variables) from the previous time step is used to initialize the solver, drastically reducing iteration count.
• Output: The solver returns the optimal input sequence. The MPC controller applies the first control input (Receding Horizon Principle) and discards the rest.
• Failure Recovery: The control architecture must define behavior on solver failure (e.g., hold last valid input, revert to a backup PID controller).

A standard QP problem solved in MPC is expressed as:

Minimize: (1/2) * xᵀ * H * x + fᵀ * x Subject to: A * x ≤ b, A_eq * x = b_eq, lb ≤ x ≤ ub

Where:

• x is the vector of optimization variables (future control inputs and states).
• H is a positive semi-definite Hessian matrix from the quadratic cost (e.g., tracking error).
• f is the linear cost vector.
• A, b, A_eq, b_eq, lb, ub define the linear inequality and equality constraints, representing actuator limits, safety boundaries, and system dynamics.

The solver's task is to find the optimal x* that minimizes cost while satisfying all constraints.

Active-set methods are a classical family of QP solvers that work by iteratively guessing which constraints are 'active' (tight at the solution).

• They solve a sequence of equality-constrained subproblems using the Karush-Kuhn-Tucker (KKT) conditions.
• At each iteration, the algorithm adds or removes constraints from the active set based on Lagrange multiplier signs and constraint violations.
• Pros: Highly accurate, can exploit warm starts effectively (crucial for MPC where the solution changes incrementally).
• Cons: Can have exponential worst-case complexity, though performance is often good in practice. Libraries like qpOASES use a primal active-set strategy optimized for MPC.

Interior-point methods (IPMs) approach the optimal solution by traveling through the interior of the feasible region, not along its boundary.

• They transform inequality constraints into barrier terms added to the objective, creating a smooth, unconstrained approximation.
• The algorithm then follows a central path to the optimum using Newton's method.
• Pros: Excellent for large, dense problems with predictable iteration counts. Scales well with problem size.
• Cons: Less effective at exploiting warm starts from a nearby solution compared to active-set methods. Implemented in solvers like OSQP and ECOS.

These are modern, lightweight algorithms designed for very fast solves on embedded hardware, often sacrificing some accuracy for speed.

• Alternating Direction Method of Multipliers (ADMM): Used by OSQP, it splits the problem into simpler subproblems solved iteratively. It's robust and can handle large problems with modest accuracy requirements.
• Proximal Algorithms: Efficient for problems with simple constraints (like box bounds).
• Pros: Extremely fast, low memory footprint, often have bounded runtime—critical for real-time MPC with strict sampling periods (e.g., < 1ms).
• Cons: May require many iterations for high precision; solutions are often approximate.

Choosing a QP solver depends on the MPC application's requirements:

• Sampling Time & Hardware: For very fast loops (< 10ms) on microcontrollers, use embedded code-generation (FORCES Pro) or a lightweight first-order solver (OSQP).
• Problem Type: For Linear MPC with a dense QP, interior-point methods are efficient. For problems that benefit heavily from warm-starting (most MPC), active-set methods (qpOASES) excel.
• Accuracy vs. Speed Trade-off: High-fidelity control (e.g., aerospace) demands high-precision solvers. Perception-aware or economic MPC might tolerate approximate solves for greater speed.
• Nonlinear MPC (NMPC): Here, the QP solver is embedded within a Sequential Quadratic Programming (SQP) loop, where speed per QP solve is paramount.

Quadratic Programming is the specific class of convex optimization problem solved by a QP solver. The standard form is:

• Objective: Minimize (\frac{1}{2} x^T Q x + c^T x)
• Subject to: (A_{eq} x = b_{eq}) and (A_{ineq} x \leq b_{ineq}) In Linear MPC, the cost function (tracking error, control effort) is formulated as quadratic, and system constraints (actuator limits, safe zones) are linear, resulting precisely in a QP at each control step.

Convex optimization is a subfield where the objective function is convex and the feasible set defined by constraints is convex. A key property is that any local minimum is also a global minimum. QP is a fundamental convex problem when the matrix Q is positive semi-definite. This convexity is what allows MPC's online optimization to be reliable and efficient, guaranteeing the solver finds the globally optimal control move within the sampling period.

The Optimal Control Problem is the broader mathematical formulation that MPC solves online. It is defined over a time horizon by:

• A dynamic model (e.g., state-space equations)
• A cost function to minimize
• Path and terminal constraints on states and controls In Linear MPC, this continuous-time OCP is discretized and, with a quadratic cost and linear constraints, is transcribed into a QP for the solver. The QP solver is thus the computational tool for the OCP.

An active-set method is a prominent algorithm class for solving QPs. It works by iteratively guessing which inequality constraints are 'active' (i.e., equalities at the solution) and solving a sequence of equality-constrained QPs. It is particularly efficient for problems where the optimal solution lies at the intersection of a small subset of constraints, a common case in MPC where only some actuators are at their limits.

An interior-point method is another major algorithm class for convex optimization, including QPs. Instead of traveling along the boundary of the feasible set, it approaches the optimal solution from the interior by using barrier functions. These methods are highly effective for large-scale, dense QP problems and form the basis of many high-performance commercial solvers used in industrial MPC applications.

Sequential Quadratic Programming is the primary iterative algorithm for solving the Nonlinear Programming (NLP) problems in Nonlinear MPC (NMPC). At each iteration, SQP approximates the original NLP by a local QP subproblem. The QP solver is therefore the core workhorse called repeatedly within each SQP iteration. The efficiency of the overall NMPC solution is directly tied to the speed of this embedded QP solver.