IFAC 2014 Tutorial: Randomized methods for analysis and design of control
At the upcoming IFAC World Conference, August 24-29, 2014, Cape Town, South Africa, the following tutorial will be organized:
Randomized methods for analysis and design of control systems
August 24, 2014 from 8.30 to 16.30
For additional information, please visit the IFAC tutorials webpage.
For registering to the tutorial, please visit the IFAC registration webpage
The slides of the workshop are now available:
- Campi - introduction to scenario
- Garatti - fundamental theorems SA
- Prandini - channel equalization
- Tempo - introduction and randomized algorithms
- Dabbene - sequential design methods
The objective of this tutorial is to introduce the attendee to randomized methods for the analysis and design of control systems. Randomized methods are an emerging technology to address problems that are otherwise difficult to solve along more traditional approaches. The main underlying idea is to replace the normally infinite set of possible uncertainty outcomes with finitely many samples that are representative of the uncertainty domain. One of the main properties which makes randomized methods attractive is that the solutions they provide come accompanied by precise probabilistic guarantees that also refer to unseen cases in the uncertainty domain. This is relevant to probabilistic performance guarantees, as well as to a certified satisfaction of control constraints. Depending on the application at hand, the samples can be drawn from a probabilistic model of uncertainty, or they can be obtained as observations. The latter situation covers data-based approaches in learning and identification.
Samples can be used all at the same time (batch or scenario approach) or in succession (sequential methods). This tutorial covers both situations. The scenario approach is a well established paradigm that can be used to solve convex uncertain optimization problems arising in control. Sequential methods are instead very well suited for feasibility problems, and the presentation will emphasize the many pros and achievements obtained in this direction. The presentation will be gradual to allow an in-depth understanding of the fundamental concepts. Practical examples will illustrate the main ideas, and a presentation of open problems will complete the tutorial.
Main topics and tutorial structure
A randomized algorithm is an algorithm that makes random choices based on samples extracted from a pre-assigned probability distribution. Hence, the returned numerical results are subject to randomness. The level of randomness, however, can be kept under control by means of many results available in the existing literature.
Randomized algorithms have been successfully used since the forties in diverse scientific disciplines such as computer science, physics, numerical analysis, and optimization. In control, the introduction of randomized methods is more recent, but randomized methods are gaining popularity and spreading rapidly due to their ability to overcome the computational difficulties that arise with more traditional deterministic approaches.
The goal of the tutorial is to introduce the attendee to randomized methods for the analysis and design of control systems. The existing methods can be grouped in two categories:
batch (scenario) approach;
Both will be covered in the tutorial.
Batch approach - the scenario method
The ``scenario approach'' is a sample-based technique to address uncertain convex optimization problems arising in control design. It offers a viable way to obtain chance-constrained feasible solutions that exhibits empirical optimality. This tutorial aims at providing the attendee with a broad introduction to the scenario approach, followed by a more-in-depth presentation of the foundational mathematical aspects at its basis, and some application examples. A detailed description of the main topics is as follows.
The scenario approach to control
Many problems in control are formulated as optimization problems. In many cases, the cost function incorporates variables that are used to model uncertainty, in addition to optimization variables. The scenario approach is first presented as a method to optimize an uncertain cost function. The main idea of sampling from the uncertainty set and optimizing with the sampled scenarios as constraints is introduced.
The scenario approach stands on some fundamental theoretical results, which make this approach mathematically solid. The mathematical foundations of the scenario approach will be reviewed in a self-contained manner.
Modulating Robustness in Control Design: Principles and Algorithms
Robust control can lead to designs that are overconservative because all emphasis is placed on safe-guarding against all possible occurrences. When 100\% guarantee of robustness is required, standard robust control is indeed the way to go. However, in many applications, robustness in 100\% of the cases is not really necessary and it is a fact that accepting a small compromise in robustness guarantees (e.g. accepting a 99\% guarantee) can lead to a huge improvement in performance. It will be shown that the scenario approach offers a viable way to find a suitable trade-off between risk and return by constraint removal.
Empirical distribution of costs
In correspondence of the sampled instances of the uncertain parameter, the scenario solution incurs various costs called ``empirical costs'', which offer an empirical description of the cost distribution. A precise characterization of the risks associated to the empirical costs, namely an evaluation of the probability that the various empirical costs are exceeded by new situations, is presented.
The sequential randomized algorithms that we study in this tutorial provide a generalization of all the sequential methods that have been previously analyzed in the literature for specific convex control problems subject to structured random uncertainty. These problems include the design of linear quadratic regulators and solutions to linear matrix inequalities under uncertainty.
In particular, we study randomized sequential methods for finding a probabilistic feasible solution (i.e. a solution which holds with high probability) to a convex constraint in the design variables and subject to nonlinear structured random uncertainty. The algorithms presented in the literature are based on two fundamental ingredients:
an Oracle, which should check probabilistic feasibility of a candidate solution;
an Update Rule, which exploits the convexity of the problem for constructing a new candidate solution based on the Oracle outcome.
We now describe these two ingredients.
The Oracle constitutes the randomized part of the algorithm, and its role is to decide probabilistic feasibility of the current solution. This decision is made based on random samples of the uncertainty. One of the objectives is to derive the sample complexity, i.e. the number of random samples to be drawn. We remark that in this case the sample complexity cannot be obtained using classical bounds like the Chernoff bound because the generated samples along the iterations are not statistically independent. We show, however, a simple formula which provides the sample complexity, showing that the obtained sample size is independent of the number of uncertain and design parameters, and which depends very mildly (in a logarithmic fashion) on the number of iterations and probabilistic levels. This is one of the key features of these algorithms, which enjoy polynomial-time complexity. For this reason, these algorithms are said to break the curse of dimensionality, at the expense of a probability of violation.
Various update rules have been proposed in the literature. The first one that has been studied is based on a (sub)gradient descent technique. More sophisticated techniques, which improve convergence rates, have been subsequently developed and fall in the class of the so-called random localization methods. These methods require the computation at each step of the algorithm of a center of a suitably constructed localization set, which is then used as the candidate solution of the problem. In particular, in probabilistic cutting plane methods, the localization set is a polytope, and the candidate solution is its analytic center. In the probabilistic ellipsoid algorithm, the localization set is an ellipsoid and the candidate solution is its center.
Several probabilistic properties for these algorithms have been established and are discussed in this tutorial. In particular, the convergence properties, the required number of iterations, the probability of a successful exit of the algorithm or the derivation of a violation certificate (in case of unsuccessful exit of the algorithm), are studied in great details. We also discuss the differences with other classical approaches developed in the area of stochastic approximation methods.
A Posteriori Analysis
Subsequently, we study a posteriori analysis (both probabilistic and deterministic) to establish the goodness of the solution obtained by the proposed sequential randomized algorithm. In particular, for deterministic analysis, we discuss methods based on classical extreme point results developed in robust control, while for probabilistic analysis, Monte Carlo techniques based on random extractions of uncertainty samples are explained.
Randomized Algorithms Control Toolbox
Batch and sequential algorithms previously discussed have been implemented in Matlab in the toolbox RACT (Randomized Algorithms Control Toolbox). This toolbox provides convenient uncertain object manipulation and implementation of these methods. Simulations and numerical examples are performed to show the efficacy of the proposed methodology. The package can be freely downloaded here.
Related publications (selected)
Randomized Algorithms for Analysis and Control of Uncertain Systems: With Applications
2nd Edition, Springer-Verlag - Series: Communications and Control Engineering, XXI, 357 p., Hardcover, 2013, ISBN: 978-1-4471-4609-4
Modulating Robustness in Control Design: Principles and Algorithms.
IEEE Control Systems Magazine, 33: 36-51, 2013.
Research on Probabilistic Methods for Control System Design
AUTOMATICA, Vol. 47, pp. 1279-1293, 2011
Probabilistic and Randomized Tools for Control Design
The Control Handbook, Second Edition (W. S. Levine, Editor), Taylor and Francis, London, pp. 65.1-65.23, 2010.
The Scenario Approach for Systems and Control Design.
Annual Reviews in Control, 33:149-157, 2009.
The Exact Feasibility of Randomized Solutions of Uncertain Convex Programs.
SIAM Journal on Optimization, 19, no.3: 1211-1230, 2008.
The Scenario Approach to Robust Control Design.
IEEE Trans. on Automatic Control, AC-51:742-753, 2006.