Abstract
Stability and sensitivity studies for stochastic programs have been motivated by the problem of incomplete information about the true probability measure through which the stochastic program is formulated and in connection with the development and evaluation of algorithms. The first part of this survey paper briefly introduces and compares different approaches and points out the contemporary efforts to remove and weaken assumptions that are not realistic (e.g., strict complementarity conditions). The second part surveys recent results on qualitative and quantitative stability with respect to the underlying probability measure and describes the ways and means of statistical sensitivity analysis based on Gâteaux derivatives. The last section comments on parallel statistical sensitivity results obtained in the parametric case, i.e., for probability measures belonging to a parametric family indexed by a finite dimensional vector parameter.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
R.L. Armacost and A.V. Fiacco, Computational experience in sensitivity analysis for nonlinear programming, Math. Programming 6 (1974) 301–326.
H. Attouch and R.J.-B. Wets, Epigraphical approach, Annales Institut H. Poincaré, Analyse Non Linéaire (1989).
J.-P. Aubin, Lipschitz behavior of solutions to convex minimization problems, Math. Oper. Res. 9 (1984) 87–111.
B. Bank et al.,Non-Linear Parametric Optimization (Akademie-Verlag, Berlin, 1982).
B.M. Beale, On minimizing a convex function subject to linear inequalities, JRSS 17B (1955) 173–184.
J.R. Birge and R.J.-B. Wets, Computing bounds for stochastic programming problems by means of a generalized moment problem, Math. Oper. Res. 12 (1987) 149–162.
A. Charnes and W.W. Cooper, Chance-constrained programming, Manag. Sci. 5 (1959) 73–79.
J.M. Danskin,Theory of Max-Min, Econometrics and Operations Research, vol. 5 (Springer, 1967).
G.B. Dantzig, Linear programming under uncertainty, Manag. Sci. 1 (1955) 197–206.
G.B. Dantzig and P.W. Glynn, Parallel processors for planning under uncertainty,5th Int. Conf. on Stochastic Programming, Ann Arbor (August 13–18, 1989).
J. Dupačová, Experience in stochastical programming models, in: A. Prékopa (ed.),Survey of Mathematical Programming, Proc. 9th Int. Mathematical Programming Symp., Budapest 1976 (Akadémiai Kiado, Budapest, 1979) pp. 99–105.
J. Dupačová, Stability in stochastic programming with recourse-estimated parameters, Math. Programming 28 (1984) 72–83.
J. Dupačová, Stability in stochastic programming with recourse-contaminated distributions, Math. Programming Study 27 (1986) 133–144.
J. Dupačová, Stochastic programming with incomplete information: A survey of results on postoptimization and sensitivity analysis, Optimization 18 (1987) 507–532.
J. Dupačová, On some connections between parametric and stochastic programming, in: J. Guddat et al. (eds.),Parametric Optimization and Related Topics, Mathematical Research Band 35 (Akademie-Verlag, Berlin, 1987) pp. 74–81.
J. Dupačová, On nonnormal asymptotic behavior of optimal solutions of stochastic programming problems: The parametric case, in: P. Mandl and M. Hušková (eds.),Proc. 4th Prague Symp. on Asymptotic Statistics, Charles University, Prague (1989) pp. 205–214. See also WP-88-19 IIASA, Laxenburg.
J. Dupačová, On statistical sensitivity analysis in stochastic programming,5th Int. Conf. on Stochastic Programming, Ann Arbor (August 13–18, 1989).
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.
Yu. Ermoliev and R.J.-B. Wets (eds.),Numerical Techniques for Stochastic Optimization Problems (Springer, Berlin, 1988).
A.V. Fiacco, Sensitivity analysis for nonlinear programming using penalty methods, Math. Programming 10 (1976) 287–311.
A.V. Fiacco,Introduction to Sensitivity and Stability Analysis in Nonlinear Programming (Academic Press, New York, 1983).
A.V. Fiacco and J. Kyparisis, Sensitivity analysis in nonlinear programming under second order assumptions, in: A.V. Balakrishnan and M. Tona (eds.),Systems and Optimization, Lecture Notes in Control and Information Sciences 66 (Springer, Berlin, 1985) pp. 74–97.
A.V. Fiacco and G.P. McCormick,Nonlinear Programming Sequential Unconstrained Minimization Techniques (Wiley, New York, 1968).
E.G. Gol'shtein,Vypukloje Programmirovanije, Elementy Teoriji (Nauka, Moscow, 1970) [Theory of Convex Programming, Translations of Mathematical Monographs 36; American Mathematical Society, Providence, RI (1972)].
F.R. Hampel, The influence curve and its role in robust estimation, J. Am. Statist. Assoc. 69 (1974) 383–397.
F.R. Hampel et al.,Robust Statistics. The Approach Based on Influence Functions (Wiley, New York, 1986).
P.J. Huber,Robust Statistics (Wiley, New York, 1981).
M. Iosifescu and R. Theodorescu, Sur la programmation linéaire, C.R. Acad. Sci. Paris 256 (1963) 4831–4833.
K. Jittorntrum, Solution point differentiability without strict complementarity in nonlinear programming, Math. Programming Study 21 (1984) 127–138.
P. Kall,Stochastic Linear Programming (Springer, Berlin, 1976).
P. Kall, Computational methods for solving two-stage stochastic linear programming problems, J. Appl. Math. Phys. 30 (1979) 261–271.
P. Kall, Approximation to optimization problems: An elementary review, Math. Oper. Res. 11 (1986) 9–18.
P. Kall, On approximations and stability in stochastic programming, in: J. Guddat et al. (eds.),Parametric Optimization and Related Topics, Math. Research Band 35 (Akademie-Verlag Berlin, 1987) pp. 387–407.
P. Kall, Stochastic programming with recourse: Upper bounds and moment problems, in: J. Guddat et al. (eds.),Advances in Mathematical Optimization, Mathematical Research vol. 45 (Akademie-Verlag, Berlin, 1988) pp. 86–103.
P. Kall and D. Stoyan, Solving stochastic programming problems with recourse including error bounds, Math. Oper. Forsch. Statist. Ser. Optimization 13 (1982) 431–447.
V. Kaňková, Optimum solution of a stochastic optimization problem with unknown parameters,Trans. 7th Prague Conf. 1974 (Academia, Prague, 1977) pp. 239–244.
V. Kaňková, An approximate solution of a stochastic optimization problem,Trans. 8th Prague Conf. 1978 (Academia, Prague, 1978) pp. 349–353.
V. Kaňková, Empirical estimates in stochastic programming,Trans. 10th Prague Conf. 1986 (Academia, Prague, 1988) pp. 21–28.
V. Kaňková, Estimates in stochastic programming — Chance constrained case, to appear in Problems of Control and Information Theory.
A.J. King, Asymptotic behaviour of solutions in stochastic optimization: Nonsmooth analysis and the derivation of non-normal limit distribution, Dissertation, Univ. of Washington (1986).
A.J. King, Generalized delta theorems for multivalued mappings and measurable selections, WP-88-56, IIASA, Laxenburg (1988), in Math. Oper. Res. (1989).
A.J. King, Asymptotic distributions for solutions in stochastic optimizaton and generalized M-estimation, WP-88-58, IIASA, Laxenburg (1988).
A.J. King and R.J.-B. Wets, Epi-consistency for convex stochastic programs, RC 14640 (# 65642) 5/26/89, IBM Research Division (1989).
D. Klatte, A note on quantitative stability results in nonlinear optimization, in: K. Lommatzsch (ed.),Proc. 19. Jahrestagung “Mathematische Optimierung”, Seminarbericht No. 90, Humboldt-Universität, Berlin (1987) pp. 77–86.
A. Prékopa, Logarithmic concave measures with application to stochastic programming, Acta Sci. Math. 32 (1971) 301–316.
S.M. Robinson, Perturbed Kuhn-Tucker points and rates of convergence for a class of nonlinear programming algorithms, Math. Programming 7 (1974) 1–16.
S.M. Robinson, Strongly regular generalized equations, Math. Oper. Res. 5 (1980) 43–62.
S.M. Robinson, Local structure of feasible sets in nonlinear programming, Part III: Stability and sensitivity, Math. Programming Study 30 (1986) 45–66.
S.M. Robinson, Local epi-continuity and local optimization, Math. Programming 37 (1987) 208–222.
S.M. Robinson and R.J.-B. Wets, Stability in two-stage stochastic programming, SIAM J. Control Optim. 25 (1988) 1409–1416.
R.T. Rockafellar, Directional differentiability of the optimal value function in a nonlinear programming problem, Math. Programming Study 21 (1984) 213–226.
R.T. Rockafellar, Proto-differentiability of set-valued mappings and its applications in optimization, Ann. Inst. H. Poincaré: Analyse Non Linéaire (1989).
R.T. Rockafellar and R.J.-B. Wets, A Lagrangian finite generation technique for solving linear-quadratic problems in stochastic programming, Math. Programming Study 28 (1986) 63–93.
W. Römisch and R. Schultz, Distribution sensitivity in stochastic programming, Preprint No. 160, Humboldt-Universität zu Berlin (1987), submitted to Math. Programming.
W. Römisch and R. Schultz, Stability of solutions for stochastic programs with complete recourse havingC 1,1 data. Inst. für Operations Research der Universität Zürich (1989).
W. Römisch and R. Schultz, Distribution sensitivity for the chance constrained model of optimal load dispatch (1989) submitted to J. Optim. Theory Appl.
W. Römisch and A. Walkobiner, Obtaining convergence rates for approximations in stochastic programming, in: J. Guddat et al. (eds.),Parametric Optimization and Related Topics, Mathematical Research Band 35 (Akademie-Verlag Berlin, 1987) pp. 327–343.
G. Salinetti and R.J.-B. Wets, On the convergence in distribution of measurable multifunctions (random sets), normal integrands, stochastic processes and stochastic infima, Math. Oper. Res. 11 (1986) 385–419.
R.J. Serfling,Approximation Theorems in Mathematical Statistics (Wiley, New York, 1980).
A. Shapiro, Second order sensitivity analysis and asymptotic theory of parametrized nonlinear programs, Math. Programming 33 (1985) 280–299.
A. Shapiro, Asymptotic properties of statistical estimators in stochastic programming, Research Report 55/87 (17), University of South Africa, Ann. Statist. 17 (1989) 841–858.
A. Shapiro, Sensitivity analysis of nonlinear programs and differentiability of metric projections, SIAM J. Control Optim. 26 (1988).
A. Shapiro, On differential stability in stochastic programming, Math. Programming (1990).
E. Tamm, On solvability of the nonlinear programming problem with a random parameter, ENSV TA Toimetised Füüsika Matemaatika 30 (1981) 220–224 (in Russian).
G. Tintner, Stochastic linear programming with applications to agricultural economics, in:Proc. 2nd Symp. on Linear Programming, Washington (1955) pp. 197–207.
A.B. Tsybakov, Error bounds for the method of minimization of empirical risk; transl. from Problemy Peredachi Informatsii 17 (1981) 50–61.
S. Vogel, Stability results for stochastic programming problems, Optimization 19 (1988) 269–288.
J. Wang, Distribution sensitivity analysis for stochastic programs with complete recourse, Math. Programming 31 (1985) 286–297.
J. Wang, Continuity of feasible solution sets of probabilistic constrained programs, submitted to J. Optim. Theory Appl.
R.J.-B. Wets, A statistical approach to the solution of stochastic programs with (convex) simple recourse, Working Paper, University of Kentucky (1979).
R.J.-B. Wets, Stochastic programming: Solution techniques and approximation schemes, in: A. Bachem et al. (eds.),Mathematical Programming — The State of the Art, Bonn, 1982 (Springer, Berlin, 1983) pp. 566–603.
R.J.-B. Wets, Stochastic programming, to appear in:Handbook on Operations Research.
J. Žáčková, On minimax solutions of stochastic linear programming problems, Čas. pěst. mat. 91 (1966) 423–430.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dupačová, J. Stability and sensitivity-analysis for stochastic programming. Ann Oper Res 27, 115–142 (1990). https://doi.org/10.1007/BF02055193
Issue Date:
DOI: https://doi.org/10.1007/BF02055193