9:38 p.m.
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.