Abstract
Multistage stochastic programs are regarded as mathematical programs in a Banach spaceX of summable functions. Relying on a result for parametric programs in Banach spaces, the paper presents conditions under which linearly constrained convex multistage problems behave stably when the (input) data process is subjected to (small) perturbations. In particular, we show the persistence of optimal solutions, the local Lipschitz continuity of the optimal value and the upper semicontinuity of optimal sets with respect to the weak topology inX. The linear case with deterministic first-stage decisions is studied in more detail.
Similar content being viewed by others
References
V.I. Arkin and I.V. Evstigneev,Stochastic Models of Control and Economic Dynamics (Academic Press, London, 1987).
B. Bank, J. Guddat, D. Klatte, B. Kummer and K. Tammer,Non-Linear Parametric Optimization (Akademie-Verlag, Berlin, 1982).
J.R. Birge and M.A.H. Dempster, Optimality conditions for match-up strategies in stochastic scheduling, The University of Michigan, Department of Industrial and Operations Engineering, Technical Report 92-58 (1992).
M.A.H. Dempster, On stochastic programming II: Dynamic problems under risk, Stochastics 25 (1988) 15–42.
J. Dupačová, Stability and sensitivity analysis for stochastic programming, Ann. Oper. Res. 27 (1990) 115–142.
J. Dupačová, Postoptimality for multistage stochastic linear programs, Ann. Oper. Res. 56 (1995), this volume.
J. Dupačová, Multistage stochastic programs: The state-of-the-art and selected bibliography, Kybernetika 31 (1995), to appear.
M.J. Eisner and P. Olsen, Duality for stochastic programming interpreted as LP inL p -space, SIAM J. Appl. Math. 28 (1975) 779–792.
I.V. Evstigneev, Measurable selection and dynamic programming, Math. Oper. Res. 1 (1976) 267–272.
S.D. Flåm, Resource management under uncertainty, The Chr. Michelsen Institute, Report CMI No. 842555-5 (1984).
S.D. Flåm, Lagrange multipliers in stochastic programming, SIAM J. Contr. Optim. 30 (1992) 1–10.
K. Frauendorfer, Multistage stochastic programming: Error analysis for the convex case, ZOR-Math. Meth. Oper. Res. 39 (1994) 93–122.
F. Hiai and H. Umegaki, Integrals, conditional expectations, and martingales of multivalued functions, J. Multivariate Anal. 7 (1977) 149–182.
J.-B. Hiriart-Urruty, Extension of Lipschitz integrands and minimization of nonconvex integral functionals: Applications to the optimal recourse problem in discrete time, Prob. Math. Statist. 3 (1982) 19–36.
P. Kall, On approximations and stability in stochastic programming, in:Parametric Optimization and Related Topics, eds. J. Guddat, H.Th. Jongen, B. Kummer and F. Nožička (Akademie-Verlag, Berlin, 1987) pp. 387–407.
A. Kirsch, Continuous perturbations of infinite optimization problems, J. Optim. Theory Appl. 32 (1980) 171–182.
R. Lepp, Discrete approximation of linear two-stage stochastic programming problem, Numer. Functional Anal. Optim. 9 (1987) 19–33.
P. Olsen, Multistage stochastic programming with recourse as mathematical programming in anL p -space, SIAM J. Contr. Optim. 14 (1976) 528–537.
P. Olsen, Discretizations of multistage stochastic programming problems, Math. Progr. Study 6 (1976) 111–124.
M.V.F. Pereira and L.M.V.G. Pinto, Multi-stage stochastic optimization applied to energy planning, Math. Progr. 52 (1991) 359–375.
S.T. Rachev,Probability Metrics and the Stability of Stochastic Models (Wiley, Chichester, 1991).
S.M. Robinson, Stability theory for systems of inequalities. Part I: Linear systems, SIAM J. Numer. Anal. 12 (1975) 754–769.
S.M. Robinson and R.J.-B. Wets, Stability in two-stage stochastic programming, SIAM J. Contr. Optim. 25 (1987) 1409–1416.
R.T. Rockafellar, Level sets and continuity of conjugate convex functions, Trans. Amer. Math. Soc. 123 (1966) 46–63.
R.T. Rockafellar,Convex Analysis (Princeton University Press, Princeton, 1970).
R.T. Rockafellar, Integral functionals, normal integrands and measurable selections, in:Nonlinear Operators and the Calculus of Variations, eds. G.P. Gossez et al., Lecture Notes in Mathematics Vol. 543 (Springer, New York, 1976) pp. 157–207.
R.T. Rockafellar and R.J.-B. Wets, Nonanticipativity and ℒ1-martingales in stochastic optimization problems, Math. Progr. Study 6 (1976) 170–187.
R.T. Rockafellar and R.J.-B. Wets, The optimal recourse problem in discrete time:L 1 multipliers for inequality constraints, SIAM J. Contr. Optim. 16 (1978) 16–36.
W. Römisch and R. Schultz, Stability analysis for stochastic programs, Ann. Oper. Res. 30 (1991) 241–266.
W. Römisch and R. Schultz, Stability of solutions for stochastic programs with complete recourse, Math. Oper. Res. 18 (1993) 590–609.
W. Römisch and A. Wakolbinger, Obtaining convergence rates for approximations in stochastic programming, in:Parametric Optimization and Related Topics, eds. J. Guddat, H.Th. Jongen, B. Kummer and F. Nožička (Akademie-Verlag, Berlin, 1987) pp. 327–343.
R.J.-B. Wets, Stochastic programs with recourse: A basic theorem for multistage problems, Zeits. Wahrscheinlichkeitstheorie und verwandte Gebiete 21 (1972) 201–206.
R.J.-B. Wets, On the relation between stochastic and deterministic optimization, in:Control Theory, Numerical Methods and Computer Systems Modelling, eds. A. Bensoussan and J.L. Lions, Lecture Notes in Economics and Mathematical Systems Vol. 107 (Springer, Berlin, 1975) pp. 350–361.
R.J.-B. Wets, Stochastic programming, in:Handbooks in Operations Research and Management Science, Vol. 1:Optimization, eds. G.L. Nemhauser, A.H.G. Rinnooy Kan and M.J. Todd (North-Holland, Amsterdam, 1989) pp. 573–629.
V.M. Zolotarev, Metric distances in spaces of random variables and their distributions, Math. USSR Sbornik 30 (1976) 373–401.
J. Zowe and S. Kurcyusz, Regularity and stability of the mathematical programming problem in Banach spaces, Appl. Math. Optim. 5 (1979) 49–62.
Author information
Authors and Affiliations
Additional information
This research has been supported by the Schwerpunktprogramm “Anwendungsbezogene Optimierung und Steuerung” of the Deutsche Forschungsgemeinschaft.
Rights and permissions
About this article
Cite this article
Fiedler, O., Römisch, W. Stability in multistage stochastic programming. Ann Oper Res 56, 79–93 (1995). https://doi.org/10.1007/BF02031701
Issue Date:
DOI: https://doi.org/10.1007/BF02031701