Skip to main content
SpringerLink
Log in

Some Aspects of Stability in Stochastic Programming

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

Abstract

Some developments in structure and stability of stochastic programs during the last decade together with interrelations to optimization theory and stochastics are reviewed. With weak convergence of probability measures as a backbone we discuss qualitative and quantitative stability of recourse models that possibly involve integer variables. We sketch stability in chance constrained stochastic programming and provide some applications in statistical estimation. Finally, an outlook is devoted to issues that were not discussed in detail and to some open problems.

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. Z. Artstein, Sensitivity with respect to the underlying information in stochastic programs, Journal of Computational and Applied Mathematics 56 (1994) 127–136.

    Google Scholar 

  2. Z. Artstein, Probing for information in two-stage stochastic programming and the associated consistency, in: Asymptotic Statistics, eds. P. Mandl and M. Hušková (Springer, Berlin, 1994) pp. 21–33.

    Google Scholar 

  3. Z. Artstein and R.J.-B. Wets, Sensors and information in optimization under stochastic uncertainty, Mathematics of Operations Research 18 (1993) 523–547.

    Google Scholar 

  4. Z. Artstein and R.J.-B. Wets, Stability results for stochastic programs and sensors, allowing for discontinuous objective functions, SIAM Journal on Optimization 4 (1994) 537–550.

    Google Scholar 

  5. Z. Artstein and R.J.-B. Wets, Consistency of minimizers and the SLLN for stochastic programs, Journal of Convex Analysis 2 (1995) 1–17.

    Google Scholar 

  6. H. Attouch, Variational Convergence for Functions and Operators(Pitman, London, 1984).

    Google Scholar 

  7. H. Attouch and R.J.-B. Wets, Epigraphical processes: laws of large numbers for random lsc functions, Technical Report, Department of Mathematics, University of California, Davis (1991).

    Google Scholar 

  8. H. Attouch and R.J.-B. Wets, Quantitative stability of variational systems: II. A framework for nonlinear conditioning, SIAM Journal on Optimization 3 (1993) 359–381.

    Google Scholar 

  9. J.P. Aubin, Lipschitz behaviour of solutions to convex minimization problems, Mathematics of Operations Research 9 (1984) 87–111.

    Google Scholar 

  10. B. Bank, J. Guddat, D. Klatte, B. Kummer and K. vTammer, Non-Linear Parametric Optimization(Akademie-Verlag, Berlin, 1982).

    Google Scholar 

  11. B. Bank and R. Mandel, Parametric Integer Optimization(Akademie-Verlag, Berlin, 1988).

    Google Scholar 

  12. C. Berge, Topological Spaces(Macmillan, New York, 1963).

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  15. J.R. Birge and F. Louveaux, Introduction to Stochastic Programming(Springer, New York, 1997).

    Google Scholar 

  16. J.R. Birge and L. Qi, Subdifferential convergence in stochastic programs, SIAM Journal on Optimization 5 (1995) 436–453.

    Google Scholar 

  17. J.R. Birge and L. Qi, Continuous approximation schemes for stochastic programs, Annals of Operations Research 56 (1995) 15–38.

    Google Scholar 

  18. J.R. 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.

    Google Scholar 

  19. C.E. Blair and R.J.-B. Jeroslow, The value function of a mixed integer program: I, Discrete Mathematics 19 (1977) 121–138.

    Google Scholar 

  20. J.F. Bonnans and A. Shapiro, Optimization problems with perturbations: A guided tour, SIAM Review 40 (1998) 228–264.

    Google Scholar 

  21. C. Borell, Convex set functions in d-space, Periodica Mathematica Hungarica 6 (1975) 111–136.

    Google Scholar 

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

    Google Scholar 

  23. J.M. Danskin, The Theory of Max-Min and its Application to Weapons Allocations Problems(Springer, New York, 1967).

    Google Scholar 

  24. G.B. Dantzig, J. Folkman and N. Shapiro, On the continuity of the minimum set of a continuous function, Journal of Mathematical Analysis and Applications 17 (1967) 519–548.

    Google Scholar 

  25. D. Dentcheva, Differentiable selections of set-valued mappings with application in stochastic programming, Journal of Mathematical Analysis and Applications 223 (1998) 371–396.

    Google Scholar 

  26. D. Dentcheva and W. Römisch, Differential stability of two-stage stochastic programs, SIAM Journal on Optimization 11 (2000) 87–112.

    Google Scholar 

  27. R.M. Dudley, Real Analysis and Probability(Wadsworth & Brooks/Cole, Pacific Grove, CA, 1989).

    Google Scholar 

  28. J. Dupačová, Stability in stochastic programming with recourse-estimated parameters, Mathematical Programming 28 (1984) 72–83.

    Google Scholar 

  29. J. Dupačová, Stability in stochastic programming—probabilistic constraints, in: Stochastic Optimization, eds. V.I. Arkin, A. Shiraev and R.J.-B. Wets (Springer, Berlin, 1986) pp. 314–325.

    Google Scholar 

  30. J. Dupačová, Stochastic programming with incomplete information: A survey of results on postoptimization and sensitivity analysis, Optimization 18 (1987) 507–532.

    Google Scholar 

  31. J. Dupačová, Stability and sensitivity analysis for stochastic programming, Annals of Operations Research 27 (1990) 115–142.

    Google Scholar 

  32. J. Dupačová and W. Römisch, Quantitative stability for scenario-based stochastic programs, in: Prague Stochastics '98, eds. M. Hušková et al. (JCMF, Prague, 1998) pp. 119–124.

    Google Scholar 

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

    Google Scholar 

  34. A.V. Fiacco, Sensitivity analysis for nonlinear programming using penalty functions, Mathematical Programming 10 (1976) 287–311.

    Google Scholar 

  35. A.V. Fiacco, Introduction to Sensitivity and Stability Analysis in Nonlinear Programming(Academic Press, New York, 1983).

    Google Scholar 

  36. O. Fiedler and W. Römisch, Stability in multistage stochastic programming, Annals of Operations Research 56 (1995) 79–93.

    Google Scholar 

  37. S.J. Gartska, Distribution functions in stochastic programs with recourse: A parametric analysis, Mathematical Programming 6 (1974) 339–351.

    Google Scholar 

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

    Google Scholar 

  39. N. Gröwe, Estimated stochastic programs with chance constraints, European Journal of Operational Research 101 (1997) 285–305.

    Google Scholar 

  40. R. Henrion and W. Römisch, Metric regularity and quantitative stability in stochastic programs with probabilistic constraints, Mathematical Programming 84 (1999) 55–88.

    Google Scholar 

  41. R. Henrion and W. Römisch, Stability of solutions to chance constrained stochastic programs, in: Parametric Optimization and Related Topics, eds. J. Guddatt, R. Hirabaya Shi, H.Th. Jongen and F. Twilt (Peter Lang, Frankfurt a. M., 2000) pp. 95–114.

    Google Scholar 

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

    Google Scholar 

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

  44. P. Kall, A. Ruszczyński and K. Frauendorfer, Approximation techniques in stochastic programming, in: Numerical Techniques for Stochastic Optimization, eds. Yu. Ermoliev and R.J.-B.Wets (Springer, Berlin, 1988) pp. 33–64.

    Google Scholar 

  45. P. Kall and S.W. Wallace, Stochastic Programming(Wiley, Chichester, 1994).

    Google Scholar 

  46. Yu.M. Kaniovski, A.J. King and R.J.-B. Wets, Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems, Annals of Operations Research 56 (1995) 189–208.

    Google Scholar 

  47. V. Kaňková, Stability in the stochastic programming, Kybernetika 14 (1978) 339–349.

    Google Scholar 

  48. A.J. King, Asymptotic behavior of solutions in stochastic optimization: Nonsmooth analysis and the derivation of non-normal limit distributions, Ph.D. dissertation, University of Washington, Seattle (1986).

    Google Scholar 

  49. A.J. King, Generalized delta theorems for multivalued mappings and measurable selections, Mathematics of Operations Research 14 (1989) 720–736.

    Google Scholar 

  50. A.J. King and R.T. Rockafellar, Asymptotic theory for solutions in statistical estimation and stochastic programming, Mathematics of Operations Research 18 (1993) 148–162.

    Google Scholar 

  51. A.J. King and R.J.-B. Wets, Epi-consistency of convex stochastic programs, Stochastics and Stochastics Reports 34 (1991) 83–92.

    Google Scholar 

  52. D. Klatte, On the stability of local and global optimal solutions in parametric problems of nonlinear programming, Part I and Part II, in: Seminarbericht Nr. 75, Sektion Mathematik(Humboldt-Universität zu Berlin, Berlin, 1985) pp. 1–39.

    Google Scholar 

  53. D. Klatte, A note on quantitative stability results in nonlinear optimization, in: Seminarbericht Nr. 90, Sektion Mathematik (Humboldt-Universität zu Berlin, Berlin, 1987) pp. 77–86.

    Google Scholar 

  54. D. Klatte, On quantitative stability for non-isolated minima, Control and Cybernetics 23 (1994) 183–200.

    Google Scholar 

  55. D. Klatte and G. Thiere, Error bounds for solutions of linear equations and inequalities, Mathematical Methods of Operations Research 41 (1995) 191–214.

    Google Scholar 

  56. L. Korf and R.J.-B. Wets, Ergodic limit laws for stochastic optimization problems, Technical Report, Department of Mathematics, University of California, Davis (1997).

    Google Scholar 

  57. J. Kuelbs and R.M. Dudley, Log log laws for empirical measures, Annals of Probability 8 (1980) 405–418.

    Google Scholar 

  58. K. Marti, Approximationen der Entscheidungsprobleme mit linearer Ergebnisfunktion und positiv homogener, subadditiver Verlustfunktion, Zeitschrift für Wahrscheinlichkeitstheorie und verwandte Gebiete 31 (1975) 203–233.

    Google Scholar 

  59. B.S. Mordukhovich, Complete characterization of openness, metric regularity and Lipschitzian properties of multifunctions, Transactions of the American Mathematical Society 340 (1993) 1–35.

    Google Scholar 

  60. B.S. Mordukhovich, Generalized differential calculus for nonsmooth and set-valued mappings, Journal of Mathematical Analysis and Applications 183 (1994) 250–288.

    Google Scholar 

  61. G.L. Nemhauser and L.A. Wolsey, Integer and Combinatorial Optimization(Wiley, New York, 1988).

    Google Scholar 

  62. G.Ch. Pflug, Asymptotic stochastic programs, Mathematics of Operations Research 21 (1996) 769–789.

    Google Scholar 

  63. G.Ch. Pflug, Stochastic programs and statistical data, Annals of Operations Research 85 (1999) 59–78.

    Google Scholar 

  64. G.Ch. Pflug, A. Ruszczyński and R. Schultz, On the Glivenko–Cantelli problem in stochastic programming: Linear recourse and extensions, Mathematics of Operations Research 23 (1998) 204–220.

    Google Scholar 

  65. G.Ch. Pflug, A. Ruszczyński and R. Schultz, On the Glivenko–Cantelli problem in stochastic programming: Mixed-integer linear recourse, Mathematical Methods of Operations Reserach 47 (1998) 39–49.

    Google Scholar 

  66. D. Pollard, Convergence of Stochastic Processes(Springer, New York, 1984).

    Google Scholar 

  67. A. Prékopa, Logarithmic concave measures with applications to stochastic programming, Acta Scientiarum Mathematicarum 32 (1971) 301–316.

    Google Scholar 

  68. A. Prékopa, Stochastic Programming(Kluwer, Dordrecht, 1995).

    Google Scholar 

  69. S.T. Rachev, Probability Metrics and the Stability of Stochastic Models(Wiley, New York, 1991).

    Google Scholar 

  70. S.T. Rachev and W. Römisch, Quantitative stability of stochastic programs: The approach via probability metrics, Manuscript, Humboldt-Universität zu Berlin, Institut für Mathematik (1999).

  71. Y. Rinott, On convexity of measures, Annals of Probability 4 (1976) 1020–1026.

    Google Scholar 

  72. S.M. Robinson, Perturbed, Kuhn–Tucker points and rates of convergence for a class of nonlinearprogramming algorithms, Mathematical Programming 7 (1974) 1–16.

    Google Scholar 

  73. S.M. Robinson, Regularity and stability for convex multivalued functions, Mathematics of Operations Research 1 (1976) 130–143.

    Google Scholar 

  74. S.M. Robinson, Persistence and continuity of local optimizers, IIASA Collaborative Paper CP–84–5, IIASA Laxenburg, Austria (1984).

    Google Scholar 

  75. S.M. Robinson, Local epi-continuity and local optimization, Mathematical Programming 37 (1987) 208–222.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  78. R.T. Rockafellar, Lipschitzian properties of multifunctions, Nonlinear Analysis: Theory, Methods and Applications 9 (1985) 867–885.

    Google Scholar 

  79. R.T. Rockafellar and R.J.-B. Wets, Variational Analysis(Springer, Berlin, 1998).

    Google Scholar 

  80. W. Römisch and R. Schultz, Distribution sensitivity in stochastic programming, Mathematical Programming 50 (1991) 197–226.

    Google Scholar 

  81. W. Römisch and R. Schultz, Distribution sensitivity for certain classes of chance-constrained models with application to power dispatch, Journal of Optimization Theory and Applications 71 (1991) 569–588.

    Google Scholar 

  82. W. Römisch and R. Schultz, Stability analysis for stochastic programs, Annals of Operations Research 30 (1991) 241–266.

    Google Scholar 

  83. W. Römisch and R. Schultz, Lipschitz stability for stochastic programs with complete recourse, SIAM Journal on Optimization 6 (1996) 531–547.

    Google Scholar 

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

  85. R.Y. Rubinstein and A. Shapiro, Discrete Event Systems. Sensitivity Analysis and Stochastic Optimization by the Score Function Method(Wiley, Chichester, 1993).

    Google Scholar 

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

    Google Scholar 

  87. R. Schultz, Continuity and stability in two-stage stochastic integer programming, in: Stochastic Optimization, Numerical Methods and Technical Applications, ed. K. Marti, Lecture Notes in Economics and Mathematical Systems, Vol. 379 (Springer, Berlin, 1992) pp. 81–92.

    Google Scholar 

  88. R. Schultz, Continuity properties of expectation functions in stochastic integer programming, Mathematics of Operations Research 18 (1993) 578–589.

    Google Scholar 

  89. R. Schultz, Strong convexity in stochastic programs with complete recourse, Journal of Computational and Applied Mathematics 56 (1994) 3–22.

    Google Scholar 

  90. R. Schultz, On structure and stability in stochastic programs with random technology matrix and complete integer recourse, Mathematical Programming 70 (1995) 73–89.

    Google Scholar 

  91. R. Schultz, Rates of convergence in stochastic programs with complete integer recourse, SIAM Journal on Optimization 6 (1996) 1138–1152.

    Google Scholar 

  92. R.J. Serfling, Approximation Theorems of Mathematical Statistics(Wiley, New York, 1980).

    Google Scholar 

  93. A. Shapiro, Asymptotic properties of statistical estimators in stochastic programming, The Annals of Statistics 17 (1989) 841–858.

    Google Scholar 

  94. A. Shapiro, On concepts of directional differentiability, Journal of Optimization Theory and Applications 66 (1990) 477–487.

    Google Scholar 

  95. A. Shapiro, On differential stability in stochastic programming, Mathematical Programming 47 (1990) 107–116.

    Google Scholar 

  96. A. Shapiro, Asymptotic analysis of stochastic programs, Annals of Operations Research 30 (1991) 169–186.

    Google Scholar 

  97. A. Shapiro, Perturbation analysis of optimization problems in Banach spaces, Numerical Functional Analysis and Optimization 13 (1992) 97–116.

    Google Scholar 

  98. A. Shapiro, Asymptotic behavior of optimal solutions in stochastic programming, Mathematics of Operations Research 18 (1993) 829–845.

    Google Scholar 

  99. A. Shapiro, Quantitative stability in stochastic programming, Mathematical Programming 67 (1994) 99–108.

    Google Scholar 

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

    Google Scholar 

  101. L. Stougie, Design and analysis of algorithms for stochastic integer programming, Ph.D. Thesis, Center for Mathematics and Computer Science, Amsterdam (1985).

    Google Scholar 

  102. L. Stougie and M.H. Van der Vlerk, Stochastic integer programming, in: Annotated Bibliographies in Combinatorial Optimization, eds. M. Dell'Amico, F. Maffioli and S. Martello (Wiley, Chichester, 1997) pp. 127–141.

    Google Scholar 

  103. A.W. Van der Vaart and J.A. Wellner, Weak Convergence and Empirical Processes(Springer, New York, 1996).

    Google Scholar 

  104. V.N. Vapnik and A.V. červonenkis, On the uniform convergence of relative frequencies of events to their probabilities, Theory of Probability and Applications 16 (1971) 264–280.

    Google Scholar 

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

    Google Scholar 

  106. S. Vogel, A stochastic approach to stability in stochastic programming, Journal of Computational and Applied Mathematics 56 (1994) 65–96.

    Google Scholar 

  107. D.W. Walkup and R.J.-B. Wets, Lifting projections of convex polyhedra, Pacific Journal of Mathematics 28 (1969) 465–475.

    Google Scholar 

  108. J. Wang, Continuity of feasible solution sets of probabilistic constrained programs, Journal of Optimization Theory and Applications 63 (1989) 79–89.

    Google Scholar 

  109. J. Wang, Stability of multistage stochastic programming, Annals of Operations Research 56 (1995) 313–322.

    Google Scholar 

  110. R.J.-B. Wets, Stochastic programs with fixed recourse: the equivalent deterministic program, SIAM Review 16 (1974) 309–339.

    Google Scholar 

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

    Google Scholar 

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

  113. R.J.-B. Wets, Constrained estimation: Consistency and asymptotics, Applied Stochastic Models and Data Analysis 7 (1991) 17–32.

    Google Scholar 

  114. R.J.-B. Wets, Challenges in stochastic programming, Mathematical Programming 75 (1996) 115–135.

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Department of Mathematics, Gerhard-Mercator University Duisburg, Lotharstr. 65, D-47048, Duisburg, Germany

    Rüdiger Schultz

Authors
  1. 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

Schultz, R. Some Aspects of Stability in Stochastic Programming. Annals of Operations Research 100, 55–84 (2000). https://doi.org/10.1023/A:1019258932012

Download citation

  • Issue Date:

  • DOI: https://doi.org/10.1023/A:1019258932012

Search

Navigation