Convex Approximations of Chance Constrained Programs

• Published in: SIAM journal on optimization 2006-01, Vol.17 (4), p.969-996
• Main Authors: Nemirovski, Arkadi, Shapiro, Alexander
• Format: Article
• Language: English
• Subjects: Approximation; Monte Carlo simulation; Optimization; Probability distribution; Random variables; Sample size
• ISSN: 1052-6234; 1095-7189
• DOI: 10.1137/050622328

We consider a chance constrained problem, where one seeks to minimize a convex objective over solutions satisfying, with a given close to one probability, a system of randomly perturbed convex constraints. This problem may happen to be computationally intractable; our goal is to build its computationally tractable approximation, i.e., an efficiently solvable deterministic optimization program with the feasible set contained in the chance constrained problem. We construct a general class of such convex conservative approximations of the corresponding chance constrained problem. Moreover, under the assumptions that the constraints are affine in the perturbations and the entries in the perturbation vector are independent-of-each-other random variables, we build a large deviation-type approximation, referred to as "Bernstein approximation," of the chance constrained problem. This approximation is convex and efficiently solvable. We propose a simulation-based scheme for bounding the optimal value in the chance constrained problem and report numerical experiments aimed at comparing the Bernstein and well-known scenario approximation approaches. Finally, we extend our construction to the case of ambiguous chance constrained problems, where the random perturbations are independent with the collection of distributions known to belong to a given convex compact set rather than to be known exactly, while the chance constraint should be satisfied for every distribution given by this set.