Abstract
Several exponential bounds are derived by means of the theory of large deviations for the convergence of approximate solutions of stochastic optimization problems. The basic results show that the solutions obtained by replacing the original distribution by an empirical distribution provides an effective tool for solving stochastic programming problems.
Similar content being viewed by others
References
H. Attouch, R. Lucchetti and R.J-B Wets, The topology of the ρ-Hausdorff distance, Ann. Mat. pura ed appl. 160 (1991) 303–320.
H. Attouch and R.J-B Wets, Quantitative stability of variational systems: I. The epigraphical distance, Trans. Amer. Math. Soc. 328 (1991) 695–729.
H. Attouch and R.J-B Wets, Epigraphical processes: laws of large numbers for random lsc functions, manuscript, University of California, Davis (1991), in: Séminaire d'Analyse Convexe, Montepellier (1990) pp. 13.1–13.29.
H. Attouch and R.J-B Wets, Quantitative stability of variational systems: II. A framework for nonlinear conditioning, SIAM J. Optim. (1992), to appear; IIASA Working Paper 88–9, Laxenburg, Austria.
G. Beer, Conjugate convex functions and the epi-distance topology, Proc. Amer. Math. Soc. 108 (1990) 117–126.
P. Billingsley,Convergence of Probability Measures (Wiley, New York, 1968).
J.-D. Deuschel and D.W. Stroock,Large Deviations (Academic Press, Boston, 1989).
N. Dunford and J. Schwartz,Linear Operators, Part I:General Theory (Interscience, New York, 1957).
J. Dupačová, Stochastic programming with incomplete information, Optimization 18 (1987) 507–532.
J. Dupačová and R.J-B Wets, Asymptotic behavior of statistical estimators and of optimal solutions for stochastic optimization problems, Ann. Statist. 16 (1988) 1517–1549.
Yu.M. Ermoliev, A.A. Gaivoronski and C. Nedeva, Stochastic optimization problems with incomplete information of distribution functions, SIAM J. Contr. Optim. 23 (1985) 696–716.
W. Hoeffding, Probability inequalities for sums of bounded random variables, J. Amer. Statist. Assoc. 58 (1963) 13–30.
P. Huber, Robust estimation of a location parameter, Ann. Math. Statist. 35 (1964) 73–101.
P. Kall, On approximations and stability in stochastic programming, in:Parametric Optimization and Related Topics, eds. J. Guddat, H. Jonge, B. Kummer and F. Nozicka (Akademie-Verlag, Berlin, 1987).
V. Kaňková, An approximate solution of a stochastic optimization problem, in:Trans. 8th Conf. on Information Theory, Statistical Decision Functions and Random Processes (Academia, Prague, 1978) pp. 349–353.
A.J. King and R.T. Rockafellar, Asymptotic theory for solutions in generalizedM-estimation and stochastic programming, Math. Oper. Res. 18 (1993) 148–162.
A.J. King and R.J-B Wets, Epi-consistency of convex stochastic programs, Stoch. and Stoch. Reports 34 (1990) 83–92.
L. Le Cam, On some asymptotic properties of maximum likelihood estimates and related Bayes estimates, University of California Publications in Statistics 1 (1953) 277–330.
R. Lucchetti and R.J-B Wets, Convergence of minima of integral functionals, with applications to optimal control and stochastic optimization, Statist. Dec. 11 (1993); IIASA WP-90-81.
S.M. Robinson and R.J-B Wets, Stability in two-stage stochastic programming, SIAM J. Control Optim. 25 (1987) 1409–1416.
R.T. Rockafellar and R.J-B Wets, Variational systems, an introduction, in:Multifunctions and Integrands: Stochastic Analysis, Approximation and Optimization, ed. G. Salinetti, Lecture Notes in Mathematics 1091 (Springer, Berlin, 1984) pp. 1–54.
R. Schultz, Strong convexity in stochastic programs with recourse, Techical Report no. 407, Humboldt University, Berlin (1992).
A. Shapiro, Asymptotic analysis of stochastic programs, Ann. Oper. Res. 30 (1991) 169–186.
A.B. Tsybakov, Error bounds for the methods of minimization of empiral risk, Probl. Inf. Transmission 17 (1981) 50–61 (in Russian).
S. Vogel, Stability results for stochastic programming problems, Optimization 19 (1988) 269–288.
A. Wald, Note on the consistency of the maximum likelihood estimate, Ann. Math. Statist. 20 (1949) 595–601.
R.J-B Wets, Convergence of convex functions, variational inequalities and convex optimization problems, in:Variational Inequalities and Complementarity Problems, eds. R. Cottle, F. Giannessi and J.L. Lions (Wiley, Chichester, 1980) pp. 405–419.
R.J-B Wets, Constrained estimation: consistency and asymptotic, Appl. Stoch. Models Data Anal. 7 (1991) 17–32.
Author information
Authors and Affiliations
Additional information
Supported in part by a grant from the US-Israel Science Foundation.
Rights and permissions
About this article
Cite this article
Kaniovski, Y.M., King, A.J. & Wets, R.JB. Probabilistic bounds (via large deviations) for the solutions of stochastic programming problems. Ann Oper Res 56, 189–208 (1995). https://doi.org/10.1007/BF02031707
Issue Date:
DOI: https://doi.org/10.1007/BF02031707