# A Unifying Complexity Certification Framework for Active-Set Methods for Convex Quadratic Programming

arXiv: https://arxiv.org/abs/2003.07605 · HTML: https://mlsanity.com/paper/2003.07605/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 17 Mar 2020.

## Built on by (most cited first, 1 of 1)

- [A direct optimization algorithm for input-constrained MPC](https://mlsanity.com/paper/2306.15079/) (2023)

## Abstract (arXiv)

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 optimization problems 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. By knowing these sequences, a worst-case bound on how many iterations, and ultimately the maximum time, the active-set algorithm requires to converge can be determined. 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.