Chance-constrained problems and rare events: an importance sampling approach
Abstract: We study chance-constrained problems in which the constraints involve the probability of a rare event. We discuss the relevance of such problems and show that the existing sampling-based algorithms cannot be applied directly in this case, since they require an impractical number of samples to yield reasonable solutions. Using a Sample Average Approximation (SAA) approach combined with importance sampling (IS) techniques, we show how variance can be reduced uniformly over a suitable approximation of the feasibility set, and as a result the problem can be solved with much fewer samples. We provide sufficient conditions to obtain such uniform variance reduction and prove asymptotic convergence of the combined SAA-IS approach. We apply our methodology to a telecommunications problem, find IS distributions that satisfy the conditions laid out for uniform variance reduction in that context and present numerical results to illustrate the ideas.
Keywords: Chance-constrained programming, Sample Average Approximation, Importance sampling, Rare-event simulation
Category 1: Stochastic Programming
Citation: Universidad Adolfo Ibañez, Feb 2014.
Entry Submitted: 02/26/2014
Modify/Update this entry
|Visitors||Authors||More about us||Links|
Search, Browse the Repository
Give us feedback
|Optimization Journals, Sites, Societies|