Scenario Approximations of Chance Constraints

Arkadi Nemirovski (nemirovsie.technion.ac.il)
Alexander Shapiro (ashapiroisye.gatech.edu)

Abstract: We consider an optimization problem of minimization of a linear function subject to chance constraints. In the multidimensional case this problem is, generically, a problem of minimizing under a nonconvex and difficult to compute constraints and as such is computationally intractable. We investigate the potential of conceptually simple scenario approximation of the chance constraints. The emphasis is on the situation where the solution to the approximation should, with high probability, be feasible for the problem of interest, while the sample size N should be polynomial in the size of this problem and in minus-logarithm of the corresponding probability parameters epsilon and delta.

Keywords: Convex optimization, stochastic uncertainty, chance constraints, Monte Carlo sampling, importance sampling

Category 1: Stochastic Programming

Category 2: Other Topics (Optimization of Simulated Systems )

Citation: Preprint, School of Indusrtial and Systems Engineering, Georgia Institute of Technology

Download: [PDF]

Entry Submitted: 11/15/2004
Entry Accepted: 11/15/2004
Entry Last Modified: 11/15/2004

Modify/Update this entry