Source-linked AI summary
HPIPM: a high-performance quadratic programming framework for model predictive control
Gianluca Frison, Moritz Diehl
TL;DR
MPC requires QP methods that combine computational speed with reliable handling of challenging optimal-control problems. HPIPM addresses this need with modular QP formulations, IPM solvers, and condensing routines. The paper reports improved reliability over HPMPC and strong speed against state-of-the-art QP solvers for MPC.
Problem
The paper addresses the need for efficient and reliable QP solution building blocks for model predictive control.
Method
HPIPM provides modular IPM solvers for dense, OCP, and tree-structured OCP QPs together with condensing and partial condensing routines.
Results
HPIPM significantly improves reliability over HPMPC on challenging QPs and excels in speed against other state-of-the-art QP solvers for MPC.
Takeaways & Limitations
HPIPM supplies a complete QP framework intended for fast and reliable MPC optimization across multiple QP structures.
Takeaways & Limitations
The current formulation does not support equality constraints other than dynamics equations, so other equalities require reformulation as bounded inequalities.
Abstract
from arXiv · showhide
This paper introduces HPIPM, a high-performance framework for quadratic programming (QP), designed to provide building blocks to efficiently and reliably solve model predictive control problems. HPIPM currently supports three QP types, and provides interior point method (IPM) solvers as well (partial) condensing routines. In particular, the IPM for optimal control QPs is intended to supersede the HPMPC solver, and it largely improves robustness while keeping the focus on speed. Numerical experiments show that HPIPM reliably solves challenging QPs, and that it outperforms other state-of-the-art solvers in speed.
1. INTRODUCTION
HPIPM is an open-source, modular high-performance QP framework for MPC that combines multiple QP formulations, IPM solvers, and condensing routines. It targets extensibility, solver speed, robustness, and integration into broader optimization software.
- Contribution: HPIPM reimplements and extends HPMPC’s QP framework for model predictive control.Its IPM for linear-quadratic optimal control problems is intended to supersede HPMPC’s solver.
- Supported formulations: HPIPM supports dense, OCP, and tree-structured OCP QPs through modular structures and routines for KKT factorization and IPM solution.The same framework defines representations for QPs, solutions, and residuals.
- Solver design: Its IPM solvers offer speed–robustness trade-offs, while shared vector routines remain independent of QP type and matrix format.Computationally intensive KKT modules are specialized by QP type and implemented using BLASFEO.
- Condensing: Condensing and partial condensing convert OCP QPs into dense or shorter-horizon OCP QPs, which can be solved and expanded back through dedicated routines.These routines can also be used independently with other QP solvers.
- Implementation: HPIPM’s setters, getters, and memory management separate user-facing access from solver-oriented internal storage.This design supports convenient data handling and allows internal layouts to change without changing the API.
- Integration: HPIPM is used within several nonlinear programming solvers, including acados, where it supplies the QP framework and preprocessing condensing routines.In acados, HPIPM is deeply integrated into construction and solution of QP approximations.
2. QP FORMULATIONS
HPIPM represents dense, OCP, and tree-structured OCP quadratic programs for common MPC, optimal-control, robust, and scenario-based settings. Its formulations expose structured variables and constraints while allowing dimensions and data to vary across stages or tree nodes.
- 2. QP FORMULATIONS: HPIPM supports dense, OCP, and tree-structured OCP QP formulations, with slack variables treated as a distinctive structured variable type.Slack elimination has computational complexity linear in the number of slack variables.
- 2.1 Dense QP: The dense QP formulation handles generic dense Hessian and constraint matrices arising in single-shooting or state-condensing MPC schemes.It is intended for QP sub-problems whose matrices do not have the stage structure of OCP formulations.
- 2.1 Dense QP: Dense QPs use diagonal slack Hessians and selector matrices to represent box and soft constraints, with two-sided constraints and optional masks.The formulation supports dynamically activating or deactivating individual upper constraints.
- 2.2 OCP QP: The OCP QP formulation covers LQR, constrained linear MPC, and SQP sub-problems for nonlinear OCP and MPC problems.Its dynamics and optimization variables follow the multi-stage structure common to these applications.
- 2.2 OCP QP: OCP QPs couple consecutive stages through dynamics equalities, while costs and inequality constraints are defined stage-wise.State, control, and slack dimensions, along with box and general constraint counts, can vary by stage.
- 2.2 OCP QP: The current OCP formulation supports no equality constraints beyond dynamics equations; other equalities must be represented as inequalities with equal bounds.The stated example is fixing the initial state with equal upper and lower limits.
- 2.3 Tree OCP QP: The tree OCP QP formulation handles common robust and scenario-based OCP and MPC problems.Its data can vary across nodes in the tree.
- 2.3 Tree OCP QP: In the tree formulation, N denotes the node set, L the leaves, and C(n) the children of node n.The cardinality of N is denoted by ˆN.
3. ALGORITHM
HPIPM implements modular primal-dual interior-point algorithms for several structured QP forms, using structure-exploiting KKT factorizations and optional iterative refinement. Its algorithmic choices trade computational speed against robustness and numerical accuracy.
- HPIPM provides modular algorithmic building blocks for variants of primal-dual interior-point methods, enabling speed–robustness trade-offs.
- 3.1 Primal-dual IPM: The infeasible-start Mehrotra predictor-corrector IPM solves relaxed KKT conditions while shrinking the homotopy parameter toward zero.
- 3.2 Delta and absolute IPM formulations: The absolute formulation computes a full-step Newton iterate and can reduce per-iteration cost from quadratic residual evaluation to linear step differencing.
- 3.3 KKT system solution: KKT systems are reduced by eliminating slack and multiplier variables, then solved with structure-exploiting routines tailored to each supported QP type.
- 3.3 KKT system solution: O(N(nx + nu)^3) flops are required for OCP-QP Riccati factorization when state and input dimensions are constant across stages.
- 3.4 Iterative refinement: Iterative refinement reuses the same KKT factorization to cheaply correct inaccurate Newton steps, especially for unstable or ill-conditioned systems.
- 3.5 Condensing and partial condensing: Condensing eliminates stage state variables to produce dense QPs, while partial condensing produces shorter-horizon OCP QPs for subsequent solution and expansion.
4. IMPLEMENTATION
HPIPM’s implementation separates QP-type-independent IPM operations from structure-specific, computationally intensive routines. Predefined modes and numerical safeguards provide configurable speed, accuracy, and robustness.
- HPIPM does not exploit sparsity within matrices; instead, it uses fixed-structure dense, symmetric, triangular, or diagonal matrix operations.
- KKT modules handle the most expensive operations through BLASFEO routines, while their complexities are quadratic or cubic in stage-variable counts.
- IPM core operations are QP-type-independent, linear in the number of variables, and available in generic C and AVX-intrinsics implementations.
- HPIPM offers speed abs, speed, balance, and robust modes that progressively emphasize solution speed, residual checking, numerical safeguards, and refinement.
- QR-based factorizations and additional iterative refinement are used in more robust modes when Cholesky-based factorization accuracy is insufficient.
- Conditional correction steps and optional Hessian regularization are common implementation choices across modes.
5. NUMERICAL EXPERIMENTS
Numerical experiments evaluate HPIPM's speed and robustness across benchmark QPs and MPC simulations. HPIPM's balance mode solves challenging problems reliably, while partially condensed OCP QPs achieve consistently fast solution times.
- The experiments assess HPIPM modes' relative speed and robustness and compare them with state-of-the-art MPC solvers.The evaluations cover the linear mass-spring benchmark, the Maros-Mészáros convex-QP set, and a nonlinear chain-of-masses MPC simulation.
- 5.1 Linear mass spring system: HPIPM speed abs matches HPMPC within 10–15% in solution time, while speed is about 2 times slower for small systems and robust is roughly 3 times slower.The robust-mode overhead results from using a slower but more accurate KKT factorization.
- 5.2 CUTEr: HPIPM balance solves all 43 Maros-Mészáros problems and is within a factor 2 of the fastest solver for more than 90% of them.The required accuracy is 10^-6 for the infinity norm of residuals.
- 5.2 CUTEr: HPIPM speed is fastest on about 50% of the Maros-Mészáros problems but fails on 4, whereas speed abs fails to converge on 32 and is inaccurate on the remainder.These results distinguish the faster modes from the more reliable balance mode on challenging dense QPs.
- 5.3 Chain of masses: In the closed-loop chain-of-masses simulation, HPIPM with partial condensing is fastest, with solution times steadily below 1 millisecond.HPIPM's solution time remains rather constant, while qpOASES and OSQP take longer when early-simulation QPs are more challenging.
6. CONCLUSION
HPIPM is presented as a high-performance QP framework for MPC, combining multiple IPM solvers with condensing routines. Experiments show significantly improved reliability over HPMPC on challenging QPs and strong speed against other state-of-the-art MPC solvers.
- HPIPM provides IPM solvers for dense, OCP, and tree-structured OCP QPs, together with partial condensing routines.
- Compared with HPMPC, HPIPM shows significantly improved reliability on challenging QPs.
- Numerical experiments show that HPIPM speed excels against other state-of-the-art QP solvers for MPC.