Epi-convergent discretizations of multistage stochastic programs via integration quadratures. (English) Zbl 1165.90014

Summary: This paper presents procedures for constructing numerically solvable discretizations of multistage stochastic programs that epi-converge to the original problem as the discretizations are made finer. Epi-convergence implies, in particular, that the cluster points of the first-stage solutions of the discretized problems are optimal first-stage solutions of the original problem. The discretization procedures apply to a general class of nonlinear stochastic programs where the uncertain factors are driven by time series models. Using existing routines for numerical integration allows for an easy and efficient implementation of the procedures.


90C15 Stochastic programming
49M25 Discrete approximations in optimal control
90C25 Convex programming


Full Text: DOI


[1] Attouch H. (1984). Variational Convergence for Functions and Operators. Pitman (Advanced Publishing Program), Boston · Zbl 0561.49012
[2] Back K., Pliska S.R. (1987). The shadow price of information in continuous time decision problems. Stochastics 22(2): 151–186 · Zbl 0628.93076
[3] Billingsley P. (1995). Probability and measure. 3rd edn. Wiley Series in Probability and Mathematical Statistics. Wiley, New York · Zbl 0822.60002
[4] Billingsley P. (1999). Convergence of probability measures, 2nd edn. Wiley, New York · Zbl 0944.60003
[5] Black F., Karasinski P. (1991). Bond and option pricing when short rates are lognormal. Finan. Anal. J. July–August: 52–59 · doi:10.2469/faj.v47.n4.52
[6] Boender, C.G.E., van Aalst, P., Heemskerk, F.: Modelling and management of assets and liabilities of pension plans in The Netherlands. In: Ziemba W.T., Mulvey J.M. (eds.) Worldwide asset and liability modeling, pp. Cambridge University Press 561–580 (1998) · Zbl 0939.91059
[7] Braides, A.: {\(\Gamma\)} for beginners. Oxford Lecture Series in Mathematics and its Applications, vol. 22. Oxford University Press, Oxford · Zbl 1198.49001
[8] Casey M., Sen S. (2005). The scenario generation algorithm for multistage stochastic linear programs. Math. Oper. Res. 30(3): 615–631 · Zbl 1082.90076 · doi:10.1287/moor.1050.0146
[9] Chen X., Womersley R.S. (1996). A parallel inexact Newton method for stochastic programs with recourse. Ann. Oper. Res. 64: 113–141 · Zbl 0854.90106 · doi:10.1007/BF02187643
[10] Chiralaksanakul, A.: Monte carlo methods for multi-stage stochastic programs. PhD thesis, University of Texas at Austin, Texas (2003)
[11] Clements M.P., Hendry D.F. (1999). Forecasting Non-Stationary Economic Time Series. MIT Press, Cambridge · Zbl 0984.62069
[12] Dal Maso, G.: An introduction to {\(\Gamma\)}-convergence, Progress in Nonlinear Differential Equations and their Applications, vol. 8. Birkhäuser Boston Inc., Boston (1993) · Zbl 0816.49001
[13] Dempster M.A.H., Germano M., Medova E., Villaverde M. (2003). Global asset liability management. Br. Actuar. J. 9(1): 137–195
[14] Dupačová J., Consigli G., Wallace S.W. (2001). Scenarios for multistage stochastic programs. Ann. Oper. Res. 100: 25–53 · Zbl 1017.90068
[15] Dupačová J., Gröwe-Kuska N., Römisch W. (2003). Scenario reduction in stochastic programming. An approach using probability metrics. Math. Program. 95(3, Ser. A): 493–511 · Zbl 1023.90043 · doi:10.1007/s10107-002-0331-0
[16] Engle R.F., Granger C.W.J. (1987). Co-integration and error correction: representation, estimation and testing. Econometrica 55(2): 251–276 · Zbl 0613.62140 · doi:10.2307/1913236
[17] Folland G.B. (1999). Real analysis, 2nd edn Pure and Applied Mathematics. Wiley, New York · Zbl 0924.28001
[18] Frauendorfer K. (1996). Barycentric scenario trees in convex multistage stochastic programming. Math. Programm. Approximation comput. stoc. Programm. 75(2, Ser. B): 277–293 · Zbl 0874.90144
[19] Gondzio J., Kouwenberg R., Vorst T. (2003). Hedging options under transaction costs and stochastic volatility. J. Econ. Dyn. Control 27(6): 1045–1068 · Zbl 1178.91196 · doi:10.1016/S0165-1889(02)00054-4
[20] Heitsch H., Römisch W. (2003). Scenario reduction algorithms in stochastic programming. Comput. Optim. Appl. Stochastic programming 24(2–3): 187–206 · Zbl 1094.90024
[21] Heitsch, H., Römisch, W., Strugarek, C.: Stability of multistage stochastic programs. Preprint 255, DFG Research Center Matheon Mathematics for key technologies (2005) · Zbl 1165.90582
[22] Hilli, P., Koivu, M., Pennanen, T., Ranne, A.: A stochastic programming model for asset liability management of a finnish pension company. Ann. Oper. Res. (in press) · Zbl 1132.91493
[23] Hlawka E., Mück R. (1972). Über eine Transformation von gleichverteilten Folgen. II. Computing (Arch. Elektron. Rechnen) 9: 127–138 · Zbl 0245.10039
[24] Ioffe A.D. (1977). On lower semicontinuity of integral functionals. I. SIAM J. Control Optimization 15(4): 521–538 · Zbl 0361.46037 · doi:10.1137/0315035
[25] Kouwenberg R. (2001). Scenario generation and stochastic programming models for asset liability management. Eur. J. Oper. Res. Financ. Model. 134(2): 279–292 · Zbl 1008.91050 · doi:10.1016/S0377-2217(00)00261-7
[26] L’Ecuyer P., Lemieux C. (2000). Variance reduction via lattice rules. Manage. Sci. 46(2): 1214–1235 · Zbl 1232.65008 · doi:10.1287/mnsc.46.9.1214.12231
[27] Lepp R. (1990). Approximations to stochastic programs with complete recourse. SIAM J. Control Optim. 28(2): 382–394 · Zbl 0692.49020 · doi:10.1137/0328020
[28] Lucchetti R., Salinetti G., Wets R.J.B. (1994). Uniform convergence of probability measures: topological criteria. J. Multivariate Anal. 51(2): 252–264 · Zbl 0817.60005 · doi:10.1006/jmva.1994.1061
[29] Marti, K., Ermoliev, Y., Pflug, G. (eds.): Dynamic stochastic optimization, Lecture Notes in Economics and Mathematical Systems. vol. 532. Papers from the IFIP/IIASA/GAMM Workshop held in Laxenburg, March 11–14, 2002. Springer, Berlin (2004) · Zbl 1024.00075
[30] Marti, K., Kall, P. (eds.): Stochastic programming. Lecture Notes in Economics and Mathematical Systems. vol. 423. Numerical techniques and engineering applications. Springer, Berlin (1995) · Zbl 0820.00015
[31] Marti, K., Kall, P. (eds.): Stochastic programming methods and technical applications. Lecture Notes in Economics and Mathematical Systems. vol. 458. Springer-Verlag, Berlin (1998) · Zbl 0889.00038
[32] Mordukhovich B. (1978). On difference approximations of optimal control systems. J. Appl. Math. Mech 42(3): 431–440 · Zbl 0407.49020 · doi:10.1016/0021-8928(78)90113-2
[33] Niederreiter, H.: Random number generation and quasi-Monte Carlo methods, CBMS-NSF Regional Conference Series in Applied Mathematics. vol. 63. Society for Industrial and Applied Mathematics (SIAM), Philadelphia (1992) · Zbl 0761.65002
[34] Niederreiter, H. (ed.): Monte Carlo and quasi-Monte Carlo methods 2002. In: Proceedings of a conference held at the National Univeristy of Singapore, Republic of Singapore, November 25–28, 2002. Springer-Verlag, Berlin (2004) · Zbl 0603.65043
[35] Olsen P. (1976). Discretizations of multistage stochastic programming problems. Math. Programm. Stud. 6: 111–124 · Zbl 0374.90053
[36] Pennanen T. (2005). Epi-convergent discretizations of multistage stochastic programs. Math. Oper. Res. 30(1): 245–256 · Zbl 1082.90078 · doi:10.1287/moor.1040.0114
[37] Pennanen, T., Koivu, M.: Integration quadratures in discretization of stochastic programs. Stochastic Programming E-Print Series (2002) · Zbl 1063.65047
[38] Pennanen T., Koivu M. (2005). Epi-convergent discretizations of stochastic programs via integration quadratures. Numer. Math. 100(1): 141–163 · Zbl 1063.65047 · doi:10.1007/s00211-004-0571-4
[39] Pflug G. (2001). Scenario tree generation for multiperiod financial optimization by optimal discretization. Math. Program. Math. Programm. Finance 89(2, Ser. B): 251–271 · Zbl 0987.91034
[40] Pflug, G., Hochreiter, R.: Scenario generation for stochastic multi-stage decision processes as facility location problems. Technical report, Department of Statistics and Decision Support Systems, University of Vienna (2003) · Zbl 1144.90442
[41] Polak, E.: Optimization. Applied Mathematical Sciences. vol. 124. Algorithms and consistent approximations. Springer, New York (1997) · Zbl 0899.90148
[42] Rockafellar R.T., Wets R.J.B. (1974). Continuous versus measurable recourse in N-stage stochastic programming. J. Math. Anal. Appl. 48: 836–859 · Zbl 0309.90039 · doi:10.1016/0022-247X(74)90157-7
[43] Rockafellar R.T., Wets R.J.B. (1976). Nonanticipativity and L 1-martingales in stochastic optimization problems. Math. Programm. Stud. 6: 170–187 · Zbl 0377.90073
[44] Rockafellar R.T., Wets R.J.B. (1977). Measures as Lagrange multipliers in multistage stochastic programming. J. Math. Anal. Appl. 60(2): 301–313 · Zbl 0369.90091 · doi:10.1016/0022-247X(77)90020-8
[45] Rockafellar, R.T., Wets, R.J.B.: Variational analysis. Grundlehren der Mathematischen Wissenschaften [Fundamental Principles of Mathematical Sciences] vol. 317. Springer, Berlin (1998)
[46] Römisch, W.: Stability of stochastic programming problems. In: Stochastic Programming, Handbooks in Operations Research and Management Science. vol. 10, pp. 483–554. Elsevier, Amsterdam (2003)
[47] Ruszczynski, A., Shapiro, A. (eds.): Stochastic Programming, Handbooks in Operations Research and Management Science. vol. 10. Elsevier, Amsterdam (2003)
[48] Shapiro A. (2003). Inference of statistical bounds for multistage stochastic programming problems. Math. Methods Oper. Res. 58(1): 57–68 · Zbl 1116.90384 · doi:10.1007/s001860300280
[49] Shapiro, A.: On complexity of multistage stochastic programs. Optimization Online (2005)
[50] Shiryaev, A.N.: Essentials of stochastic finance, Advanced Series on Statistical Science & Applied Probability. vol. 3. World Scientific Publishing Co. Inc., River Edge(1999) · Zbl 0926.62100
[51] Sloan I.H., Joe S. (1994). Lattice methods for multiple integration. The Clarendon Press/Oxford University Press, New York · Zbl 0855.65013
[52] Vainikko G.M. (1971). The convergence of the method of mechanical quadratures for integral equations with discontinuous kernels. Siberian Math. J. 12: 29–38 · Zbl 0229.45013 · doi:10.1007/BF00969138
[53] Ziemba, W.T., Mulvey, J.M. (eds.): Worldwide Asset and Liability Modeling, Publications of the Newton Institute, vol. 10. Cambridge University Press, Cambridge (1998) · Zbl 1067.91506
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.