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

Martin Branda

Kybernetika (2012)

  • Volume: 48, Issue: 1, page 105-122
  • ISSN: 0023-5954

Abstract

top
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.

How to cite

top

Branda, Martin. "Chance constrained problems: penalty reformulation and performance of sample approximation technique." Kybernetika 48.1 (2012): 105-122. <http://eudml.org/doc/246573>.

@article{Branda2012,
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.},
author = {Branda, Martin},
journal = {Kybernetika},
keywords = {chance constrained problems; penalty functions; asymptotic equivalence; sample approximation technique; investment problem; chance constrained problems; penalty functions; asymptotic equivalence; sample approximation technique; investment problem},
language = {eng},
number = {1},
pages = {105-122},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Chance constrained problems: penalty reformulation and performance of sample approximation technique},
url = {http://eudml.org/doc/246573},
volume = {48},
year = {2012},
}

TY - JOUR
AU - Branda, Martin
TI - Chance constrained problems: penalty reformulation and performance of sample approximation technique
JO - Kybernetika
PY - 2012
PB - Institute of Information Theory and Automation AS CR
VL - 48
IS - 1
SP - 105
EP - 122
AB - 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.
LA - eng
KW - chance constrained problems; penalty functions; asymptotic equivalence; sample approximation technique; investment problem; chance constrained problems; penalty functions; asymptotic equivalence; sample approximation technique; investment problem
UR - http://eudml.org/doc/246573
ER -

References

top
  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. (2008) 
  2. E. Angelelli, R. Mansini, M. G. Speranza, 10.1016/j.jbankfin.2006.07.015, J. Banking Finance 32 (2008), 1188-1197. (2008) DOI10.1016/j.jbankfin.2006.07.015
  3. M. S. Bazara, H. D. Sherali, C. M. Shetty, Nonlinear Programming: Theory and Algorithms., Wiley, Singapore 1993. (1993) MR2218478
  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. (2010) 
  5. M. Branda, Stochastic programming problems with generalized integrated chance constraints., Accepted to Optimization 2011. (2011) MR2955282
  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. (2011) MR2874754
  7. G. Calafiore, M. C. Campi, 10.1007/s10107-003-0499-y, Math. Programming, Ser. A 102 (2008), 25-46. (2008) MR2115479DOI10.1007/s10107-003-0499-y
  8. A. DasGupta, Asymptotic Theory of Statistics and Probability., Springer, New York 1993. (1993) MR2664452
  9. J. Dupačová, M. Kopa, Robustness in stochastic programs with risk constraints., Accepted to Ann. Oper. Res. 2011 (Online first). (2011) MR2989600
  10. J. Dupačová, A. Gaivoronski, Z. Kos, T. Szantai, 10.1016/0377-2217(91)90333-Q, Europ. J. Oper. Res. 52 (1991), 28-44. (1991) Zbl0726.90048DOI10.1016/0377-2217(91)90333-Q
  11. Y. M. Ermoliev, T. Y. Ermolieva, G. J. Macdonald, V. I. Norkin, 10.1023/A:1019244405392, Ann. Oper. Res. 99 (2000), 207-225. (2000) Zbl0990.90084MR1837739DOI10.1023/A:1019244405392
  12. P. Lachout, Approximative solutions of stochastic optimization problems., Kybernetika 46 (2010), 3, 513-523. (2010) Zbl1229.90110MR2676087
  13. J. Luedtke, S. Ahmed, 10.1137/070702928, SIAM J. Optim. 19 (2008), 674-699. (2008) Zbl1177.90301MR2425035DOI10.1137/070702928
  14. J. Nocedal, S. J. Wright, Numerical Optimization., Springer, New York 2000. (2000) MR2244940
  15. B. Pagnoncelli, S. Ahmed, A. Shapiro, Computational study of a chance constrained portfolio selection problem., Optimization Online 2008. (2008) 
  16. B. Pagnoncelli, S. Ahmed, A. Shapiro, 10.1007/s10957-009-9523-6, J. Optim. Theory Appl. 142 (2009), 399-416. (2009) Zbl1175.90306MR2525799DOI10.1007/s10957-009-9523-6
  17. A. Prékopa, 10.1007/BF01584661, Math. Programming 4 (1973), 202-221. (1973) Zbl0273.90045MR0376145DOI10.1007/BF01584661
  18. A. Prékopa, 10.1007/BF01421551, Math. Methods Oper. Res. 34 (1990), 441-461. (1990) Zbl0724.90048MR1087554DOI10.1007/BF01421551
  19. A. Prékopa, Stochastic Programming., Kluwer, Dordrecht and Académiai Kiadó, Budapest 1995. (1995) Zbl0863.90116MR1375234
  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. (2003) MR2052757
  21. R. T. Rockafellar, S. Uryasev, 10.1016/S0378-4266(02)00271-6, J. Banking Finance 26 (2002), 1443-1471. (2002) DOI10.1016/S0378-4266(02)00271-6
  22. R. T. Rockafellar, R. Wets, Variational Analysis., Springer-Verlag, Berlin 2004. (2004) MR1491362
  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. (2003) MR2052758
  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. (2005) Zbl1068.90002MR2162941
  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. (2010) 
  26. E. Žampachová, P. Popela, M. Mrázek, Optimum beam design via stochastic programming., Kybernetika 46 (2010), 3, 571-582. (2010) Zbl1201.90145MR2676092

NotesEmbed ?

top

You must be logged in to post comments.

To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.