Approximation and contamination bounds for probabilistic programs. (English) Zbl 1254.90133

Summary: Development of applicable robustness results for stochastic programs with probabilistic constraints is a demanding task. In this paper we follow the relatively simple ideas of output analysis based on the contamination technique and focus on construction of computable global bounds for the optimal value function. Dependence of the set of feasible solutions on the probability distribution rules out the straightforward construction of these concavity-based global bounds for the perturbed optimal value function whereas local results can still be obtained. Therefore we explore approximations and reformulations of stochastic programs with probabilistic constraints by stochastic programs with suitably chosen recourse or penalty-type objectives and fixed constraints. Contamination bounds constructed for these substitute problems may be then implemented within the output analysis for the original probabilistic program.


90C15 Stochastic programming
Full Text: DOI


[1] Birge, J. R., & Louveaux, F. (1997). Springer series on operations research. Introduction to stochastic programming. New York: Springer. · Zbl 0892.90142
[2] Bonnans, J. S., & Shapiro, A. (2000). Springer series on operations research. Perturbation analysis of optimization problems. New York: Springer. · Zbl 0966.49001
[3] Bosch, P., Jofré, A., & Schultz, R. (2007). Two-stage stochastic programs with mixed probabilities. SIAM Journal on Optimization, 18, 778–788. · Zbl 1211.90145
[4] Branda, M. (2010). Reformulation of general chance constrained problems using the penalty functions. In SPEPS 2010-2. · Zbl 1202.90203
[5] Branda, M., & Dupačová, J. (2008). Approximation and contamination bounds for probabilistic programs. In SPEPS 2008-13 (available at www.stoprog.org ). · Zbl 1254.90133
[6] Danskin, J. M. (1967). Econometrics and operations research: Vol. 5. Theory of Max-Min. Berlin: Springer. · Zbl 0154.20009
[7] Dobiáš, P. (2003). Contamination for stochastic integer programs. Bulletin of the Czech Econometric Society, 18, 65–80.
[8] Dupačová, J. (1986). Stability in stochastic programming with recourse–contaminated distributions. Mathematical Programming Studies, 27, 133–144. · Zbl 0594.90068
[9] Dupačová, J. (1987). Stochastic programming with incomplete information: a survey of results on postoptimization and sensitivity analysis. Optimization, 18, 507–532. · Zbl 0637.90070
[10] Dupačová, J. (1990). Stability and sensitivity analysis in stochastic programming. Annals of Operation Research, 27, 115–142. · Zbl 0724.90049
[11] Dupačová, J. (1996). Scenario based stochastic programs: Resistance with respect to sample. Annals of Operation Research, 64, 21–38. · Zbl 0854.90107
[12] Dupačová, J. (2008). Risk objectives in two-stage stochastic programming problems. Kybernetika, 44, 227–242. · Zbl 1154.91500
[13] Dupačová, J., & Polívka, J. (2007). Stress testing for VaR and CVaR. Quantitative Finance, 7, 411–421. · Zbl 1190.91073
[14] Dupačová, J., Bertocchi, M., & Moriggia, V. (1998). Postoptimality for scenario based financial models with an application to bond portfolio management. In W. T. Ziemba & J. Mulvey (Eds.), World wide asset and liability modeling (pp. 263–285). Cambridge: Cambridge University Press. · Zbl 0939.91061
[15] Dupačová, J., Gaivoronski, A. A., Kos, Z., & Szántai, T. (1991). Stochastic programming in water management: a case study and a comparison of solution techniques. European Journal of Operational Research, 52, 28–44. · Zbl 0726.90048
[16] Ermoliev, T., Ermolieva, Y. M., MacDonald, G. J., & Norkin, V. I. (2000). Stochastic optimization of insurance portfolios for managing expose to catastrophic risks. Annals of Operation Research, 99, 207–225. · Zbl 0990.90084
[17] Gol’štejn, E. G. (1972). Translations of mathematical monographs: Vol. 36. Theory of convex programming. Providence: Am. Math. Soc.
[18] Guddat, J., Guerra Vasquez, F., Tammer, K., & Wendler, K. (1985). Multiobjective and stochastic optimization based on parametric optimization. Berlin: Akademie-Verlag. · Zbl 0583.90055
[19] Kall, P. (1987). On approximations and stability in stochastic programming. In J. Guddat et al. (Eds.), Parametric optimization and related topics (pp. 387–400). Berlin: Akademie-Verlag. · Zbl 0636.90066
[20] Kall, P., & Mayer, J. (2005a). Springer international series. Stochastic linear programming: models, theory and computation. New York: Springer. · Zbl 1104.90033
[21] Kall, P., & Mayer, J. (2005b). Building and solving stochastic linear programming models with SLP-IOR. In S. W. Wallace & W. T. Ziemba (Eds.), MPS-SIAM book series on optimization: Vol. 5. Applications of stochastic programming (pp. 79–93). · Zbl 1105.90342
[22] Kall, P., Ruszczyński, A., & Frauendorfer, K. (1988). Approximation techniques in stochastic programming. In Yu. Ermoliev & R. J.-B. Wets (Eds.), Numerical techniques for stochastic optimization (pp. 34–64). Berlin: Springer. · Zbl 0665.90067
[23] Kibzun, A. I., & Kan, Y. S. (1996). Stochastic programming problems with probability and quantile functions. New York: Wiley. · Zbl 0885.90088
[24] Klein Haneveld, W. K. (1986). LNEMS: Vol. 274. Duality in stochastic linear and dynamic programming. Berlin: Springer. · Zbl 0598.90062
[25] Luedtke, J., & Ahmed, S. (2008). A sample approximation approach for optimization with probabilistic constraints. SIAM Journal on Optimization, 19, 674–633. · Zbl 1177.90301
[26] Pagnoncelli, B. K., Ahmed, S., & Shapiro, A. (2009). Sample average approximation method for chance constrained programming: theory and applications. Journal of Optimization Theory and Applications, 142, 399–416. · Zbl 1175.90306
[27] Prékopa, A. (1971). Logarithmic concave measures with application to stochastic programming. Acta Sientiarum Mathematic (Szeged), 32, 301–316. · Zbl 0235.90044
[28] Prékopa, A. (1973). Contributions to the theory of stochastic programming. Mathematical Programming, 4, 202–221. · Zbl 0273.90045
[29] Prékopa, A. (2003). Probabilistic programming. In A. Ruszczynski & A. Shapiro (Eds.), Handbook on stochastic programming (pp. 267–351). Amsterdam: Elsevier. Chap. 5.
[30] Römisch, W. (2003). Stability of stochastic programming problems. In A. Ruszczynski & A. Shapiro (Eds.), Handbook on stochastic programming (pp. 483–554). Amsterdam: Elsevier. Chap. 8.
[31] Ruszczynski, A., & Shapiro, A. (Eds.) (2003). Handbook on stochastic programming. Amsterdam: Elsevier.
[32] Serfling, R. J. (1980). Approximation theorems of mathematical statistics. New York: Wiley. · Zbl 0538.62002
[33] Shapiro, A. (2003). Monte Carlo sampling methods. In A. Ruszczynski & A. Shapiro (Eds.), Handbook on stochastic programming (pp. 353–425). Amsterdam: Elsevier. Chap. 6.
[34] Žampachová, E. (2010). Approximations in stochastic optimization and their applications. Ph.D. Thesis, Brno University of Technology.
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.