A Sample Approximation Approach for Optimization with Probabilistic Constraints

James Luedtke (jluedtkus.ibm.com)
Shabbir Ahmed (sahmedisye.gatech.edu)

Abstract: We study approximations of optimization problems with probabilistic constraints in which the original distribution of the underlying random vector is replaced with an empirical distribution obtained from a random sample. We show that such a sample approximation problem with risk level larger than the required risk level will yield a lower bound to the true optimal value with probability approaching one exponentially fast. This leads to an a priori estimate of the sample size required to have high confidence that the sample approximation will yield a lower bound. We then provide conditions under which solving a sample approximation problem with a risk level smaller than the required risk level will yield feasible solutions to the original problem with high probability. Once again, we obtain a priori estimates on the sample size required to obtain high confidence that the sample approximation problem will yield a feasible solution to the original problem. Finally, we present numerical illustrations of how these results can be used to obtain feasible solutions and optimality bounds for optimization problems with probabilistic constraints.

Keywords: Probabilistic constraints, chance constraints, stochastic programming, Monte Carlo, large deviations

Category 1: Stochastic Programming

Citation: Georgia Institute of Technology, 765 Ferst Drive, Atlanta, GA, 30332, Sep/2007.

Download: [PDF]

Entry Submitted: 09/15/2007
Entry Accepted: 09/15/2007
Entry Last Modified: 05/02/2008

Modify/Update this entry