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.
Citation
Universidad Adolfo Ibañez, Feb 2014.