Multistage stochastic programming: Error analysis for the convex case. (English) Zbl 0810.90098

From the introduction of the paper: ‘An approximation technique for convex stochastic multistage programming problems is proposed. This technique is based on the barycentric optimization scheme developed recently by the author [‘Stochastic two-stage programming’, Lect. Notes Econ. Math. Syst. 392 (1992; Zbl 0794.90042)] and it allows to analyze the error with respect to time (stages)’.
Reviewer: E.Tamm (Tallinn)


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


Zbl 0794.90042


Full Text: DOI


[1] Birge J (1985) Decomposition and partitioning methods for multi-stage stochastic linear programs.Operations Research 33:989-1007 · Zbl 0581.90065 · doi:10.1287/opre.33.5.989
[2] Birge J (1988) AnL-shaped computer code for multi-stage stochastic linear programs. In: Ermoliev Y and Wets RJ-B (eds)Numerical techniques for stochastic optimization, Springer-Verlag 255-266
[3] Birge J (1988) The relationship between theL-shaped method and dual basis factorization for stochastic linear programming. In: Ermoliev Y and Wets RJ-B (eds)Numerical techniques for stochastic optimization, Springer-Verlag 267-272 · Zbl 0667.90074
[4] Birge J, Wets RJ-B (1986) Designing approximation schemes for stochastic optimization problems in particular for stochastic programs with recourse.Math Prog Study 27:54-102 · Zbl 0603.90104
[5] Birge J, Wets RJ-B (1987) Computing bounds for stochastic programming problems by means of a generalized moment problem.Math of OR 12:149-162 · Zbl 0619.90053 · doi:10.1287/moor.12.1.149
[6] Birge J, Wets RJ-B (1991)Stochastic programming, Part I, II; Proceedings of the 5th International Conference on Stochastic Programming, Ann Arbor, Michigan, August 13-18, 1989, Annals of Operations Research 30-31
[7] Dantzig GB, Glynn PW (1990) Parallel processors for planning under uncertainty.Annals of Operations Research 22:1-21 · Zbl 0714.90074 · doi:10.1007/BF02023045
[8] Dantzig GB, Infanger G (1991) Multistage stochastic linear programs for portfolio optimization. Technical Report SOL 91-11, Stanford University
[9] Dempster MAH (ed) (1980)Stochastic programming; Proceedings of the 1st International Conference on Stochastic Programming, Oxford 1974; Academic Press
[10] Dempster MAH (1980) Introduction to stochastic programming. In; Dempster MAH (ed)Stochastic Programming; Academic Press 3-59
[11] Dempster MAH (1986) On stochastic programming II: Dynamic problems under risk; Research Report DAL TR 86-5, Dalhousie University
[12] Dupacova J (1990) Stability and sensitivity analysis for stochastic programming.Annals of Operations Research 27:115-142 · Zbl 0724.90049 · doi:10.1007/BF02055193
[13] Edirisinghe NCP, Ziemba WT (1992) Bounds for two-stage stochastic programs with fixed recourse, Working Paper, Faculty of Commerce, University of British Columbia, Vancouver, Canada (to appear inMathematics of OR)
[14] Edirisinghe NCP, Ziemba WT (1992) Bounding the expectation of a saddle function with application to stochastic programming, Working Paper, Faculty of Commerce, University of British Columbia, Vancouver, Canada (to appear inMathematics of OR)
[15] Ermoliev Y, Wets RJ-B (1988)Numerical techniques for stochastic optimization; Springer-Verlag · Zbl 0658.00020
[16] Ermoliev Y, Wets RJ-B (1988) Stochastic programming, an introduction. In: Ermoliev Y,Wets RJ-B (eds)Numerical Techniques for Stochastic Optimization; Springer-Verlag 1-32
[17] Fiedler O, Römisch W (1993) Stability in stochastic multistage programming; Working paper, Humboldt University
[18] Frauendorfer K (1988) Solving SLP recourse problems with arbitrary multivariate distributions ? The dependent case.Math of OR 13/3:377-394 · Zbl 0652.90080 · doi:10.1287/moor.13.3.377
[19] Frauendorfer K (1992)Stochastic two-stage programming. Lecture Notes in Economics and Mathematical Systems 392 Springer-Verlag · Zbl 0794.90042
[20] Frauendorfer K, Kall P (1988) A solution method for SLP recourse problems with Arbitrary distributions ? The independent case.Problems of Control and Information Theory 17:177-205 · Zbl 0651.90054
[21] Gassmann HI (1990) MSLiP: A computer code for the multistage stochastic linear programming problem.Math Prog 47:407-423 · Zbl 0701.90070 · doi:10.1007/BF01580872
[22] Hartley R (1980) Inequalities for a class of sequential stochastic decision process. In: Dempster MAH (ed)Stochastic programming, Academic Press 3-59 · Zbl 0459.90085
[23] Hartley R (1980) Inequalities in completely convex stochastic programming.Journal of Math Anal and Applic 75:373-384 · Zbl 0446.90062 · doi:10.1016/0022-247X(80)90086-4
[24] Hernandez-Lerma O, Runggaldier WJ (1993) Monotone approximations for convex stochastic control problems, (to appear inJournal of Estimation, Control and Systems)
[25] Huang C, Ziemba WT, Ben-Tal A (1977) Bounds on the expectation of a convex function of a random variable: With application to stochastic programming.Operations Research 25:315-325 · Zbl 0362.62014 · doi:10.1287/opre.25.2.315
[26] Infanger G (1992) Monte Carlo (Importance) sampling within Bender’s decomposition for stochastic linear programs.Annals of Operations Research 39 · Zbl 0773.90054
[27] Kall P (1987) On approximation and stability in stochastic programming. In: Guddat J, Jongen HTh, Kummer B, Nozicka F (eds)Parametric Optimization and Related Topics; Akademie-Verlag 387-404
[28] Kall P (1988) Stochastic programming with recourse: Upper bound and moment problems ? A review. In: Guddat J, Bank B, Hollatz H, Kall P, Klatte D, Kummer B, Lommatzsch K, Tammer K, Vlach M, Zimmermann K (eds)Advances in Mathematical Optimization; Akademie-Verlag 86-103
[29] Kall P, Ruszczynski A, Frauendorfer K (1988) Approximation techniques in stochastic programming. In: Ermoliev Y, Wets RJ-B (eds)Numerical Techniques for Stochastic Optimization, Springer-Verlag 33-64 · Zbl 0665.90067
[30] Kall P, Stoyan D (1982) Solving programming problems with recourse including error bound. Mathematische Operationsforschung und Statistik,Ser Opt 13:431-447 · Zbl 0507.90067
[31] Loève M (1963)Probability theory · Zbl 0108.14202
[32] Louveaux FV (1980) A solution method for multistage stochastic programs with recourse, with application to an energy investment problem.Operations Research 28/4:889-902 · Zbl 0441.90076 · doi:10.1287/opre.28.4.889
[33] Mulvey JM, Vladimirou H (1991) Solving multistage stochastic networks: An application of scenario aggregation.Networks 21/6:619-643 · Zbl 0743.90053 · doi:10.1002/net.3230210603
[34] Mulvey JM, Vladimirou H (1991) Applying the progressive hedging algorithm to stochastic generalized networks. In: Birge J, Wets RJ-B (eds)Stochastic Programming, Part II; Annals of Operations Research 31:399-424 · Zbl 0734.90033
[35] Mulvey JM, Vladimirou H (1992) Stochastic network programming for financial planning problems; Princeton University, Department of Civil Engineering and Operations Research; to appear in Management Science
[36] Olsen P (1976) Multistage stochastic programming with recourse: The equivalent deterministic problem.SIAM J Control and Optimization 14/3:495-517 · Zbl 0336.90039 · doi:10.1137/0314033
[37] Olsen P (1976) When is a multistage stochastic programming well-defined?SIAM J Control and Optimization 14/3:518-527 · Zbl 0336.90040 · doi:10.1137/0314034
[38] Olsen P (1976) Multistage stochastic programming with recourse as mathematical programming in anL p -space.SIAM J Control and Optimization 14/3:528-537 · Zbl 0336.90041 · doi:10.1137/0314035
[39] Olsen P (1976) Discretization of multistage stochastic programming problems.Math Prog Study 6:111-124 · Zbl 0374.90053
[40] Prekopa A, Szantai T (1976) On multi-stage stochastic programming (with Application to optimal control of Water Supply). In: Prekopa A (ed)Progress in Operations Research, North-Holland 733-755 · Zbl 0337.90067
[41] Prekopa A, Szantai T (1979) On optimal regulation of a storage level with application to the Water level regulation of a lake. In: Prekopa A (ed)Survey of mathematical programming, North Holland 2:183-210 · Zbl 0399.90051
[42] Robinson SM, Wets RJ-B (1987) Stability in two-stage stochastic programming.SIAM J Cont and Opt 25:1409-1416 · Zbl 0639.90074 · doi:10.1137/0325077
[43] Robinson SM (1991) Extended scenario analysis. In: Birge J, Wets RJ-B (eds)Stochastic Programming, Part II; Annals of Operations Research 31:385-398 · Zbl 0739.90049
[44] Rockafellar RT (1970)Convex analysis. Princeton University Press · Zbl 0193.18401
[45] Rockafellar RT (1976) Integral functionals, normal integrand and measurable selections. In:Nonlinear operators and the calculus of variations. Lecture Notes in Mathematics 543 Springer-Verlag 157-207
[46] Rockafellar RT, Wets RJ-B (1976) Nonanticipativity andL 1-martingales in stochastic optimization problems.Math Prog Study 6:170-187
[47] Rockafellar RT, Wets RJ-B (1978) The optimal recourse problem in discrete time:L 1-multipliers for inequality constraints.SIAM J Control and Optimization 16/1:16-36 · Zbl 0397.90078 · doi:10.1137/0316002
[48] Rockafellar RT, Wets RJ-B (1990) Generalized linear-quadratic problems of deterministic and stochastic optimal control in discrete time.SIAM J Control and Optimization 28/4:810-822 · Zbl 0714.49036 · doi:10.1137/0328046
[49] Rockafellar RT, Wets RJ-B (1991) Scenarios and policy aggregation in optimization under uncertainty.Math of OR 16:119-147 · Zbl 0729.90067 · doi:10.1287/moor.16.1.119
[50] Römisch W, Schultz R (1991) Stability analysis for stochastic programs.Annals of Operations Research 30:241-266 · Zbl 0748.90047 · doi:10.1007/BF02204819
[51] Römisch W, Schultz R (1991) Distribution sensitivity in stochastic programming.Mathematical Programming 50:197-226 · Zbl 0743.90083 · doi:10.1007/BF01594935
[52] Ruszczynski A (1993) Parallel decomposition of multistage stochastic programming problems.Mathematical Programming 58/2:201-228 · Zbl 0777.90036 · doi:10.1007/BF01581267
[53] Varaiya P, Wets RJ-B (1990) Stochastic dynamic optimization: Approaches and computation. In: Iri M, Tanabe K (eds) Mathematical Programming (KTKSci Publ.) Tokyo, 309-332
[54] Vogel S (1992) On stability in multiobjective programming ? A stochastic approach.Mathematical Programming 56:91-119 · Zbl 0770.90061 · doi:10.1007/BF01580896
[55] Wallace SW, Yan T (1993) Bounding multistage stochastic linear programs from above. Mathematical Programming 61:111-130 · Zbl 0783.90092 · doi:10.1007/BF01582142
[56] Wets RJ-B (1983) Stochastic programming: Solution techniques and approximation schemes. In: Bachem A, Grötschel M, Korte B (eds)Mathematical programming, The state of the art; Springer-Verlag 566-603
[57] Wets RJ-B (1988) Large-scale linear programming techniques in stochastic programming. In: Ermoliev Y, Wets RJ-B (eds)Numerical Techniques for Stochastic Optimization; Springer-Verlag 65-94
[58] Wets RJ-B (1989) Stochastic programming. In: Nemhauser GL, Rinnooy Kan AHG, Todd MJ (eds)Handbook on Operations Research and Management Science 1: Optimization, North-Holland 573-629
[59] Wets RJ-B (1989) The aggregation principle in scenario analysis and stochastic optimization. In: Wallace S (ed)Algorithms and Model Formulations in Mathematical Programming, Springer-Verlag, NATO ASI 51: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.