Exact Complexity Certification of Active-Set Methods for Quadratic Programming

Authors:
Publisher website
Google Scholar
Abstract
Active-set methods are recognized to often outperform other methods in terms of speed and solution accuracy when solving small-size Quadratic Programming (QP) problems, making them very attractive in embedded linear Model Predictive Control (MPC) applications. A drawback of active-set methods is the lack of tight bounds on the worst-case number of iterations, a fundamental requirement for their implementation in a real-time system. Extensive simulation campaigns provide an indication of the expected worst-case computation load, but not a complete guarantee. This paper solves such a certification problem by proposing an algorithm to compute the exact bound on the maximum number of iterations and floating point operations required by a state-of-the-art dual active-set QP solver. The algorithm is applicable to a given QP problem whose linear term of the cost function and right hand side of the constraints depend linearly on a vector of parameters, as in the case of linear MPC. In addition, a new solver is presented that combines explicit and implicit MPC ideas, guaranteeing improvements of the worst-case computation time. The ability of the approach to exactly quantify memory and worst-case computation requirements is tested on a few MPC examples, also highlighting when on-line optimization should be preferred to explicit MPC.

This publication has 40 references indexed in Scilit: