Geodesic
Numerical study of discretizations of multistage stochastic programs
Kybernetika, Tome 44 (2008) no. 2, pp. 185-204 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
Classification : 49M25, 90C15, 90C25
Keywords: stochastic programming; discretization; integration quadratures; simulation 
@article{KYB_2008_44_2_a4,
     author = {Hilli, Petri and Pennanen, Teemu},
     title = {Numerical study of discretizations of multistage stochastic programs},
     journal = {Kybernetika},
     pages = {185--204},
     year = {2008},
     volume = {44},
     number = {2},
     mrnumber = {2428219},
     zbl = {1154.90556},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/KYB_2008_44_2_a4/}
}
TY  - JOUR
AU  - Hilli, Petri
AU  - Pennanen, Teemu
TI  - Numerical study of discretizations of multistage stochastic programs
JO  - Kybernetika
PY  - 2008
SP  - 185
EP  - 204
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/KYB_2008_44_2_a4/
LA  - en
ID  - KYB_2008_44_2_a4
ER  - 
%0 Journal Article
%A Hilli, Petri
%A Pennanen, Teemu
%T Numerical study of discretizations of multistage stochastic programs
%J Kybernetika
%D 2008
%P 185-204
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/KYB_2008_44_2_a4/
%G en
%F KYB_2008_44_2_a4
Hilli, Petri; Pennanen, Teemu. Numerical study of discretizations of multistage stochastic programs. Kybernetika, Tome 44 (2008) no. 2, pp. 185-204. http://geodesic.mathdoc.fr/item/KYB_2008_44_2_a4/

[1] Blomvall J., Shapiro A.: Solving multistage asset investment problems by the sample average approximation method. Math. Program. 108 (2006), 571–595 | MR | Zbl

[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 | MR | Zbl

[6] Glasserman P.: Monte Carlo Methods in Financial Engineering. Springer-Verlag, New York 2004 | MR | Zbl

[7] Heitsch H., Römisch W.: Scenario tree modelling for multistage stochastic programs. Math. Programming. To appear | MR

[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 | MR | Zbl

[9] Kall P., Mayer J.: Stochastic Linear Programming. Springer-Verlag, New York 2005 | MR | Zbl

[10] Kuhn D.: Generalized Bounds for Convex Multistage Stochastic Programs. Springer-Verlag, Berlin 2005 | MR | Zbl

[11] Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia 1992 | MR | Zbl

[12] Niederreiter H., Talay D.: Monte Carlo and Quasi-Monte Carlo Methods 2004. Springer-Verlag, Berlin 2006 | MR | Zbl

[13] Olsen P.: Discretizations of multistage stochastic programming problems. Math. Programming Stud. 6 (1976), 111–124 | MR | Zbl

[14] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs. Math. Oper. Res. 30 (2005), 245–256 | MR | Zbl

[15] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math. Programming, Series B. To appear | MR | Zbl

[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 | MR

[18] Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P.: Numerical Recipes in C. Cambridge University Press, Cambridge 1992 | MR | Zbl

[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 | MR | Zbl

[20] Rockafellar R. T., Wets R. J.-B.: Nonanticipativity and $L^1$-martingales in stochastic optimization problems. Math. Programming Stud. (1976), 170–187 | MR

[21] Shapiro A.: Inference of statistical bounds for multistage stochastic programming problems. Math. Methods Oper. Res. 58 (2003), 57–68 | MR | Zbl

[22] Shapiro A.: On complexity of multistage stochastic programs. Oper. Res. Lett. 34 (2006), 1–8 | MR | Zbl

[23] Sloan I. H., Joe S.: Lattice Methods for Multiple Integration. The Clarendon Press Oxford University Press, New York 1994 | MR | Zbl

[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 | MR | Zbl