In model-predictive control (MPC), an optimization problem has to be solved at each time step, which in real-time applications makes it important to solve these efficiently and to have good upper bounds on worst-case solution time. Often for linear MPC problems, the optimization problem in question is a quadratic program (QP) that depends on parameters such as system states and reference signals. A popular class of methods for solving such QPs is active-set methods, where a sequence of linear systems of equations is solved. We propose an algorithm for computing which sequence of subproblems an active-set algorithm will solve, for every parameter of interest. These sequences can be used to set worst-case bounds on how many iterations, floating-point operations, and, ultimately, the maximum solution time the active-set algorithm requires to converge. The usefulness of the proposed method is illustrated on a set of QPs originating from MPC problems, by computing the exact worst-case number of iterations primal and dual active-set algorithms require to reach optimality.

When Model Predictive Control (MPC) is used in real-time to control linear systems, quadratic programs (QPs) need to be solved within a limited time frame. Recently, several parametric methods have been proposed that certify the number of computations active-set QP solvers require to solve these QPs. These certification methods, hence, ascertain that the optimization problem can be solved within the limited time frame. A shortcoming in these methods is, however, that they do not account for numerical errors that might occur internally in the solvers, which ultimately might lead to optimistic complexity bounds if, for example, the solvers are implemented in single precision. In this paper we propose a general framework that can be incorporated in any of these certification methods to account for such numerical errors.

When solving a quadratic program (QP), one can improve the numerical stability of any QP solver by performing proximal-point outer iterations, resulting in solving a sequence of better conditioned QPs. In this letter we present a method which, for a given multi-parametric quadratic program (mpQP) and any polyhedral set of parameters, determines which sequences of QPs will have to be solved when using outer proximal-point iterations. By knowing this sequence, bounds on the worst-case complexity of the method can be obtained, which is of importance in, for example, real-time model predictive control (MPC) applications. Moreover, we combine the proposed method with previous work on complexity certification for active-set methods to obtain a more detailed certification of the proximal-point methods complexity, namely the total number of inner iterations.

In this technical article, we present a dual active-set solver for quadratic programming that has properties suitable for use in embedded model predictive control applications. In particular, the solver is efficient, can easily be warm started, and is simple to code. Moreover, the exact worst-case computational complexity of the solver can be determined offline and, by using outer proximal-point iterations, ill-conditioned problems can be handled in a robust manner.

We propose a semi-explicit approach for linear MPC in which a dual active-set quadratic programming algorithm is initialized through a pre-computed warm start. By using a recently developed complexity certification method for active-set algorithms for quadratic programming, we show how the computational complexity of the dual active-set algorithm can be determined offline for a given warm start. We also show how these complexity certificates can be used as quality measures when constructing warm starts, enabling the online complexity to be reduced further by iteratively refining the warm start. In addition to showing how the computational complexity of any pre-computed warm start can be determined, we also propose a novel technique for generating warm starts with low overhead, both in terms of computations and memory.