Kybernetika 48 no. 1, 105-122, 2012

Chance constrained problems: penalty reformulation and performance of sample approximation technique

Martin Branda

Abstract:

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.

Keywords:

chance constrained problems, penalty functions, asymptotic equivalence, sample approximation technique, investment problem

Classification:

93E12, 62A10

paper.pdf

References:

  1. S. Ahmed and 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.   CrossRef
  2. E. Angelelli, R. Mansini and M. G. Speranza: A comparison of MAD and CVaR models with real features. J. Banking Finance 32 (2008), 1188-1197.   CrossRef
  3. M. S. Bazara, H. D. Sherali and C. M. Shetty: Nonlinear Programming: Theory and Algorithms. Wiley, Singapore 1993.   CrossRef
  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.   CrossRef
  5. M. Branda: Stochastic programming problems with generalized integrated chance constraints. Accepted to Optimization 2011.   CrossRef
  6. M. Branda and J. Dupačová: Approximations and contamination bounds for probabilistic programs. Accepted to Ann. Oper. Res. 2011 (Online first). See also SPEPS 13, 2008.   CrossRef
  7. G. Calafiore and M. C. Campi: Uncertain convex programs: randomized solutions and confidence levels. Math. Programming, Ser. A 102 (2008), 25-46.   CrossRef
  8. A. DasGupta: Asymptotic Theory of Statistics and Probability. Springer, New York 1993.   CrossRef
  9. J. Dupačová and M. Kopa: Robustness in stochastic programs with risk constraints. Accepted to Ann. Oper. Res. 2011 (Online first).   CrossRef
  10. J. Dupačová, A. Gaivoronski, Z. Kos and T. Szantai: Stochastic programming in water management: A case study and a comparison of solution techniques. Europ. J. Oper. Res. 52 (1991), 28-44.   CrossRef
  11. Y. M. Ermoliev, T. Y. Ermolieva, G. J. Macdonald and V. I. Norkin: Stochastic optimization of insurance portfolios for managing exposure to catastrophic risks. Ann. Oper. Res. 99 (2000), 207-225.   CrossRef
  12. P. Lachout: Approximative solutions of stochastic optimization problems. Kybernetika 46 (2010), 3, 513-523.   CrossRef
  13. J. Luedtke and S. Ahmed: A sample approximation approach for optimization with probabilistic constraints. SIAM J. Optim. 19 (2008), 674-699.   CrossRef
  14. J. Nocedal and S. J. Wright: Numerical Optimization. Springer, New York 2000.   CrossRef
  15. B. Pagnoncelli, S. Ahmed and A. Shapiro: Computational study of a chance constrained portfolio selection problem. Optimization Online 2008.   CrossRef
  16. B. Pagnoncelli, S. Ahmed and A. Shapiro: Sample average approximation method for chance constrained programming: Theory and applications. J. Optim. Theory Appl. {\mi 142} (2009), 399-416.   CrossRef
  17. A. Prékopa: Contributions to the theory of stochastic programming. Math. Programming 4 (1973), 202-221.   CrossRef
  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.   CrossRef
  19. A. Prékopa: Stochastic Programming. Kluwer, Dordrecht and Académiai Kiadó, Budapest 1995.   CrossRef
  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.   CrossRef
  21. R. T. Rockafellar and S. Uryasev: Conditional value-at-risk for general loss distributions. J. Banking Finance 26 (2002), 1443-1471.   CrossRef
  22. R. T. Rockafellar and R. Wets: Variational Analysis. Springer-Verlag, Berlin 2004.   CrossRef
  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.   CrossRef
  24. S. W. Wallace and W. T. Ziemba: Applications of stochastic programming. MPS-SIAM Book Series on Optimization 5 (2005), Society for Industrial and Applied Mathematics.   CrossRef
  25. E. Žampachová and 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.   CrossRef
  26. E. Žampachová, P. Popela and M. Mrázek: Optimum beam design via stochastic programming. Kybernetika 46 (2010), 3, 571-582.   CrossRef