Abstract
This paper considers a procedure of two-stage stochastic programming in which the performance function to be optimized is replaced by its empirical mean. This procedure converts a stochastic optimization problem into a deterministic one for which many methods are available. Another strength of the method is that there is essentially no requirement on the distribution of the random variables involved. Exponential convergence for the probability of deviation of the empirical optimum from the true optimum is established using large deviation techniques. Explicit bounds on the convergence rates are obtained for the case of quadratic performance functions. Finally, numerical results are presented for the famous news vendor problem, which lends experimental evidence supporting exponential convergence.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
BIRGE, J. R., and LOUVEAUX, F., Introduction to Stochastic Programming, Springer Verlag, New York, NY, 1997.
KUSHNER, H. J., and CLARKE, D. S., Stochastic Approximation for Constrained and Unconstrained Systems, Springer Verlag, New York, NY, 1978.
MEKETON, M. S., Optimization in Simulation: A Survey of Recent Results, Proceedings of the 1987 Winter Simulation Conference, pp. 58-67, 1987.
KING, A. J., and ROCKAFELLAR, R. T., Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Programming, Mathematics of Operations Research, Vol. 18, pp. 148-163, 1993.
ROBINSON, S.M., Analysis of Sample-Path Optimization, Mathematics of Operations Research, Vol. 21, pp. 513-528, 1996.
HUBER, P. J., Robust Estimation of a Location Parameter, Annals of Mathematical Statistics, Vol. 35, pp. 73-101, 1964.
HUBER, P. J., The Behavior of Maximum Likelihood Estimates under Nonstandard Conditions, Proceedings of the 5th Berkeley Symposium on Mathematical Statistics, pp. 221-233, 1967.
DUPăCOVÁ, J., and WETS, R., Asymptotic Behavior of Statistical Estimators and of Optimal Solutions of Stochastic Optimization Problems, Annals of Statistics, Vol. 16, pp. 1517-1549, 1988.
SHAPIRO, A., Asymptotic Properties of Statistical Estimators in Stochastic Programming, Annals of Statistics, Vol. 17, pp. 841-858, 1989.
SHAPIRO, A., Asymptotic Analysis of Stochastic Programs, Annals of Operations Research, Vol. 30, pp. 169-186, 1991.
PLAMBECK, E. L., FU, B. R., ROBINSON, S. M., and SURI, R., Sample-Path Optimization of Convex Stochastic Functions, Mathematical Programming, Vol. 75, pp. 137-176, 1996.
KANKOVA, V., An Approximate Solution of a Stochastic Optimization Problem, Transactions of the 8th Conference on Information Theory, Statistical Decision Functions, and Random Processes, pp. 349-353, 1978.
KANIOVSKI, Y. M., KING, A. J., and WETS, R. J., Probabilistic Bounds for the Solutions of Stochastic Programming Problems, Annals of Operations Research, Vol. 56, pp. 189-208, 1995.
SHIRYAYEV, A. N., Probability, Springer Verlag, New York, NY, 1984.
CHERNOFF, H., A Measure of Asymptotic Efficiency for Tests of a Hypothesis Based on the Sum of Observations, Annals of Mathematical Statistics, Vol. 23, pp. 493-507, 1952.
DEMBO, A., and ZEITOUNI, O., Large Deviations Techniques, Jones and Bartlett, Boston, Massachusetts, 1993.
BUCKLEW, J. A., Large Deviation Techniques in Decision, Simulation, and Estimation, John Wiley, New York, NY, 1990.
Author information
Authors and Affiliations
Rights and permissions
About this article
Cite this article
Dai, L., Chen, C.H. & Birge, J.R. Convergence Properties of Two-Stage Stochastic Programming. Journal of Optimization Theory and Applications 106, 489–509 (2000). https://doi.org/10.1023/A:1004649211111
Issue Date:
DOI: https://doi.org/10.1023/A:1004649211111