Skip to main content
SpringerLink
Log in

Distribution sensitivity in stochastic programming

  • Published:
Mathematical Programming Submit manuscript

Abstract

In this paper, stochastic programming problems are viewed as parametric programs with respect to the probability distributions of the random coefficients. General results on quantitative stability in parametric optimization are used to study distribution sensitivity of stochastic programs. For recourse and chance constrained models quantitative continuity results for optimal values and optimal solution sets are proved (with respect to suitable metrics on the space of probability distributions). The results are useful to study the effect of approximations and of incomplete information in stochastic programming.

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: A.V. Fiacco, ed.,Mathematical Programming with Data Perturbations II. Proceedings of the 2nd Symposium on Mathematical Programming with Data Perturbations, Washington 1980 (Dekker, New York and Basel, 1983) pp. 7–21.

    Google Scholar 

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

    Google Scholar 

  3. A. Auslender, “Stability in mathematical programming with non-differentiable data,”SIAM Journal on Control and Optimization 22 (1984) 239–254.

    Google Scholar 

  4. B. Bank, J. Guddat, D. Klatte, B. Kummer and K. Tammer,Non-linear Parametric Optimization (Akademie-Verlag, Berlin, 1982).

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  7. P. Billingsley and F. Topsøe, “Uniformity in weak convergence,”Zeitschrift für Wahrscheinlichkeits-theorie und Verwandte Gebiete 7 (1967) 1–16.

    Google Scholar 

  8. J. Birge and R. Wets, “Designing approximation schemes for stochastic optimization problems, in particular for stochastic programs with recourse,”Mathematical Programming Study 27 (1986) 54–102.

    Google Scholar 

  9. J. Birge and R. Wets, “Sublinear upper bounds for stochastic programs with recourse,”Mathematical Programming 43 (1989) 131–149.

    Google Scholar 

  10. S. Chevet, “Gaussian measures and large deviations,” in: A. Beck and K. Jacobs, eds.,Probability in Banach Spaces IV. Lecture Notes in Mathematics No. 990 (Springer, Berlin, 1983) pp. 30–46.

    Google Scholar 

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

    Google Scholar 

  12. B. Cornet and J.Ph. Vial, “Lipschitzian solutions of perturbed nonlinear programming problems,”SIAM Journal on Control and Optimization 24 (1986) 1123–1137.

    Google Scholar 

  13. A. Donchev and H.Th. Jongen, “On the regularity of the Kuhn-Tucker curve,”SIAM Journal on Control and Optimization 24 (1986) 169–176.

    Google Scholar 

  14. R.M. Dudley, “The speed of mean Glivenko-Cantelli convergence,”Annals of Mathematical Statistics 40 (1969) 40–50.

    Google Scholar 

  15. R.M. Dudley, “Speeds of metric probability convergence,”Zeitschrift für Wahrscheinlichkeitstheorie und Verwandte Gebiete 22 (1972) 323–332.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  18. J. Dupačová, “Stability in stochastic programming-probabilistic constraints,” in: V.I. Arkin, A. Shiriaev and R. Wets, eds.,Proceedings of the International Conference on Stochastic Optimization, Kiev. Lecture Notes in Control and Information Sciences No. 81 (Springer, Berlin, 1986) pp. 314–325.

    Google Scholar 

  19. J. Dupačová, “Stability in stochastic programming with recourse. Contaminated distributions,”Mathematical Programming Study 27 (1986) 133–144.

    Google Scholar 

  20. J. Dupačová, “Stochastic programming with incomplete information,” IIASA-Working-Paper WP 86-08, International Institute for Applied Systems Analysis (Laxenburg, Austria, 1986).

    Google Scholar 

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

    Google Scholar 

  22. P. Gaenssler and W. Stute, “Empirical Processes: A survey of results for independent and identically distributed random variables,”Annals of Probability 7 (1979) 193–243.

    Google Scholar 

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

    Google Scholar 

  24. H. Gassmann and W.T. Ziemba, “A tight upper bound for the expectation of a convex function of a multivariate random variable,”Mathematical Programming Study 27 (1986) 39–53.

    Google Scholar 

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

    Google Scholar 

  26. W.W. Hager, “Lipschitz continuity for constrained processes,”SIAM Journal on Control and Optimization 17 (1979) 321–338.

    Google Scholar 

  27. P.J. Huber,Robust Statistics (Wiley, New York, 1981).

    Google Scholar 

  28. P. Kall, “Approximations to stochastic programs with complete fixed recourse,”Numerische Mathematik 22 (1974) 333–339.

    Google Scholar 

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

    Google Scholar 

  30. P. Kall, “On approximations and stability in stochastic programming,” in: J. Guddat, H.Th. Jongen, B. Kummer and F. Nožička, eds.,Parametric Optimization and Related Topics. Proceedings of the International Conference in Plaue, GDR, 1985 (Akademie-Verlag, Berlin, 1987), pp. 387–407.

    Google Scholar 

  31. P. Kall and D Stoyan, “Solving stochastic programming problems with recourse including error bounds,”Mathematische Operationsforschung und Statistik, Series Optimization 13 (1982) 431–447.

    Google Scholar 

  32. P. Kall, A. Ruszczyński and K. Frauendorfer, “Approximation techniques in stochastic programming,” in: Y. Ermoliev and R. Wets, eds.,Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 33–64.

    Google Scholar 

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

    Google Scholar 

  34. V. Kaňková, “Uncertainty in stochastic programming,” in: V.I. Arkin, A. Shiriaev and R. Wets, eds.,Proceedings of the International Conference on Stochastic Optimization, Kiev. Lecture Notes in Control and Information Sciences No. 81 (Springer, Berlin 1986) pp. 393–401.

    Google Scholar 

  35. D. Klatte, “On the stability of local and global optimal solutions in parametric problems of nonlinear programming. Part I and Part II,”Seminarbericht No. 75 (Humboldt-Universität Berlin, Berlin, 1985).

    Google Scholar 

  36. D. Klatte, “A note on quantitative stability results in nonlinear optimization,” in: K. Lommatzsch, ed.,Proceedings of the 19. Jahrestagung “Mathematische Optimierung” Sellin, GDR, 1987. Seminarbericht No. 90 (Humboldt-Universität Berlin, Berlin, 1987) pp. 77–86.

    Google Scholar 

  37. R. Lepp, “Discrete approximation of linear two-stage stochastic programming problem,”Numerical Functional Analysis and Optimization 9 (1987) 19–33.

    Google Scholar 

  38. K. Marti,Approximationen stochastischer Optimierungsprobleme (Anton Hain, Königstein, 1979).

    Google Scholar 

  39. P. Olsen, “Discretizations of multistage stochastic programming problems,”Mathematical Programming Study 6 (1976) 111–124.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  42. C. van de Panne and W. Popp, “Minimum cost cattle feed under probabilistic protein constraints,”Management Science 9 (1963) 405–430.

    Google Scholar 

  43. S.M. Robinson, “Stability theory for systems of inequalities, part I: Linear systems,”SIAM Journal on Numerical Analysis 12 (1975) 754–769.

    Google Scholar 

  44. S.M. Robinson, “Generalized equations and their solutions, part II: Applications to nonlinear programming,”Mathematical Programming Study 19 (1982) 200–221.

    Google Scholar 

  45. S.M. Robinson, “Local epi-continuity and local optimization,”Mathematical Programming 37 (1987) 208–223.

    Google Scholar 

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

    Google Scholar 

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

    Google Scholar 

  48. R.T. Rockafellar and R. Wets, “A Lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming,”Mathematical Programming Study 28 (1986) 63–93.

    Google Scholar 

  49. W. Römisch and A. Wakolbinger, “Obtaining convergence rates for approximations in stochastic programming,” in: J. Guddat, H.Th. Jongen, B. Kummer and F. Nožička, eds.,Parametric Optimization and Related Topics. Proceedings of the International Conference in Plaue, GDR, 1985 (Akademie-Verlag, Berlin, 1987) pp. 327–343.

    Google Scholar 

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

    Google Scholar 

  51. F. Solis and R. Wets, “A statistical view of stochastic programming,” manuscript, University of Kentucky (Lexington, 1981).

    Google Scholar 

  52. S. Vogel, “Stability results for stochastic programming problems,”Optimization (formerly a series ofMathematische Operationsforschung und Statistik) 19 (1988) 269–288.

    Google Scholar 

  53. J. Wang, “Distribution sensitivity analysis for stochastic programs with complete recourse,”Mathematical Programming 31 (1985) 286–297.

    Google Scholar 

  54. J. Wang, “Lipschitz continuity of objective functions in stochastic programs with fixed recourse and its applications,”Mathematical Programming Study 27 (1986) 145–152.

    Google Scholar 

  55. R. Wets, “Stochastic programs with fixed recourse: the equivalent deterministic program,”SIAM Review 16 (1974) 309–339.

    Google Scholar 

  56. R. Wets, “A statistical approach to the solution of stochastic programs with (convex) simple recourse,” Technical Report, University of Kentucky (Lexington, 1979).

    Google Scholar 

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

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Sektion Mathematik, Humboldt-Universität Berlin, O-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. Distribution sensitivity in stochastic programming. Mathematical Programming 50, 197–226 (1991). https://doi.org/10.1007/BF01594935

Download citation

  • Received:

  • Revised:

  • Issue Date:

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

AMS 1980 Subject Classifications

Key words

Search

Navigation