The Talk will be held at IDSIA, Meeting Room, Galleria 1, Thursday 15th of January, 11 am

A Distributed Accelerated Dual Gradient Projection Algorithm for Large-scale Stochastic Model Predictive Control

P. Sopasakis and A.K. Sampathirao,
IMT Institute for Advanced Studies Lucca, Piazza San Ponziano, 6, 55100, Lucca, Italy.

Uncertainty is ubiquitous – is it measurement noise or modelling uncertainty or any other type, it inevitably needs to be taken into account when modelling a dynamical system and, of course, when a control system needs to be designed. Large-scale uncertain systems such as power production plants and power distribution grids, drinking water networks and irrigation systems, computer networks and more have attracted a lot of attention and call for advanced control methodologies to cope with the computational difficulties that arise. In this talk, I will motivate the development of advanced numerical algorithms for large-scale systems and present a distributed variant of a dual first order method for stochastic model predictive control (MPC).

Two well-established approaches have been presented in the literature for dealing with system uncertainty: robust and stochastic control. For both cases, numerous model predictive control formulations have been proposed to accommodate state and input constraints and control the system while optimising some desired performance criterion. Although stochastic control has been shown to be less conservative and enjoy plenty favourable theoretical properties, its applicability is conditioned by its complexity. In particular, two major approaches are pursued when modelling uncertainty: it is either assumed that the uncertain parameters follow the normal distribution (or some other distribution whose cumulative inverse is known exactly), or it is assumed that the uncertainty is finite-valued and evolves as a tree of scenarios. The normality assumption is often not met while the latter approach offers greater flexibility at the cost of higher computational complexity. Therefore, computational feasibility has been a limiting factor for stochastic model predictive control algorithms; overcoming this limitation was the main motivation for the work I am going to present.

General-purpose graphics processing units (GP-GPUs) are gaining increased popularity for scientific computations. They offer unprecedented computational capabilities, which may amount up to almost 9000GFlop/s in single precision or 3000GFlop/s in double precision. Our ability to master and harness this computational power depends on the availability of algorithms able to properly decompose the problem into simple sub-problems and iterate over those in lockstep (i.e., performing the same set of operations at the same time in parallel over a different set of data).

We designed an accelerated dual gradient projection algorithm for tree-based stochastic model predictive control problems and implemented it on GPUs, which afforded a minimum speed-up of 50x (with respect to a CPU implementation). We compared the performance of the proposed algorithm with Gurobi, a widely used solver for quadratic optimisation problems, and recorded speed-ups of 1 to 3 orders of magnitude. Additionally, the accuracy of the proposed algorithm can be controlled so that less accurate solutions are obtained faster for which, however, explicit sub-optimality and infeasibility bounds are known. The proposed algorithm is well-suited for stochastic MPC problems and paves the way for its application in many fields of interest.