Chance constrained problems: penalty reformulation and performance of sample approximation technique. (English) Zbl 1243.93117

Summary: We explore reformulation of nonlinear stochastic programs with several joint chance constraints by stochastic programs with suitably chosen penalty-type objectives. We show that the two problems are asymptotically equivalent. Simpler cases with one chance constraint and particular penalty functions are solved. The obtained problems with penalties and with a fixed set of feasible solutions are simpler to solve and analyze then the chance constrained programs. We discuss solving both problems using Monte-Carlo simulation techniques for the cases when the set of feasible solution is finite or infinite bounded. The approach is applied to a financial optimization problem with Value at Risk constraint, transaction costs and integer allocations. We compare the ability to generate a feasible solution of the original chance constrained problem using the sample approximations of the chance constraints directly or via sample approximation of the penalty function objective.


93E12 Identification in stochastic control theory
62D05 Sampling theory, sample surveys
91B30 Risk theory, insurance (MSC2010)
Full Text: EuDML Link


[1] S. Ahmed, A. Shapiro: Solving chance-constrained stochastic programs via sampling and integer programming. Tutorials in Operations Research, (Z.-L. Chen and S. Raghavan, INFORMS 2008.
[2] E. Angelelli, R. Mansini, M. G. Speranza: A comparison of MAD and CVaR models with real features. J. Banking Finance 32 (2008), 1188-1197.
[3] M. S. Bazara, H. D. Sherali, C. M. Shetty: Nonlinear Programming: Theory and Algorithms. Wiley, Singapore 1993.
[4] M. Branda: Solving real-life portfolio problem using stochastic programming and Monte-Carlo techniques. Proc. Mathematical Methods in Economics 2010, (M. Houda, J. Friebelová, University of South Bohemia, České Budějovice 2010.
[5] M. Branda: Stochastic programming problems with generalized integrated chance constraints. Accepted to Optimization 2011. · Zbl 1252.90056
[6] M. Branda, J. Dupačová: Approximations and contamination bounds for probabilistic programs. Accepted to Ann. Oper. Res. 2011 (Online first). See also SPEPS 13, 2008.
[7] G. Calafiore, M. C. Campi: Uncertain convex programs: randomized solutions and confidence levels. Math. Programming, Ser. A 102 (2008), 25-46. · Zbl 1177.90317
[8] A. DasGupta: Asymptotic Theory of Statistics and Probability. Springer, New York 1993.
[9] J. Dupačová, M. Kopa: Robustness in stochastic programs with risk constraints. Accepted to Ann. Oper. Res. 2011 · Zbl 1255.90088
[10] J. Dupačová, A. Gaivoronski, Z. Kos, T. Szantai: Stochastic programming in water management: A case study and a comparison of solution techniques. Europ. J. Oper. Res. 52 (1991), 28-44. · Zbl 0726.90048
[11] Y. M. Ermoliev, T. Y. Ermolieva, G. J. Macdonald, V. I. Norkin: Stochastic optimization of insurance portfolios for managing exposure to catastrophic risks. Ann. Oper. Res. 99 (2000), 207-225. · Zbl 0990.90084
[12] P. Lachout: Approximative solutions of stochastic optimization problems. Kybernetika 46 (2010), 3, 513-523. · Zbl 1229.90110
[13] J. Luedtke, S. Ahmed: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19 (2008), 674-699. · Zbl 1177.90301
[14] J. Nocedal, S. J. Wright: Numerical Optimization. Springer, New York 2000. · Zbl 0930.65067
[15] B. Pagnoncelli, S. Ahmed, A. Shapiro: Computational study of a chance constrained portfolio selection problem. Optimization Online 2008.
[16] B. Pagnoncelli, S. Ahmed, A. Shapiro: Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl. 142 (2009), 399-416. · Zbl 1175.90306
[17] A. Prékopa: Contributions to the theory of stochastic programming. Math. Programming 4 (1973), 202-221. · Zbl 0273.90045
[18] A. Prékopa: Dual method for the solution of a one-stage stochastic programming problem with random RHS obeying a discrete probability distribution. Math. Methods Oper. Res. 34 (1990), 441-461. · Zbl 0724.90048
[19] A. Prékopa: Stochastic Programming. Kluwer, Dordrecht and Académiai Kiadó, Budapest 1995. · Zbl 0863.90116
[20] A. Prékopa: Probabilistic programming. Stochastic Programming, (A. Ruszczynski and A. Shapiro,eds.), Handbook in Operations Research and Management Science, Vol. 10, Elsevier, Amsterdam 2003, pp. 267-352.
[21] R. T. Rockafellar, S. Uryasev: Conditional value-at-risk for general loss distributions. J. Banking Finance 26 (2002), 1443-1471.
[22] R. T. Rockafellar, R. Wets: Variational Analysis. Springer-Verlag, Berlin 2004.
[23] A. Shapiro: Monte Carlo sampling methods. Stochastic Programming, (A. Ruszczynski and A. Shapiro, Handbook in Operations Research and Management Science, Vol. 10, Elsevier, Amsterdam 2003, pp. 353-426.
[24] S. W. Wallace, W. T. Ziemba: Applications of stochastic programming. MPS-SIAM Book Series on Optimization 5 (2005), Society for Industrial and Applied Mathematics. · Zbl 1068.90002
[25] E. Žampachová, M. Mrázek: Stochastic optimization in beam design and its reliability check. MENDEL 2010 - 16th Internat. Conference on Soft Computing, (R. Matoušek), Mendel Journal series, FME BUT, Brno 2010, pp. 405-410.
[26] E. Žampachová, P. Popela, M. Mrázek: Optimum beam design via stochastic programming. Kybernetika 46 (2010), 3, 571-582. · Zbl 1201.90145
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.