Randomization in Systems and Control

Abstract

Designs in systems and control are traditionally carried out through deterministic algorithms consisting of a sequence of steps set by deterministic rules. This approach, however, can be generalized by the introduction of randomization: a randomized algorithm is an algorithm where one or more steps are based on a random rule, that is – among many deterministic rules – one rule is selected according to a random scheme. Randomization has turned out to be a powerful tool for solving a number of problems deemed unsolvable with deterministic methods.

A crucial fact is that randomization permits one to introduce the notion of ``probabilistically successful algorithm''. In many cases, when deterministic successfulness cannot be achieved, probabilistic successfulness offers a valid alternative.

In the talk, the use of randomized algorithms will be discussed in relation to several problems:

• robust design (e.g. by means of linear matrix inequalities - LMIs) is computationally difficult. Randomized methods come into play by offering alternative design methodologies;
• in estimation and identification, randomization can change our perception of what constitutes an impossible problem, and estimation problems which were deemed impossible can be successfully solved in a probabilistic sense;
• trading robustness for performance is a central issue in decision making and new methods for achieving a compromise can be obtained through randomization.