Randomized methods for design of uncertain systems: Sample complexity and sequential algorithms

In this paper, we study randomized methods for feedback design of uncertain systems. The first contribution is to derive the sample complexity of various constrained control problems. In particular, we show the key role played by the binomial distribution and related tail inequalities, and compute th e sample complexity. This contribution significantly improves the existing results by reducing the number of required samples in the andomized algorithm. These results are then applied to the analysis of worst-case performance and design with robust optimization. The second contribution of the paper is to introduce a general class of sequential algorithms, denote das Sequential Probabilistic Validation (SPV). In these se quential algorithms, at each iteration, a candidate solution is prob abilistically validated, and corrected if necessary, to me et the required specifications. The results we derive provide the sample com plexity which guarantees that the solutions obtained with SPV algorithms meet some pre-specified probabilistic accuracy and confidence. The performance of these algorithms is illus trated and compared with other existing methods using a numerical e xample dealing with robust system identification.