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.
Preprint, School of Indusrtial and Systems Engineering, Georgia Institute of Technology