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.

In this paper we present a method to exactly certify the iteration complexity of a primal active-set algorithm for quadratic programs which is terminated early, given a specific multi-parametric quadratic program. The primal active-set algorithms real-time applicability is, hence, improved by early termination, increasing its computational efficiency, and by the proposed certification method, providing guarantees on worst-case behaviour. The certification method is illustrated on a multi-parametric quadratic program originating from model predictive control of an inverted pendulum, for which the relationship between allowed suboptimality and iterations needed by the primal active-set algorithm is presented. Copyright (C) 2020 The Authors.

In this letter we propose a method to exactly certify the complexity of an active-set method which is based on reformulating strictly convex quadratic programs to nonnegative least-squares problems. The exact complexity of the method is determined by proving the correspondence between the method and a standard primal active-set method for quadratic programming applied to the dual of the quadratic program to be solved. Once this correspondence has been established, a complexity certification method which has already been established for the primal active-set method is used to also certify the complexity of the nonnegative least-squares method. The usefulness of the proposed method is illustrated on a multi-parametric quadratic program originating from model predictive control of an inverted pendulum.

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.