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.