Skip to main content
SpringerLink
Log in

Stability analysis for stochastic programs

  • Theory
  • Published:
Annals of Operations Research Aims and scope Submit manuscript

Abstract

For stochastic programs with recourse and with (several joint) probabilistic constraints, respectively, we derive quantitative continuity properties of the relevant expectation functionals and constraint set mappings. This leads to qualitative and quantitative stability results for optimal values and optimal solutions with respect to perturbations of the underlying probability distributions. Earlier stability results for stochastic programs with recourse and for those with probabilistic constraints are refined and extended, respectively. Emphasis is placed on equipping sets of probability measures with metrics that one can handle in specific situations. To illustrate the general stability results we present possible consequences when estimating the original probability measure via empirical ones.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Similar content being viewed by others

References

  1. W. Alt, Lipschitzian perturbations of infinite optimization problems, in:Mathematical Programming with Data Perturbations II, ed. A.V. Fiacco (M. Dekker, New York, 1983) pp. 7–21.

    Google Scholar 

  2. R.N. Bhattacharya and R. Ranga Rao,Normal Approximation and Asymptotic Expansions (Wiley, New York, 1976).

    Google Scholar 

  3. P. Billingsley,Convergence of Probability Measures (Wiley, New York, 1968).

    Google Scholar 

  4. J.R. Birge and R.J.-B. Wets, Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse, Math. Progr. Study 27 (1986) 54–102.

    Google Scholar 

  5. C. Borell, Convex set functions ind-space, Periodica Math. Hung. 6 (1975) 111–136.

    Google Scholar 

  6. F.H. Clarke,Optimization and Nonsmooth Analysis (Wiley, New York, 1983).

    Google Scholar 

  7. S. Dancs and B. Uhrin, On a class of integral inequalities and their measure-theoretic consequences, J. Math. Anal. Appl. 74 (1980) 388–400.

    Google Scholar 

  8. R.M. Dudley, The speed of mean Glivenko-Cantelli convergence, Ann. Math. Statist. 40 (1969) 40–50.

    Google Scholar 

  9. R.M. Dudley,Probabilities and Metrics, Lecture Notes Series No. 45. Aarhus Universitet, Aarhus, Denmark (1976).

    Google Scholar 

  10. J. Dupačová, Stability and sensitivity analysis for stochastic programming, Ann. Oper. Res. 27 (1990) 115–142.

    Google Scholar 

  11. J. Dupačová and R.J.-B. Wets, Asymptotic behaviour of statistical estimators and of optimal solutions of stochastic optimization problems, Ann. Statist. 16 (1988) 1517–1549.

    Google Scholar 

  12. Y. Ermoliev and R.J.-B. Wets (eds.),Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988).

    Google Scholar 

  13. P. Gaenssler and W. Stute, Empirical processes: A survey of results for independent and identically distributed random variables, Ann. Prob. 7 (1979) 193–243.

    Google Scholar 

  14. M. Gelbrich, On a formula for theL 2-Wasserstein metric between measures on Euclidean and Hilbert spaces, Math. Nachr. 147 (1990) 185–203.

    Google Scholar 

  15. C.R. Givens and R.M. Shortt, A class of Wasserstein metrics for probability distributions, Michigan Math. J. 31 (1984) 231–240.

    Google Scholar 

  16. P. Kall,Stochastic Linear Programming (Springer, Berlin, 1976).

    Google Scholar 

  17. 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.

    Google Scholar 

  18. V. Kaňková, Estimates in stochastic programming-chance constrained case, Problems Control Inf. Theory, to appear.

  19. A.J. King and R.J.-B. Wets, Epi-consistency of convex stochastic programs, Research Report, IBM Research Division, T.J. Watson Research Center, Yorktown Heights, New York (1989).

    Google Scholar 

  20. D. Klatte, A note on quantitative stability results in nonlinear optimization, in:Proc. 19. Jahrestagung Mathematische Optimierung, ed. K. Lommatzsch (Seminarbericht Nr. 90, Humboldt-Universität Berlin, Sektion Mathematik, 1987) pp. 77–86.

  21. R. Lucchetti, G. Salinetti and R.J.-B. Wets Uniform convergence of probability measures: Topological criteria, Technical Report, University of California, Davis (1989).

    Google Scholar 

  22. H. Niederreiter and J.M. Wills, Diskrepanz und Distanz von Massen bezüglich konvexer und Jordanscher Mengen, Math. Zeits. 144 (1975) 125–134.

    Google Scholar 

  23. C. van de Panne and W. Popp, Minimum cost cattle feed under probabilistic protein constraints, Manag. Sci. 9 (1963) 405–430.

    Google Scholar 

  24. A. Prékopa. Logarithmic concave measures with applications to stochastic programming, Acta Sci. Math. 32 (1971) 301–316.

    Google Scholar 

  25. A. Prékopa, Logarithmic concave measures and related topics, in:Stochastic Programming, ed. M.A.H. Dempster, (Academic Press, London, 1980) pp. 63–82.

    Google Scholar 

  26. S.T. Rachev, The Monge-Kantorovich mass transference problem and its stochastic applications, Theory Prob. Appl. 29 (1984) 647–676.

    Google Scholar 

  27. Y. Rinott, On convexity of measures, Ann. Prob. 4 (1976) 1020–1026.

    Google Scholar 

  28. S.M. Robinson, Stability theory for systems of inequalities, Part I: Linear systems, SIAM J. Num. Anal. 12 (1975) 754–769.

    Google Scholar 

  29. S.M. Robinson, Regularity and stability for convex multivalued functions, Math. Oper. Res. 1 (1976) 130–143.

    Google Scholar 

  30. S.M. Robinson, Local epi-continuity and local optimization, Math. Progr. 37 (1987) 208–223.

    Google Scholar 

  31. S.M. Robinson and R.J.-B. Wets, Stability in two-stage stochastic programming, SIAM J. Control Optim. 25 (1987) 1409–1416.

    Google Scholar 

  32. R.T. Rockafellar, Lipschitzian properties of multifunctions, Nonlinear Anal. Theory, Meth. Appl. 9 (1985) 867–885.

    Google Scholar 

  33. W. Römisch and R. Schultz, Distribution sensitivity in stochastic programming, Math. Progr. (1991) to appear.

  34. W. Römisch and R. Schultz, Distribution sensitivity for certain classes of chance constrained models—with application to power dispatch, J. Optim. Theory Appl., to appear.

  35. W. Römisch and R. Schultz, Stability of solutions for stochastic programs with complete recourse havingC 1,1 data, Manuskript, Institut für Operations Research, Universität Zürich, Switzerland (1989).

    Google Scholar 

  36. 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.

    Google Scholar 

  37. G. Salinetti, Approximations for chance-constrained programming problems, Stochastics 10 (1983) 157–179.

    Google Scholar 

  38. A. Shapiro, Gâteaux, Fréchet and Hadamard directional differentiability of functional solutions in stochastic programming, Mimeograph Series No. 395, Operations Research and Statistics, Technion, Haifa, Israel (1988).

    Google Scholar 

  39. G.R. Shorack and J.A. Wellner,Empirical Processes with Applications to Statistics (Wiley, New York, 1986).

    Google Scholar 

  40. S. Vogel, Stability results for stochastic programming problems, Optimization 19 (1988) 269–288.

    Google Scholar 

  41. J. Wang, Continuity of feasible solution sets of probabilistic constrained programs, J. Optim. Theory Appl. 63 (1989) 79–89.

    Google Scholar 

  42. R.J.-B. Wets, Stochastic programming: solution techniques and approximation schemes, in:Mathematical Programming—The State of the Art 1982, eds. A Bachem, M. Grötschel and B. Korte (Springer, Berlin, 1983) pp. 566–603.

    Google Scholar 

  43. 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, 1989) pp. 573–629.

Download references

Author information

Authors and Affiliations

  1. Sektion Mathematik, Humboldt-Universität Berlin, P.O. Box. 1297, D-1086, Berlin, Germany

    Werner Römisch & Rüdiger Schultz

Authors
  1. Werner Römisch
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. Rüdiger Schultz
    View author publications

    You can also search for this author in PubMed Google Scholar

Rights and permissions

Reprints and permissions

About this article

Cite this article

Römisch, W., Schultz, R. Stability analysis for stochastic programs. Ann Oper Res 30, 241–266 (1991). https://doi.org/10.1007/BF02204819

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1007/BF02204819

Key words

Search

Navigation