Numerical study of discretizations of multistage stochastic programs

Petri Hilli; Teemu Pennanen

Kybernetika (2008)

  • Volume: 44, Issue: 2, page 185-204
  • ISSN: 0023-5954

Abstract

top
This paper presents a numerical study of a deterministic discretization procedure for multistage stochastic programs where the underlying stochastic process has a continuous probability distribution. The discretization procedure is based on quasi-Monte Carlo techniques originally developed for numerical multivariate integration. The solutions of the discretized problems are evaluated by statistical bounds obtained from random sample average approximations and out-of-sample simulations. In the numerical tests, the optimal values of the discretizations as well as their first-stage solutions approach those of the original infinite-dimensional problem as the discretizations are made finer.

How to cite

top

Hilli, Petri, and Pennanen, Teemu. "Numerical study of discretizations of multistage stochastic programs." Kybernetika 44.2 (2008): 185-204. <http://eudml.org/doc/33921>.

@article{Hilli2008,
abstract = {This paper presents a numerical study of a deterministic discretization procedure for multistage stochastic programs where the underlying stochastic process has a continuous probability distribution. The discretization procedure is based on quasi-Monte Carlo techniques originally developed for numerical multivariate integration. The solutions of the discretized problems are evaluated by statistical bounds obtained from random sample average approximations and out-of-sample simulations. In the numerical tests, the optimal values of the discretizations as well as their first-stage solutions approach those of the original infinite-dimensional problem as the discretizations are made finer.},
author = {Hilli, Petri, Pennanen, Teemu},
journal = {Kybernetika},
keywords = {stochastic programming; discretization; integration quadratures; simulation; stochastic programming; discretization; integration quadratures; simulation},
language = {eng},
number = {2},
pages = {185-204},
publisher = {Institute of Information Theory and Automation AS CR},
title = {Numerical study of discretizations of multistage stochastic programs},
url = {http://eudml.org/doc/33921},
volume = {44},
year = {2008},
}

TY - JOUR
AU - Hilli, Petri
AU - Pennanen, Teemu
TI - Numerical study of discretizations of multistage stochastic programs
JO - Kybernetika
PY - 2008
PB - Institute of Information Theory and Automation AS CR
VL - 44
IS - 2
SP - 185
EP - 204
AB - This paper presents a numerical study of a deterministic discretization procedure for multistage stochastic programs where the underlying stochastic process has a continuous probability distribution. The discretization procedure is based on quasi-Monte Carlo techniques originally developed for numerical multivariate integration. The solutions of the discretized problems are evaluated by statistical bounds obtained from random sample average approximations and out-of-sample simulations. In the numerical tests, the optimal values of the discretizations as well as their first-stage solutions approach those of the original infinite-dimensional problem as the discretizations are made finer.
LA - eng
KW - stochastic programming; discretization; integration quadratures; simulation; stochastic programming; discretization; integration quadratures; simulation
UR - http://eudml.org/doc/33921
ER -

References

top
  1. Blomvall J., Shapiro A., Solving multistage asset investment problems by the sample average approximation method, Math. Program. 108 (2006), 571–595 Zbl1130.90373MR2238715
  2. Chiralaksanakul A., Monte Carlo Methods for Multi-stage Stochastic Programs, PhD. Thesis, University of Texas at Austin, 2003 
  3. Chiralaksanakul A., Morton D., Assessing policy quality in multi-stage stochastic programming, Stochastic Programming E-Print Series, 2004 
  4. Fourer R., Gay D. M., Kernighan B.W., AMPL: A Modeling Language for Mathematical Programming, Second edition. Thomson, Canada 2002 
  5. Frauendorfer K., Barycentric scenario trees in convex multistage stochastic programming, Math. Programming 75 (1996), 277–293 (1996) Zbl0874.90144MR1426642
  6. Glasserman P., Monte Carlo Methods in Financial Engineering, Springer-Verlag, New York 2004 Zbl1038.91045MR1999614
  7. Heitsch H., Römisch W., Scenario tree modelling for multistage stochastic programs, Math. Programming. To appear MR2470797
  8. Hilli P., Koivu M., Pennanen, T., Ranne A., A stochastic programming model for asset liability management of a Finnish pension company, Ann. Oper. Res. 152 (2007), 115–139 Zbl1132.91493MR2303128
  9. Kall P., Mayer J., Stochastic Linear Programming, Springer-Verlag, New York 2005 Zbl1211.90003MR2118904
  10. Kuhn D., Generalized Bounds for Convex Multistage Stochastic Programs, Springer-Verlag, Berlin 2005 Zbl1103.90069MR2103400
  11. Niederreiter H., Random Number Generation and Quasi-Monte Carlo Methods, SIAM, Philadelphia 1992 Zbl0761.65002MR1172997
  12. Niederreiter H., Talay D., Monte Carlo and Quasi-Monte Carlo Methods 2004, Springer-Verlag, Berlin 2006 Zbl1084.65005MR2208697
  13. Olsen P., Discretizations of multistage stochastic programming problems, Math. Programming Stud. 6 (1976), 111–124 (1976) Zbl0374.90053MR0462589
  14. Pennanen T., Epi-convergent discretizations of multistage stochastic programs, Math. Oper. Res. 30 (2005), 245–256 Zbl1165.90014MR2125146
  15. Pennanen T., Epi-convergent discretizations of multistage stochastic programs via integration quadratures, Math. Programming, Series B. To appear Zbl1165.90014MR2421289
  16. Pennanen T., Koivu M., Integration quadratures in discretization of stochastic programs, SPEPS E-Print Series, 2002 
  17. Pflug G., Scenario tree generation for multiperiod financial optimization by optimal discretization, Math. Programming 89 (2001), 251–271 MR1816503
  18. Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P., Numerical Recipes in C, Cambridge University Press, Cambridge 1992 Zbl1078.65500MR1201159
  19. Rockafellar R. T., Wets R. J.-B., Continuous versus measurable recourse in N -stage stochastic programming, J. Math. Anal. Appl. 48 (1974), 836–859 (1974) Zbl0309.90039MR0406509
  20. Rockafellar R. T., Wets R. J.-B., Nonanticipativity and L 1 -martingales in stochastic optimization problems, Math. Programming Stud. (1976), 170–187 (1976) MR0462590
  21. Shapiro A., Inference of statistical bounds for multistage stochastic programming problems, Math. Methods Oper. Res. 58 (2003), 57–68 Zbl1116.90384MR2002322
  22. Shapiro A., On complexity of multistage stochastic programs, Oper. Res. Lett. 34 (2006), 1–8 Zbl1080.90056MR2186066
  23. Sloan I. H., Joe S., Lattice Methods for Multiple Integration, The Clarendon Press Oxford University Press, New York 1994 Zbl0855.65013MR1442955
  24. Sobol’ I. M., The distribution of points in a cube and the approximate evaluation of integrals, U.S.S.R. Computational Math. And Math. Phys. (1967), 86–112 (1967) Zbl0185.41103MR0219238

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.