๐”– Bobbio Scriptorium
โœฆ   LIBER   โœฆ

Convex Approximations of Chance Constrained Programs

โœ Scribed by Nemirovski, Arkadi; Shapiro, Alexander


Book ID
118204672
Publisher
Society for Industrial and Applied Mathematics
Year
2007
Tongue
English
Weight
321 KB
Volume
17
Category
Article
ISSN
1052-6234

No coin nor oath required. For personal study only.

โœฆ Synopsis


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.


๐Ÿ“œ SIMILAR VOLUMES