Abstract
We consider the problem of choosing design parameters to minimize the probability of an undesired rare event that is described through the average of n i.i.d. random variables. Since the probability of interest for near optimal design parameters is very small, one needs to develop suitable accelerated Monte-Carlo methods for estimating its value. One of the challenges in the study is that simulating from exponential twists of the laws of the summands may be computationally demanding since these transformed laws may be non-standard and intractable. We consider a setting where the summands are given as a nonlinear functional of random variables, the exponential twists of whose distributions take a simpler form than those for the original summands. We use techniques from Dupuis and Wang (Stochastics 76(6):481–508, 2004, Math Oper Res 32(3):723–757, 2007) to identify the appropriate Issacs equations whose subsolutions are used to construct tractable importance sampling (IS) schemes. We also study the closely related problem of estimating buffered probability of exceedance and provide the first rigorous results that relate the asymptotics of buffered probability and that of the ordinary probability under a large deviation scaling. The analogous minimization problem for buffered probability, under conditions, can be formulated as a convex optimization problem. We show that, under conditions, changes of measures that are asymptotically efficient (under the large deviation scaling) for estimating ordinary probability are also asymptotically efficient for estimating the buffered probability of exceedance. We embed the constructed IS scheme in gradient descent algorithms to solve the optimization problems, and illustrate these schemes through computational experiments.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Barrera, J., Homem-de Mello, T., Moreno, E., Pagnoncelli, B. K., & Canessa, G. (2016). Chance-constrained problems and rare events: An importance sampling approach. Mathematical Programming, 157(1), 153–189.
Bertsekas, D. P. (2009). Convex Optimization Theory. Belmont: Athena Scientific.
Bremer, I., Henrion, R., & Möller, A. (2015). Probabilistic constraints via SQP solver: Application to a renewable energy management problem. Computational Management Science, 12(3), 435–459.
Bucklew, J. A. (1990). Large Deviation Techniques in Decision, Simulation, and Estimation. New York: Wiley.
Calafiore, G. C., & Campi, M. C. (2006). The scenario approach to robust control design. IEEE Transactions on Automatic Control, 51(5), 742–753.
Chen, J. C., Lu, D., Sadowsky, J. S., & Yao, K. (1993). On importance sampling in digital communications. I. Fundamentals. IEEE Journal on Selected Areas in Communications, 11(3), 289–299.
Collamore, J. F. (2002). Importance sampling techniques for the multidimensional ruin problem for general Markov additive sequences of random vectors. Annals of Applied Probability, 12(1), 382–421.
Dentcheva, D., & Martinez, G. (2013). Regularization methods for optimization problems with probabilistic constraints. Mathematical Programming, 138, 223–251.
Dupuis, P., & Ellis, R. S. (2011). A Weak Convergence Approach to the Theory of Large Deviations. New York: Wiley.
Dupuis, P., & Wang, H. (2004). Importance sampling, large deviations, and differential games. Stochastics: An International Journal of Probability and Stochastic Processes, 76(6), 481–508.
Dupuis, P., & Wang, H. (2007). Subsolutions of an Isaacs equation and efficient schemes for importance sampling. Mathematics of Operations Research, 32(3), 723–757.
Ellis, R. S. (2007). Entropy, Large Deviations, and Statistical Mechanics. New York: Springer.
Evans, M., & Swartz, T. (2000). Approximating integrals via Monte Carlo and deterministic methods. Oxford: OUP Oxford.
Glasserman, P., Wang, Y., et al. (1997). Counterexamples in importance sampling for large deviations probabilities. The Annals of Applied Probability, 7(3), 731–746.
L’Ecuyer, P., & Tuffin, B. (2011). Approximating zero-variance importance sampling in a reliability setting. Annals of Operations Research, 189(1), 277–297.
Mafusalov, A., & Uryasev, S. (2014). Buffered probability of exceedance: Mathematical properties and optimization algorithms (p. 1). Risk Management and Financial Engineering Lab: Department of Industrial and Systems Engineering, University of Florida, Research Report.
Mafusalov, A., Shapiro, A., & Uryasev, S. (2015). Estimation and asymptotics for buffered probability of exceedance (p. 5). Risk Management and Financial Engineering Lab: Department of Industrial and Systems Engineering, University of Florida, Research Report.
Nemirovski, A., & Shapiro, A. (2006). Convex approximations of chance constrained programs. SIAM Journal on Optimization, 17(4), 969–996.
Owen, A., & Zhou, Y. (2000). Safe and effective importance sampling. Journal of the American Statistical Association, 95(449), 135–143.
Pagnoncelli, B., Ahmed, S., & Shapiro, A. (2009). Sample average approximation method for chance constrained programming: Theory and applications. Journal of Optimization Theory and Applications, 142(2), 399–416.
Prékopa, A. (2013). Stochastic Programming. New York: Springer.
Ridder, A. (2005). Importance sampling simulations of Markovian reliability systems using cross-entropy. Annals of Operations Research, 134(1), 119–136.
Rockafellar, R. T., & Royset, J. O. (2010). On buffered failure probability in design and optimization of structures. Reliability Engineering & System Safety, 95(5), 499–510.
Rockafellar, R. T., & Uryasev, S. (2000). Optimization of conditional value-at-risk. Journal of Risk, 2, 21–42.
Sadowsky, J. S. (1991). Large deviations theory and efficient simulation of excessive backlogs in a GI/GI/m queue. IEEE Transactions on Automatic Control, 36(12), 1383–1394.
Sadowsky, J. S. (1996). On Monte Carlo estimation of large deviations probabilities. The Annals of Applied Probability, 6(2), 399–422.
Sadowsky, J. S., & Bucklew, J. A. (1990). On large deviations theory and asymptotically efficient Monte Carlo estimation. IEEE Transactions on Information Theory, 36(3), 579–588.
Shapiro, A., Dentcheva, D., & Ruszczyński, A. (2009). Lectures on Stochastic Programming: Modeling and Theory. New Delhi: SIAM.
Siegmund, D. (1976). Importance sampling in the Monte Carlo study of sequential tests. The Annals of Statistics, 4(4), 673–684.
Van Ackooij, W., & Henrion, R. (2014). Gradient formulae for nonlinear probabilistic constraints with Gaussian and Gaussian-like distributions. SIAM Journal on Optimization, 24(4), 1864–1889.
Acknowledgements
This project was supported by the National Science Foundation (DMS-1814894, DMS-1853968 and DMS-1619884).
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Budhiraja, A., Lu, S., Yu, Y. et al. Minimization of a class of rare event probabilities and buffered probabilities of exceedance. Ann Oper Res 302, 49–83 (2021). https://doi.org/10.1007/s10479-021-03991-8
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s10479-021-03991-8