TR2013-108

On a Multiplicative Update Dual Optimization Algorithm for Constrained Linear MPC



We discuss a multiplicative update quadratic programming algorithm with applications to model predictive control for constrained linear systems. The algorithm, named PQP, is very simple to implement and thus verify, does not require projection, offers a linear rate of convergence, and can be completely parallelized. The PQP algorithm is equipped with conditions that guarantee the desired bound on sub-optimality and with an acceleration step based on projection-free line search. We also show how PQP can take advantage of the parametric structure of the MPC problem, thus moving offline several calculations and avoiding large input/output dataflows. The algorithm is evaluated on two benchmark problems, where it is shown to compete with, and possibly outperform, other open source and commercial packages.