IDEAS home Printed from https://ideas.repec.org/a/spr/joptap/v106y2000i3d10.1023_a1004649211111.html
   My bibliography  Save this article

Convergence Properties of Two-Stage Stochastic Programming

Author

Listed:
  • L. Dai

    (Genuity)

  • C. H. Chen

    (University of Pennsylvania)

  • J. R. Birge

    (Northwestern University)

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.

Suggested Citation

  • L. Dai & C. H. Chen & J. R. Birge, 2000. "Convergence Properties of Two-Stage Stochastic Programming," Journal of Optimization Theory and Applications, Springer, vol. 106(3), pages 489-509, September.
    • Handle: RePEc:spr:joptap:v:106:y:2000:i:3:d:10.1023_a:1004649211111
    DOI: 10.1023/A:1004649211111
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1023/A:1004649211111
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1023/A:1004649211111?utm_source=ideas
    LibKey link: if access is restricted and if your library uses this service, LibKey will redirect you to where you can use your library subscription to access this item
    ---><---

    As the access to this document is restricted, you may want to search for a different version of it.

    References listed on IDEAS

    as
    1. Stephen M. Robinson, 1996. "Analysis of Sample-Path Optimization," Mathematics of Operations Research, INFORMS, vol. 21(3), pages 513-528, August.
    2. Alan J. King & R. Tyrrell Rockafellar, 1993. "Asymptotic Theory for Solutions in Statistical Estimation and Stochastic Programming," Mathematics of Operations Research, INFORMS, vol. 18(1), pages 148-162, February.
    Full references (including those not matched with items on IDEAS)

    Citations

    Citations are extracted by the CitEc Project, subscribe to its RSS feed for this item.
    as


    Cited by:

    1. Maqsood, Imran & Huang, Guo H. & Scott Yeomans, Julian, 2005. "An interval-parameter fuzzy two-stage stochastic program for water resources management under uncertainty," European Journal of Operational Research, Elsevier, vol. 167(1), pages 208-225, November.
    2. Li, G.C. & Huang, G.H. & Lin, Q.G. & Zhang, X.D. & Tan, Q. & Chen, Y.M., 2011. "Development of a GHG-mitigation oriented inexact dynamic model for regional energy system management," Energy, Elsevier, vol. 36(5), pages 3388-3398.
    3. Jörg Fliege & Huifu Xu, 2011. "Stochastic Multiobjective Optimization: Sample Average Approximation and Applications," Journal of Optimization Theory and Applications, Springer, vol. 151(1), pages 135-162, October.
    4. Tahir Ekin & Nicholas G. Polson & Refik Soyer, 2014. "Augmented Markov Chain Monte Carlo Simulation for Two-Stage Stochastic Programs with Recourse," Decision Analysis, INFORMS, vol. 11(4), pages 250-264, December.
    5. Merve Bodur & James R. Luedtke, 2017. "Mixed-Integer Rounding Enhanced Benders Decomposition for Multiclass Service-System Staffing and Scheduling with Arrival Rate Uncertainty," Management Science, INFORMS, vol. 63(7), pages 2073-2091, July.
    6. Daniel Ralph & Huifu Xu, 2011. "Convergence of Stationary Points of Sample Average Two-Stage Stochastic Programs: A Generalized Equation Approach," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 568-592, August.
    7. L. Shao & X. Qin & Y. Xu, 2011. "A Conditional Value-at-Risk Based Inexact Water Allocation Model," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 25(9), pages 2125-2145, July.
    8. Lin, Q.G. & Huang, G.H., 2010. "An inexact two-stage stochastic energy systems planning model for managing greenhouse gas emission at a municipal level," Energy, Elsevier, vol. 35(5), pages 2270-2280.
    9. Huifu Xu & Dali Zhang, 2012. "Monte Carlo methods for mean-risk optimization and portfolio selection," Computational Management Science, Springer, vol. 9(1), pages 3-29, February.
    10. Yang, Xin & Chen, Anthony & Ning, Bin & Tang, Tao, 2016. "A stochastic model for the integrated optimization on metro timetable and speed profile with uncertain train mass," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 424-445.
    11. Zhenfang Liu & Yang Zhou & Gordon Huang & Bin Luo, 2019. "Risk Aversion Based Inexact Stochastic Dynamic Programming Approach for Water Resources Management Planning under Uncertainty," Sustainability, MDPI, vol. 11(24), pages 1-22, December.
    12. Özdemir, Deniz & Yücesan, Enver & Herer, Yale T., 2013. "Multi-location transshipment problem with capacitated production," European Journal of Operational Research, Elsevier, vol. 226(3), pages 425-435.
    13. Lin, Q.G. & Huang, G.H. & Bass, B. & Qin, X.S., 2009. "IFTEM: An interval-fuzzy two-stage stochastic optimization model for regional energy systems planning under uncertainty," Energy Policy, Elsevier, vol. 37(3), pages 868-878, March.
    14. Huifu Xu & Dali Zhang, 2013. "Stochastic Nash equilibrium problems: sample average approximation and applications," Computational Optimization and Applications, Springer, vol. 55(3), pages 597-645, July.
    15. Mingqiang Yin & Min Huang & Xiaohu Qian & Dazhi Wang & Xingwei Wang & Loo Hay Lee, 2023. "Fourth-party logistics network design with service time constraint under stochastic demand," Journal of Intelligent Manufacturing, Springer, vol. 34(3), pages 1203-1227, March.
    16. C. Li & L. Zhang, 2015. "An Inexact Two-Stage Allocation Model for Water Resources Management Under Uncertainty," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 29(6), pages 1823-1841, April.
    17. Vlasta Kaňková, 2013. "Risk Measures in Optimization Problems via Empirical Estimates," Czech Economic Review, Charles University Prague, Faculty of Social Sciences, Institute of Economic Studies, vol. 7(3), pages 162-177, November.
    18. ZhenFang Liu & GuoHe Huang, 2009. "Dual-Interval Two-Stage Optimization for Flood Management and Risk Analyses," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 23(11), pages 2141-2162, September.
    19. Hu, Jian & Bansal, Manish & Mehrotra, Sanjay, 2018. "Robust decision making using a general utility set," European Journal of Operational Research, Elsevier, vol. 269(2), pages 699-714.
    20. P. Guo & G. Huang & L. He & H. Zhu, 2009. "Interval-parameter Two-stage Stochastic Semi-infinite Programming: Application to Water Resources Management under Uncertainty," Water Resources Management: An International Journal, Published for the European Water Resources Association (EWRA), Springer;European Water Resources Association (EWRA), vol. 23(5), pages 1001-1023, March.
    21. John R. Birge, 2023. "Uses of Sub-sample Estimates to Reduce Errors in Stochastic Optimization Models," Papers 2310.07052, arXiv.org.
    22. Shane S. Drew & Tito Homem-de-Mello, 2012. "Some Large Deviations Results for Latin Hypercube Sampling," Methodology and Computing in Applied Probability, Springer, vol. 14(2), pages 203-232, June.

    Most related items

    These are the items that most often cite the same works as this one and are cited by the same works as this one.
    1. Daniel Ralph & Huifu Xu, 2011. "Convergence of Stationary Points of Sample Average Two-Stage Stochastic Programs: A Generalized Equation Approach," Mathematics of Operations Research, INFORMS, vol. 36(3), pages 568-592, August.
    2. Svetlozar T. Rachev & Werner Römisch, 2002. "Quantitative Stability in Stochastic Programming: The Method of Probability Metrics," Mathematics of Operations Research, INFORMS, vol. 27(4), pages 792-818, November.
    3. Xiaojun Chen & Masao Fukushima, 2005. "Expected Residual Minimization Method for Stochastic Linear Complementarity Problems," Mathematics of Operations Research, INFORMS, vol. 30(4), pages 1022-1038, November.
    4. Shane S. Drew & Tito Homem-de-Mello, 2012. "Some Large Deviations Results for Latin Hypercube Sampling," Methodology and Computing in Applied Probability, Springer, vol. 14(2), pages 203-232, June.
    5. Yongchao Liu & Huifu Xu & Jane J. Ye, 2011. "Penalized Sample Average Approximation Methods for Stochastic Mathematical Programs with Complementarity Constraints," Mathematics of Operations Research, INFORMS, vol. 36(4), pages 670-694, November.
    6. Baha Alzalg & Asma Gafour, 2023. "Convergence of a Weighted Barrier Algorithm for Stochastic Convex Quadratic Semidefinite Optimization," Journal of Optimization Theory and Applications, Springer, vol. 196(2), pages 490-515, February.
    7. Alfieri, Arianna & Matta, Andrea, 2012. "Mathematical programming formulations for approximate simulation of multistage production systems," European Journal of Operational Research, Elsevier, vol. 219(3), pages 773-783.
    8. Sun, Haoze & Weng, Chengguo & Zhang, Yi, 2017. "Optimal multivariate quota-share reinsurance: A nonparametric mean-CVaR framework," Insurance: Mathematics and Economics, Elsevier, vol. 72(C), pages 197-214.
    9. Arianna Alfieri & Andrea Matta & Giulia Pedrielli, 2015. "Mathematical programming models for joint simulation–optimization applied to closed queueing networks," Annals of Operations Research, Springer, vol. 231(1), pages 105-127, August.
    10. Özdemir, Deniz & Yücesan, Enver & Herer, Yale T., 2013. "Multi-location transshipment problem with capacitated production," European Journal of Operational Research, Elsevier, vol. 226(3), pages 425-435.
    11. Jörg Fliege & Huifu Xu, 2011. "Stochastic Multiobjective Optimization: Sample Average Approximation and Applications," Journal of Optimization Theory and Applications, Springer, vol. 151(1), pages 135-162, October.
    12. Qi Fan & Jiaqiao Hu, 2018. "Surrogate-Based Promising Area Search for Lipschitz Continuous Simulation Optimization," INFORMS Journal on Computing, INFORMS, vol. 30(4), pages 677-693, November.
    13. Flam, Sjur Didrik & Mirman, Leonard J., 1998. "Groping for optimal growth," Journal of Economic Dynamics and Control, Elsevier, vol. 23(2), pages 191-207, September.
    14. Raymond K.-M. Cheung & Warren B. Powell, 2000. "Shape -- A Stochastic Hybrid Approximation Procedure for Two-Stage Stochastic Programs," Operations Research, INFORMS, vol. 48(1), pages 73-79, February.
    15. Victor DeMiguel & Huifu Xu, 2009. "A Stochastic Multiple-Leader Stackelberg Model: Analysis, Computation, and Application," Operations Research, INFORMS, vol. 57(5), pages 1220-1235, October.
    16. Garcia, Diego, 2003. "Convergence and Biases of Monte Carlo estimates of American option prices using a parametric exercise rule," Journal of Economic Dynamics and Control, Elsevier, vol. 27(10), pages 1855-1879, August.
    17. Ilker Birbil, S. & Gürkan, G. & Listes, O.L., 2004. "Simulation-Based Solution of Stochastic Mathematical Programs with Complementarity Constraints : Sample-Path Analysis," Discussion Paper 2004-25, Tilburg University, Center for Economic Research.
    18. Gkiotsalitis, K. & Alesiani, F., 2019. "Robust timetable optimization for bus lines subject to resource and regulatory constraints," Transportation Research Part E: Logistics and Transportation Review, Elsevier, vol. 128(C), pages 30-51.
    19. Gürkan, G. & Ozge, A.Y. & Robinson, S.M., 1997. "Sample-path solution of stochastic variational inequalities," Discussion Paper 1997-87, Tilburg University, Center for Economic Research.
    20. Lin, Rung-Chuan & Sir, Mustafa Y. & Pasupathy, Kalyan S., 2013. "Multi-objective simulation optimization using data envelopment analysis and genetic algorithm: Specific application to determining optimal resource levels in surgical services," Omega, Elsevier, vol. 41(5), pages 881-892.

    Corrections

    All material on this site has been provided by the respective publishers and authors. You can help correct errors and omissions. When requesting a correction, please mention this item's handle: RePEc:spr:joptap:v:106:y:2000:i:3:d:10.1023_a:1004649211111. See general information about how to correct material in RePEc.

    If you have authored this item and are not yet registered with RePEc, we encourage you to do it here. This allows to link your profile to this item. It also allows you to accept potential citations to this item that we are uncertain about.

    If CitEc recognized a bibliographic reference but did not link an item in RePEc to it, you can help with this form .

    If you know of missing items citing this one, you can help us creating those links by adding the relevant references in the same way as above, for each refering item. If you are a registered author of this item, you may also want to check the "citations" tab in your RePEc Author Service profile, as there may be some citations waiting for confirmation.

    For technical questions regarding this item, or to correct its authors, title, abstract, bibliographic or download information, contact: Sonal Shukla or Springer Nature Abstracting and Indexing (email available below). General contact details of provider: http://www.springer.com .

    Please note that corrections may take a couple of weeks to filter through the various RePEc services.

    IDEAS is a RePEc service. RePEc uses bibliographic data supplied by the respective publishers.