Note: This content is accessible to all versions of every browser. However, this browser does not seem to support current Web standards, preventing the display of our site's design details.


Computational Complexity Certification for Real-Time MPC with Input Constraints Based on the Fast Gradient Method


S. Richter, C. Jones, M. Morari

IEEE Transactions on Automatic Control, vol. 57, no. 6, pp. 1391 - 1403

This paper proposes to use Nesterov's fast gradient method for the solution of linear quadratic model predictive control (MPC) problems with input constraints. The main focus is on the method's a priori computational complexity certification which consists of deriving lower iteration bounds such that a solution of pre-specified suboptimality is obtained for any possible state of the system. We investigate cold- and warm-starting strategies and provide an easily computable lower iteration bound for cold-starting and an asymptotic characterization of the bounds for warm-starting. Moreover, we characterize the set of MPC problems for which small iteration bounds and thus short solution times are expected. The theoretical findings and the practical relevance of the obtained lower iteration bounds are underpinned by various numerical examples and compared to certification results for a primal-dual interior point method.

Further Information

Type of Publication:


M. Morari

File Download:

Request a copy of this publication.
(Uses JavaScript)
% Autogenerated BibTeX entry
@Article { RicJon:2012:IFA_3894,
    author={S. Richter and C. Jones and M. Morari},
    title={{Computational Complexity Certification for Real-Time MPC
	  with Input Constraints Based on the Fast Gradient Method}},
    journal={IEEE Transactions on Automatic Control},
    pages={1391 -- 1403},
Permanent link