×

Barycentric scenario trees in convex multistage stochastic programming. (English) Zbl 0874.90144

Summary: This work deals with the approximation of convex stochastic multistage programs allowing prices and demand to be stochastic with compact support. Based on earlier results, sequences of barycentric scenario trees with associated probability trees are derived for minorizing and majorizing the given problem. Error bounds for the optimal policies of the approximate problem and duality analysis with respect to the stochastic data determine the scenarios which improve the approximation. Convergence of the approximate solutions is proven under the stated assumptions. Preliminary computational results are outlined.

MSC:

90C15 Stochastic programming
90C40 Markov and semi-Markov decision processes
90C25 Convex programming

Software:

MSLiP
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] J. Birge, ”Decomposition and partitioning methods for multi-stage stochastic linear programs”,Operations Research 33 (1985) 989–1007. · Zbl 0581.90065 · doi:10.1287/opre.33.5.989
[2] J. birge, ”An L-shaped computer code for multi-stage stochastic linear programs,” in: Y. Ermoliev and R.J.-B. Wets, eds.,Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 255–266.
[3] J. Birge, ”The relationship between the L-shaped method and dual basis factorization for stochastic linear programming”, in: Y. Ermoliev and R.J.-B. Wets, eds.,Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 267–272. · Zbl 0667.90074
[4] J. Birge and R.J.-B. Wets, ”Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse”,Mathematical Programming Study 27 (1986) 54–102. · Zbl 0603.90104 · doi:10.1007/BFb0121114
[5] J. Birge and R.J.-B. Wets, ”Computing bounds for stochastic programming problems by means of a generalized moment problem”,Mathematics of Operations Research 12 (1987) 149–162. · Zbl 0619.90053 · doi:10.1287/moor.12.1.149
[6] J. Birge and R.J.-B. Wets, eds.,Stochastic Programming, Part I, II, Proceedings of the 5th International Conference on Stochastic Programming, Ann Arbor, MI, August 13–18 (1989);Annals of Operations Research 30, 31 (1991).
[7] G.B. Dantzig and P.W. Glynn ”Parallel processors for planning under uncertainty”,Annals of Operations Research 22 (1990) 1–21. · Zbl 0714.90074 · doi:10.1007/BF02023045
[8] G.B. Dantzig and G. Infanger, ”Multistage stochastic linear programs for portfolio optimization,” Technical Report SOL 91-11, Stanford University (1991). · Zbl 0785.90008
[9] M.A.H. Dempster, ed.,Stochastic Programming, Proceedings of the 1st International Conference on Stochastic Programming, Oxford (1974), (Academic Press, New York, 1980).
[10] M.A.H. Dempster, ”Introduction to stochastic programming,” in: M.A.H. Dempster, ed.,Stochastic Programming (Academic Press, New York, 1980) pp. 3–59. · Zbl 0484.90076
[11] M.A.H. Dempster, ”The expected value of perfect information in the optimal evolution of stochastic systems,” in: M. Arato, D. Vermes and A.V. Balakrishnan, eds.,Stochastic Differential Systems, Lecture Notes in Control and Information Sciences (1981) pp. 25–40. · Zbl 0483.60032
[12] M.A.H. Dempster, ”On stochastic programming II: Dynamic problems under risk”,Stochastics 25 (1988) 15–42. · Zbl 0653.90054 · doi:10.1080/17442508808833530
[13] N.C.P. Edirisinghe and W.T. Ziemba, ”Bounds for two-stage stochastic programs with fixed recourse,Mathematics of Operations Research 19 (2) (1994) 292–313. · Zbl 0824.90100 · doi:10.1287/moor.19.2.292
[14] N.C.P. Edirisinghe and W.T. Ziemba, ”Bounding the expectation of a saddle function with application to stochastic programming”,Mathematics of Operations Research 19 (2) (1994) 314–340. · Zbl 0824.90101 · doi:10.1287/moor.19.2.314
[15] Y. Ermoliev and R.J.-B. Wets,Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988). · Zbl 0658.00020
[16] K. Frauendorfer, ”Solving SLP recourse problems with arbitrary multivariate distributions–The dependent case,”Mathematics of Operations Research 13 (3) (1988) 377–394. · Zbl 0652.90080 · doi:10.1287/moor.13.3.377
[17] K. Frauendorfer,Stochastic Two-stage Programming, Lecture Notes in Economics and Mathematical Systems, Vol. 392 (Springer, Berlin, 1992). · Zbl 0794.90042
[18] K. Frauendorfer, ”Multistage stochastic programming: Error analysis for the convex case”,Mathematical Methods of Operations Research 39 (1) (1994) 93–122. · Zbl 0810.90098 · doi:10.1007/BF01440737
[19] K. Frauendorfer, ”Stochastic dynamic optimization: Modelling and methodological aspects,” Working Paper, University of St. Gallen (1994). · Zbl 0810.90132
[20] K. Frauendorfer and P. Kall, ”A solution method for SLP recourse problems with arbitrary distributions–The independent case”,Problems of Control and Information Theory 17 (1988) 177–205. · Zbl 0651.90054
[21] H.I. Gassmann, ”MSLiP: A computer code for the multistage stochastic linear programming problem,”Mathematical Programming 47 (1990) 407–423. · Zbl 0701.90070 · doi:10.1007/BF01580872
[22] O. Hemandez-Lerma and W.J. Runggaldier, ”Monotone approximations for convex stochastic control problems,Journal of Estimation, Control and Systems, to appear. · Zbl 0812.93078
[23] C. Huang, W.T. Ziemba and A. Ben-Tal, ”Bounds on the expectation of a convex function of a random variable: With application to stochastic programming”,Operations Research 25 (1977) 315–325. · Zbl 0362.62014 · doi:10.1287/opre.25.2.315
[24] G. Infanger,Planning under Uncertainty–Solving Large-scale Stochastic Linear Programs (Boyd & Fraser, New York, 1994). · Zbl 0867.90086
[25] P. Kall, ”Stochastic programming with recourse: Upper bound and moment problems–A review,” in: J. Guddat, B. Bank, H. Hollatz, P. Kall, D. Klatte, B. Kummer, K. Lommatsch, K. Tammer, M. Vlach and K. Zimmermann, eds.,Advances in Mathematical Optimization (Akademie Verlag, Berlin, 1988) pp. 86–103.
[26] P. Kall, A. Ruszczynski and K. Frauendorfer, ”Approximation techniques in stochastic programming”, in: Y. Ermoliev and R.J.-B. Wets, eds.,Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 33–64. · Zbl 0665.90067
[27] P. Kall and S.W. Wallace,Stochastic Programming (Wiley, Chichester, 1994).
[28] M. Loève,Probability Theory (1963).
[29] F.V. Louveaux, ”A solution method for multistage stochastic programs, with recourse with application to an energy investment problem”,Operations Research 28 (4) (1980) 889–902. · Zbl 0441.90076 · doi:10.1287/opre.28.4.889
[30] F.V. Louveaux, ”Multistage stochastic programs with block-separable recourse”,Mathematical Programming Study 28 (1986) 48–62. · Zbl 0593.90059 · doi:10.1007/BFb0121125
[31] J.M. Mulvey and H. Vladimirou, ”Solving multistage stochastic networks: An application of scenario aggregation”,Networks 21 (6) (1991) 619–643. · Zbl 0743.90053 · doi:10.1002/net.3230210603
[32] J.M. Mulvey and H. Vladimirou, ”Applying the progressive hedging algorithm to stochastic generalized networks”, in: J. Birge and R.J.-B. Wets, eds.,Stochastic Programming, Part II; Annals of Operations Research 31 (1991) 399–424. · Zbl 0734.90033
[33] J.M. Mulvey and H. Vladimirou, ”Stochastic network programming for financial planning problems,” Department of Civil Engineering and Operations Research, Princeton University (1992);Management Science 38 (1992) 1642–1664. · Zbl 0825.90062
[34] M.C. Noel and Y. Smeers, ”Nested Decomposition of multistage nonlinear programs with recourse”,Mathematical Programming 37 (1987) 131–152. · Zbl 0619.90054 · doi:10.1007/BF02591691
[35] P. Olsen, ”When is a multistage stochastic programming well-defined?”,SIAM Journal on Control and Optimization 14 (3) (1976) 518–527. · Zbl 0336.90040 · doi:10.1137/0314034
[36] S.M. Robinson, ”Extended scenario analysis”, in: J. Birge and R.J.-B. Wets, eds.,Stochastic Programming, Part II; Annals of Operations Research 31 (1991) 385–398. · Zbl 0739.90049
[37] R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, NJ, 1970). · Zbl 0193.18401
[38] R.T. Rockafellar, ”Integral functionals, normal integrand and measurable selections”, in:Nonlinear Operators and the Calculus of Variations, Lecture Notes in Mathematics, Vol. 543, (Springer, Berlin, 1976) pp. 157–207.
[39] R.T. Rockafellar and R.J.-B. Wets, ”Nonanticipativity andL 1-martingales in stochastic optimization problems”,Mathematical Programming Study 6 (1976) 170–187. · Zbl 0377.90073 · doi:10.1007/BFb0120750
[40] R.T. Rockafellar and R.J.-B. Wets, ”The optimal recourse problem in discrete time:L 1-multipliers for inequality constraints”,SIAM Journal on Control and Optimization 16 (1) (1978) 16–36. · Zbl 0397.90078 · doi:10.1137/0316002
[41] R.T. Rockafellar and R.J.-B. Wets, ”Scenarios and policy aggregation in optimization under uncertainty”,Mathematics of Operations Research 16 (1991) 119–147. · Zbl 0729.90067 · doi:10.1287/moor.16.1.119
[42] A. Rusczyński, ”Parallel decomposition of multistage stochastic programming problems”,Mathematical Programming 58 (2) (1993) 201–228. · Zbl 0777.90036 · doi:10.1007/BF01581267
[43] H. Vladimirou, ”Stochastic networks: Solution methods and applications in financial planning”, HD Thesis, Department of Civil Engineering and Operations Research, Princeton University (1990).
[44] R.J.-B. Wets, ”Stochastic programming: Solution techniques and approximation schemes”, in: A. Bachem, M. Grötschel and B. Korte, eds.,Mathematical Programming, The State of the Art (Springer, Berlin, 1983), pp. 566–603.
[45] R.J.-B. Wets, ”Large-scale linear programming techniques in stochastic programming”, in: Y. Ermoliev and R.J.-B. Wets, eds.,Numerical Techniques for Stochastic Optimization, (Springer, Berlin, 1988) pp. 65–94. · Zbl 0676.90043
[46] R.J.-B. Wets, ”The aggregation principle in scenario analysis and stochastic optimization”, in: S. Wallace, ed.,Algorithms and Model Formulations in Mathematical Programming (Springer, Berlin);NATO ASI 51 (1989) 91–113.
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.