Article
Full entry |
PDF
(0.9 MB)
Feedback
PDF
(0.9 MB)
Feedback
Keywords:
stochastic programming; discretization; integration quadratures; simulation
stochastic programming; discretization; integration quadratures; simulation
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.
References:
[1] Blomvall J., Shapiro A.: Solving multistage asset investment problems by the sample average approximation method. Math. Program. 108 (2006), 571–595 MR 2238715 | Zbl 1130.90373
[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 1426642 | Zbl 0874.90144
[6] Glasserman P.: Monte Carlo Methods in Financial Engineering. Springer-Verlag, New York 2004 MR 1999614 | Zbl 1038.91045
[7] Heitsch H., Römisch W.: Scenario tree modelling for multistage stochastic programs. Math. Programming. To appear MR 2470797
[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 2303128 | Zbl 1132.91493
[9] Kall P., Mayer J.: Stochastic Linear Programming. Springer-Verlag, New York 2005 MR 2118904 | Zbl 1211.90003
[10] Kuhn D.: Generalized Bounds for Convex Multistage Stochastic Programs. Springer-Verlag, Berlin 2005 MR 2103400 | Zbl 1103.90069
[11] Niederreiter H.: Random Number Generation and Quasi-Monte Carlo Methods. SIAM, Philadelphia 1992 MR 1172997 | Zbl 0761.65002
[12] Niederreiter H., Talay D.: Monte Carlo and Quasi-Monte Carlo Methods 2004. Springer-Verlag, Berlin 2006 MR 2208697 | Zbl 1084.65005
[13] Olsen P.: Discretizations of multistage stochastic programming problems. Math. Programming Stud. 6 (1976), 111–124 MR 0462589 | Zbl 0374.90053
[14] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs. Math. Oper. Res. 30 (2005), 245–256 MR 2125146 | Zbl 1165.90014
[15] Pennanen T.: Epi-convergent discretizations of multistage stochastic programs via integration quadratures. Math. Programming, Series B. To appear MR 2421289 | Zbl 1165.90014
[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 1816503
[18] Press W. H., Teukolsky S. A., Vetterling W. T., Flannery B. P.: Numerical Recipes in C. Cambridge University Press, Cambridge 1992 MR 1201159 | Zbl 1078.65500
[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 0406509 | Zbl 0309.90039
[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
[21] Shapiro A.: Inference of statistical bounds for multistage stochastic programming problems. Math. Methods Oper. Res. 58 (2003), 57–68 MR 2002322 | Zbl 1116.90384
[22] Shapiro A.: On complexity of multistage stochastic programs. Oper. Res. Lett. 34 (2006), 1–8 MR 2186066 | Zbl 1080.90056
[23] Sloan I. H., Joe S.: Lattice Methods for Multiple Integration. The Clarendon Press Oxford University Press, New York 1994 MR 1442955 | Zbl 0855.65013
[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 0219238 | Zbl 0185.41103
Search
Partner of
