Abstract
For two-stage stochastic programs with integrality constraints in the second stage, we study continuity properties of the expected recourse as a function both of the first-stage policy and the integrating probability measure.
Sufficient conditions for lower semicontinuity, continuity and Lipschitz continuity with respect to the first-stage policy are presented. Furthermore, joint continuity in the policy and the probability measure is established. This leads to conclusions on the stability of optimal values and optimal solutions to the two-stage stochastic program when subjecting the underlying probability measure to perturbations.
Similar content being viewed by others
References
B. Bank, J. Guddat, D. Klatte, B. Kummer and K. Tammer,Nonlinear Parametric Optimization (Akademie-Verlag, Berlin, 1982).
B. Bank and R. Mandel,Parametric Integer Optimization (Akademie-Verlag, Berlin, 1988).
C. Berge,Espaces Topologiques, Fonctions Multivoques (Dunod, Paris, 1959).
P. Billingsley,Convergence of Probability Measures (Wiley, New York, 1968).
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.
C.E. Blair and R.G. Jeroslow, “The value function of a mixed integer program: I,”Discrete Mathematics 19 (1977) 121–138.
C. Borell, “Convex set functions ind-space,”Periodica Mathematica Hungarica 6 (1975) 111–136.
R.M. Dudley,Real Analysis and Probability (Wadsworth & Brooks/Cole, Pacific Grove, 1989).
J. Dupačová, “Stochastic programming with incomplete information: A survey of results on postoptimization and sensitivity analysis,”Optimization 18 (1987) 507–532.
P. Gänssler and W. Stute,Wahrscheinlichkeitstheorie (Springer, Berlin, 1977).
P. Kall,Stochastic Linear Programming (Springer, Berlin, 1976).
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 (Akademie Verlag, Berlin, 1987) pp. 387–407.
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.
D. Klatte, “A note on quantitative stability results in nonlinear optimization,” in: K. Lommatzsch, ed.,Proceedings of the 19. Jahrestagung Mathematische Optimierung, Seminarbericht Nr. 90, Sektion Mathematik, Humboldt-Universität Berlin (1987) pp. 77–86.
W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, “Stochastic integer programming with simple recourse,” Research Memorandum 455, Institute of Economic Research, University of Groningen (1991).
W.K. Klein Haneveld, L. Stougie and M.H. van der Vlerk, “On the convex hull of the simple integer recourse objective function,” Research Memorandum 516, Institute of Economic Research, University of Groningen (1993).
W.K. Klein Haneveld and M.H. van der Vlerk, “On the expected value function of a simple integer recourse problem with random technology matrix,”Journal of Computational and Applied Mathematics 56 (1994) 45–53.
G. Laporte and F.V. Louveaux, “The integer L-shaped method for stochastic integer programs with complete recourse,”Operations Research Letters 13 (1993) 133–142.
F.V. Louveaux and M.H. van der Vlerk, “Stochastic programs with simple integer recourse,”Mathematical Programming 61 (1993) 301–326.
G.L. Nemhauser and L.A. Wolsey,Integer and Combinatorial Optimization (Wiley, New York, 1988).
S.T. Rachev,Probability Metrics and the Stability of Stochastic Models (Wiley, New York, 1991).
A. Rinnooy Kan and L. Stougie, “Stochastic integer programming,” in: Y. Ermoliev and R. Wets, eds.,Numerical Techniques for Stochastic Optimization (Springer, Berlin, 1988) pp. 201–213.
S.M. Robinson, “Local epi-continuity and local optimization,”Mathematical Programming 37 (1987) 208–222.
S.M. Robinson and R. Wets, “Stability in two-stage stochastic programming,”SIAM Journal on Control and Optimization 25 (1987) 1409–1416.
W. Römisch and R. Schultz, “Distribution sensitivity in stochastic programming,”Mathematical Programming 50 (1991) 197–226.
W. Römisch and R. Schultz, “Stability analysis for stochastic programs,”Annals of Operations Research 30 (1991) 241–266.
R. Schultz, “Continuity and stability in two-stage stochastic integer programming,” in: K. Marti, ed.,Stochastic Optimization, Numerical Methods and Technical Applications, Lecture Notes in Economics and Mathematical Systems 379 (Springer, New York, 1992) pp. 81–92.
R. Schultz, “Continuity properties of expectation functions in stochastic integer programming,”Mathematics of Operations Research 18 (1993) 578–589.
A. Shapiro, “Quantitative stability in stochastic programming,”Mathematical Programming 67 (1994) 99–108.
L. Stougie, “Design and analysis of algorithms for stochastic integer programming,” Ph.D. Thesis, Center for Mathematics and Computer Science, Amsterdam (1985).
R. Wets, “Stochastic programs with fixed recourse: the equivalent deterministic program,”SIAM Review 16 (1974) 309–339.
Author information
Authors and Affiliations
Additional information
This research is supported by the Schwerpunktprogramm “Anwendungsbezogene Optimierung und Steuerung” of the Deutsche Forschungsgemeinschaft.
The main part of the paper was written while the author was an assistant at the Department of Mathematics at Humboldt University Berlin.
Rights and permissions
About this article
Cite this article
Schultz, R. On structure and stability in stochastic programs with random technology matrix and complete integer recourse. Mathematical Programming 70, 73–89 (1995). https://doi.org/10.1007/BF01585929
Received:
Revised:
Issue Date:
DOI: https://doi.org/10.1007/BF01585929