Efficient interior point methods for multistage problems arising in receding horizon control

TLDR

Receding horizon control requires solving an optimization problem at every sampling instant. The authors develop efficient interior‑point methods for convex multistage problems, enabling high‑speed, numerically stable implementations for most linear‑dynamics MPC applications. They categorize common MPC formulations by complexity and use a low‑rank forward‑substitution scheme to accelerate quadratic or linear constraints, providing implementation details that yield 2–5× faster speed and 3–70× smaller code than three benchmark solvers. The solver supports quadratic constraints, handles large problem sizes efficiently, and outperforms state‑of‑the‑art solvers by factors of 2–5 in speed and 3–70 in code size, making advanced MPC feasible on low‑cost embedded hardware.

Abstract

Receding horizon control requires the solution of an optimization problem at every sampling instant. We present efficient interior point methods tailored to convex multistage problems, a problem class which most relevant MPC problems with linear dynamics can be cast in, and specify important algorithmic details required for a high speed implementation with superior numerical stability. In particular, the presented approach allows for quadratic constraints, which is not supported by existing fast MPC solvers. A categorization of widely used MPC problem formulations into classes of different complexity is given, and we show how the computational burden of certain quadratic or linear constraints can be decreased by a low rank matrix forward substitution scheme. Implementation details are provided that are crucial to obtain high speed solvers.We present extensive numerical studies for the proposed methods and compare our solver to three well-known solver packages, outperforming the fastest of these by a factor 2-5 in speed and 3-70 in code size. Moreover, our solver is shown to be very efficient for large problem sizes and for quadratically constrained QPs, extending the set of systems amenable to advanced MPC formulations on low-cost embedded hardware.