Uncertain convex programs: randomized solutions and confidence levels

Many engineering problems can be cast as optimization problems subject to convex constraints that are parameterized by an uncertainty or instance parameter. Two main approaches are generally available to tackle constrained optimization problems in presence of uncertainty: robust optimization and chance-constrained optimization. Robust optimization is a deterministic paradigm where one seeks a solution which simultaneously satisfies all possible constraint instances. In chance-constrained optimization a probability distribution is instead assumed on the uncertain parameters, and the constraints are enforced up to a pre-specified level of probability. Unfortunately however, both approaches lead to computationally intractable problem formulations.In this paper, we consider an alternative randomized or scenario approach for dealing with uncertainty in optimization, based on constraint sampling. In particular, we study the constrained optimization problem resulting by taking into account only a finite set of N constraints, chosen at random among the possible constraint instances of the uncertain problem. We show that the resulting randomized solution fails to satisfy only a small portion of the original constraints, provided that a sufficient number of samples is drawn. Our key result is to provide an efficient and explicit bound on the measure (probability or volume) of the original constraints that are possibly violated by the randomized solution. This volume rapidly decreases to zero as N is increased.This work is supported in part by the European Commission under the project HYBRIDGE IST-2001-32460, and by MIUR under the project New methods for Identification and Adaptive Control for Industrial Systems, and the FIRB project Learning, randomization and guaranteed predictive inference for complex uncertain systems.Acknowledgement We wish to thank Professor Arkadi Nemirovski for his encouragement in pursuing this line of research. We also acknowledge the many valuable comments from anonymous reviewers that helped improve this paper.