| Title:
|
Numerical study of discretizations of multistage stochastic programs (English) |
| Author:
|
Hilli, Petri |
| Author:
|
Pennanen, Teemu |
| Language:
|
English |
| Journal:
|
Kybernetika |
| ISSN:
|
0023-5954 |
| Volume:
|
44 |
| Issue:
|
2 |
| Year:
|
2008 |
| Pages:
|
185-204 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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. (English) |
| Keyword:
|
stochastic programming |
| Keyword:
|
discretization |
| Keyword:
|
integration quadratures |
| Keyword:
|
simulation |
| MSC:
|
49M25 |
| MSC:
|
90C15 |
| MSC:
|
90C25 |
| idZBL:
|
Zbl 1154.90556 |
| idMR:
|
MR2428219 |
| . |
| Date available:
|
2009-09-24T20:33:24Z |
| Last updated:
|
2012-06-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/135843 |
| . |
| Reference:
|
[1] Blomvall J., Shapiro A.: Solving multistage asset investment problems by the sample average approximation method.Math. Program. 108 (2006), 571–595 Zbl 1130.90373, MR 2238715 |
| Reference:
|
[2] Chiralaksanakul A.: Monte Carlo Methods for Multi-stage Stochastic Programs.PhD. Thesis, University of Texas at Austin, 2003 |
| Reference:
|
[3] Chiralaksanakul A., Morton D.: Assessing policy quality in multi-stage stochastic programming.Stochastic Programming E-Print Series, 2004 |
| Reference:
|
[4] Fourer R., Gay D. M., Kernighan B.W.: AMPL: A Modeling Language for Mathematical Programming.Second edition. Thomson, Canada 2002 |
| Reference:
|
[5] Frauendorfer K.: Barycentric scenario trees in convex multistage stochastic programming.Math. Programming 75 (1996), 277–293 Zbl 0874.90144, MR 1426642 |
| Reference:
|
[6] Glasserman P.: Monte Carlo Methods in Financial Engineering.Springer-Verlag, New York 2004 Zbl 1038.91045, MR 1999614 |
| Reference:
|
[7] Heitsch H., Römisch W.: Scenario tree modelling for multistage stochastic programs.Math. Programming. To appear MR 2470797 |
| Reference:
|
[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 Zbl 1132.91493, MR 2303128 |
| Reference:
|
[9] Kall P., Mayer J.: Stochastic Linear Programming.Springer-Verlag, New York 2005 Zbl 1211.90003, MR 2118904 |
| Reference:
|
[10] Kuhn D.: Generalized Bounds for Convex Multistage Stochastic Programs.Springer-Verlag, Berlin 2005 Zbl 1103.90069, MR 2103400 |
| Reference:
|
[11] Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods.SIAM, Philadelphia 1992 Zbl 0761.65002, MR 1172997 |
| Reference:
|
[12] Niederreiter H., Talay D.: Monte Carlo and Quasi-Monte Carlo Methods 2004.Springer-Verlag, Berlin 2006 Zbl 1084.65005, MR 2208697 |
| Reference:
|
[13] Olsen P.: Discretizations of multistage stochastic programming problems.Math. Programming Stud. 6 (1976), 111–124 Zbl 0374.90053, MR 0462589 |
| Reference:
|
[14] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs.Math. Oper. Res. 30 (2005), 245–256 Zbl 1165.90014, MR 2125146 |
| Reference:
|
[15] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures.Math. Programming, Series B. To appear Zbl 1165.90014, MR 2421289 |
| Reference:
|
[16] Pennanen T., Koivu M.: Integration quadratures in discretization of stochastic programs.SPEPS E-Print Series, 2002 |
| Reference:
|
[17] Pflug G.: Scenario tree generation for multiperiod financial optimization by optimal discretization.Math. Programming 89 (2001), 251–271 MR 1816503 |
| Reference:
|
[18] Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P.: Numerical Recipes in C.Cambridge University Press, Cambridge 1992 Zbl 1078.65500, MR 1201159 |
| Reference:
|
[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 Zbl 0309.90039, MR 0406509 |
| Reference:
|
[20] Rockafellar R. T., Wets R. J.-B.: Nonanticipativity and $L^1$-martingales in stochastic optimization problems.Math. Programming Stud. (1976), 170–187 MR 0462590 |
| Reference:
|
[21] Shapiro A.: Inference of statistical bounds for multistage stochastic programming problems.Math. Methods Oper. Res. 58 (2003), 57–68 Zbl 1116.90384, MR 2002322 |
| Reference:
|
[22] Shapiro A.: On complexity of multistage stochastic programs.Oper. Res. Lett. 34 (2006), 1–8 Zbl 1080.90056, MR 2186066 |
| Reference:
|
[23] Sloan I. H., Joe S.: Lattice Methods for Multiple Integration.The Clarendon Press Oxford University Press, New York 1994 Zbl 0855.65013, MR 1442955 |
| Reference:
|
[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 Zbl 0185.41103, MR 0219238 |
| . |
