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 of Gradient Methods for Real-Time Model Predictive Control


S. Richter

Zurich, Switzerland

The main objective of this thesis is to derive practically relevant certificates for the computational complexity of real-time model predictive control (MPC). MPC is a well-established method for the control of systems that are subject to constraints in the inputs and/or states. Since MPC requires the solution to an optimization problem at the sampling rate of the control loop, it is considered a computationally intensive control method. Even for the class of convex optimization problems, which are solvable by state-of-the-art optimization methods, the complexity of obtaining a solution is either unknown a priori or does not correspond to the practically observed complexity at all. However, a certified operation of the optimization routine is relevant in view of MPC applications for systems with fast dynamics that require sampling times in the milli- to microseconds range, e.g., grid power converters.

The complexity of an optimization method is best expressed by an upper bound on the required number of floating point operations that in turn stems from an upper bound on the iteration count. Knowing a meaningful upper bound a priori would enable control engineers to use optimization-based control in safety-critical and risk-of-loss applications, guide the selection of control hardware before implementation and reduce extensive and costly testing procedures of the optimization routine. Even if certification is not an issue in an application, the understanding of the entities that define (expressive) iteration bounds can help to modify the problem at hand in a way such that faster practical convergence can be achieved, saving computational resources.

This thesis investigates certification aspects for the most common class of constrained linear-quadratic MPC problems. After confirming that existing state-of-the-art solution methods for MPC do not allow for meaningful complexity certificates, Nesterov's fast gradient method is proposed as an alternative. The fast gradient method is an accelerated variant of the classic gradient method and provides a significant speed-up at the same iteration cost. Moreover, its simple algorithmic scheme and its applicability to a wide class of optimization problems make it a viable optimization method for low-resource processors such as found in embedded systems. Although the method has existed since the early 80s, it was practically unknown in the control community. In this sense, this work has also contributed to making it known to a wider audience and other control labs have started projects on the use of the fast gradient method in the meantime.

In order to account for that and since a similar overview of the method is missing in the literature, the first part of the thesis provides a self-contained treatment of the fast gradient method and its latest generalization, the (accelerated) proximal gradient method. From this it becomes clear that no other gradient-based method can provide better certificates for MPC and also, that the fast gradient method's certificates are indeed practically relevant for the considered MPC problems in this thesis. In addition, two new stopping criteria for gradient-based methods are derived that allow to detect sufficient optimality even before the certified iteration bound is reached.

In the second part, we start with certificates for input-only constrained MPC, which - after changing the problem formulation - can be conveniently solved by the fast gradient method in the primal domain. The validity of the obtained certificates crucially depends on the initialization of the fast gradient method. Therefore, a generic initialization scheme is derived and specialized variants for cold- and warm-starting deduced. Computation of the `best' bound on the iteration count turns out to be computationally expensive as it requires the solution to a bilevel optimization problem. However, an easy-to-compute, while still expressive bound can be derived for cold-starting. In order to understand for which MPC problem setups low bounds and thus short solution times can be expected, their dependence on the problem data is analyzed, and it is found that the certificates do not necessarily get worse when the prediction horizon in MPC is increased, which at first seems counterintuitive. The application of the certification scheme to several real-world MPC problems, such as a power converter, proves the practical relevance of the obtained bounds and shows that the fast gradient method is the method of choice for most of these problems.

In the input- and state-constrained MPC case, the fast gradient method is shown to be applicable in the dual domain only. This implies that the guaranteed convergence rate changes from linear in the primal to the slower sublinear rate in the dual domain. Reduced convergence speed means that the entities defining the upper iteration bound need to be known with the least amount of conservatism in order to result in a meaningful bound. Motivated by this, the derivation of the smallest values of these entities is considered. It turns out that the first entity, which is the smallest Lipschitz constant of the dual gradient, can be computed exactly whereas the other entity, the worst case minimal distance between an initial dual iterate and a Lagrange multiplier, can only be upper bounded with much conservatism. The conservatism causes the bounds for a real-world ball on plate system to be too large to be practical. For this reason, a theoretical framework for the investigation of a less conservative bound is introduced and it is found that under specific assumptions improved upper bounds can be found.

Finally, optimal preconditioning for better certificates and increased computational speed is studied for both the primal and the dual domain.

Further Information

Type of Publication:

(03)Ph.D. Thesis

M. Morari

No Files for download available.
% Autogenerated BibTeX entry
@PhDThesis { Xxx:2012:IFA_4274,
    author={S. Richter},
    title={{Computational Complexity Certification of Gradient Methods
	  for Real-Time Model Predictive Control}},
    address={Zurich, Switzerland},
Permanent link