Convex Approximations of Chance Constrained Programs

TLDR

A chance constrained problem seeks to minimize a convex objective while satisfying randomly perturbed convex constraints with high probability. The authors aim to construct a computationally tractable deterministic approximation whose feasible set lies within the original chance constrained problem. They develop a family of convex conservative approximations, including a Bernstein large‑deviation approximation for affine, independent perturbations, a simulation‑based bounding scheme, and an extension to ambiguous distributions, and compare these to the scenario approach. The Bernstein approximation is convex, efficiently solvable, and simulation experiments demonstrate its performance relative to the scenario method.

Abstract

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.