Previous |  Up |  Next


chance constrained problems; penalty functions; asymptotic equivalence; sample approximation technique; investment problem
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 were studied in [6,11]. 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.
[1] S. Ahmed, A. Shapiro: Solving chance-constrained stochastic programs via sampling and integer programming. In: Tutorials in Operations Research, (Z.-L. Chen and S. Raghavan, eds.), 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. DOI 10.1016/j.jbankfin.2006.07.015
[3] M. S. Bazara, H. D. Sherali, C. M. Shetty: Nonlinear Programming: Theory and Algorithms. Wiley, Singapore 1993. MR 2218478
[4] M. Branda: Solving real-life portfolio problem using stochastic programming and Monte-Carlo techniques. In: Proc. Mathematical Methods in Economics 2010, (M. Houda, J. Friebelová, eds.), University of South Bohemia, České Budějovice 2010.
[5] M. Branda: Stochastic programming problems with generalized integrated chance constraints. Accepted to Optimization 2011. MR 2955282
[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. MR 2874754
[7] G. Calafiore, M. C. Campi: Uncertain convex programs: randomized solutions and confidence levels. Math. Programming, Ser. A 102 (2008), 25-46. DOI 10.1007/s10107-003-0499-y | MR 2115479
[8] A. DasGupta: Asymptotic Theory of Statistics and Probability. Springer, New York 1993. MR 2664452
[9] J. Dupačová, M. Kopa: Robustness in stochastic programs with risk constraints. Accepted to Ann. Oper. Res. 2011 (Online first). MR 2989600
[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. DOI 10.1016/0377-2217(91)90333-Q | 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. DOI 10.1023/A:1019244405392 | MR 1837739 | Zbl 0990.90084
[12] P. Lachout: Approximative solutions of stochastic optimization problems. Kybernetika 46 (2010), 3, 513-523. MR 2676087 | Zbl 1229.90110
[13] J. Luedtke, S. Ahmed: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19 (2008), 674-699. DOI 10.1137/070702928 | MR 2425035 | Zbl 1177.90301
[14] J. Nocedal, S. J. Wright: Numerical Optimization. Springer, New York 2000. MR 2244940
[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. DOI 10.1007/s10957-009-9523-6 | MR 2525799 | Zbl 1175.90306
[17] A. Prékopa: Contributions to the theory of stochastic programming. Math. Programming 4 (1973), 202-221. DOI 10.1007/BF01584661 | MR 0376145 | 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. DOI 10.1007/BF01421551 | MR 1087554 | Zbl 0724.90048
[19] A. Prékopa: Stochastic Programming. Kluwer, Dordrecht and Académiai Kiadó, Budapest 1995. MR 1375234 | Zbl 0863.90116
[20] A. Prékopa: Probabilistic programming. In: Stochastic Programming, (A. Ruszczynski and A. Shapiro,eds.), Handbook in Operations Research and Management Science, Vol. 10, Elsevier, Amsterdam 2003, pp. 267-352. MR 2052757
[21] R. T. Rockafellar, S. Uryasev: Conditional value-at-risk for general loss distributions. J. Banking Finance 26 (2002), 1443-1471. DOI 10.1016/S0378-4266(02)00271-6
[22] R. T. Rockafellar, R. Wets: Variational Analysis. Springer-Verlag, Berlin 2004. MR 1491362
[23] A. Shapiro: Monte Carlo sampling methods. In: Stochastic Programming, (A. Ruszczynski and A. Shapiro, eds.), Handbook in Operations Research and Management Science, Vol. 10, Elsevier, Amsterdam 2003, pp. 353-426. MR 2052758
[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. MR 2162941 | Zbl 1068.90002
[25] E. Žampachová, M. Mrázek: Stochastic optimization in beam design and its reliability check. In: MENDEL 2010 - 16th Internat. Conference on Soft Computing, (R. Matoušek), ed.), 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. MR 2676092 | Zbl 1201.90145
Partner of
EuDML logo