TY - JOUR

T1 - Chance-constrained problems and rare events

T2 - an importance sampling approach

AU - Barrera, Javiera

AU - Homem-de-Mello, Tito

AU - Moreno, Eduardo

AU - Pagnoncelli, Bernardo K.

AU - Canessa, Gianpiero

N1 - Publisher Copyright:
© 2015, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.

PY - 2016/5/1

Y1 - 2016/5/1

N2 - 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. We argue that importance sampling (IS) techniques, combined with a Sample Average Approximation (SAA) approach, can be effectively used in such situations, provided that variance can be reduced uniformly with respect to the decision variables. We give sufficient conditions to obtain such uniform variance reduction, and prove asymptotic convergence of the combined SAA-IS approach. As it often happens with IS techniques, the practical performance of the proposed approach relies on exploiting the structure of the problem under study; in our case, we work with a telecommunications problem with Bernoulli input distributions, and show how variance can be reduced uniformly over a suitable approximation of the feasibility set by choosing proper parameters for the IS distributions. Although some of the results are specific to this problem, we are able to draw general insights that can be useful for other classes of problems. We present numerical results to illustrate our findings.

AB - 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. We argue that importance sampling (IS) techniques, combined with a Sample Average Approximation (SAA) approach, can be effectively used in such situations, provided that variance can be reduced uniformly with respect to the decision variables. We give sufficient conditions to obtain such uniform variance reduction, and prove asymptotic convergence of the combined SAA-IS approach. As it often happens with IS techniques, the practical performance of the proposed approach relies on exploiting the structure of the problem under study; in our case, we work with a telecommunications problem with Bernoulli input distributions, and show how variance can be reduced uniformly over a suitable approximation of the feasibility set by choosing proper parameters for the IS distributions. Although some of the results are specific to this problem, we are able to draw general insights that can be useful for other classes of problems. We present numerical results to illustrate our findings.

KW - Chance-constrained programming

KW - Importance sampling

KW - Rare-event simulation

KW - Sample average approximation

UR - http://www.scopus.com/inward/record.url?scp=84940925267&partnerID=8YFLogxK

U2 - 10.1007/s10107-015-0942-x

DO - 10.1007/s10107-015-0942-x

M3 - Article

AN - SCOPUS:84940925267

SN - 0025-5610

VL - 157

SP - 153

EP - 189

JO - Mathematical Programming

JF - Mathematical Programming

IS - 1

ER -