IDEAS home Printed from https://ideas.repec.org/a/inm/oropre/v61y2013i3p762-776.html
   My bibliography  Save this article

Optimal Budget Allocation for Sample Average Approximation

Author

Listed:
  • Johannes O. Royset

    (Operations Research Department, Naval Postgraduate School, Monterey, California 93943)

  • Roberto Szechtman

    (Operations Research Department, Naval Postgraduate School, Monterey, California 93943)

Abstract

The sample average approximation approach to solving stochastic programs induces a sampling error, caused by replacing an expectation by a sample average, as well as an optimization error due to approximating the solution of the resulting sample average problem. We obtain estimators of an optimal solution and the optimal value of the original stochastic program after executing a finite number of iterations of an optimization algorithm applied to the sample average problem. We examine the convergence rate of the estimators as the computing budget tends to infinity, and we characterize the allocation policies that maximize the convergence rate in the case of sublinear, linear, and superlinear convergence regimes for the optimization algorithm.

Suggested Citation

  • Johannes O. Royset & Roberto Szechtman, 2013. "Optimal Budget Allocation for Sample Average Approximation," Operations Research, INFORMS, vol. 61(3), pages 762-776, June.
    • Handle: RePEc:inm:oropre:v:61:y:2013:i:3:p:762-776
    DOI: 10.1287/opre.2013.1163
    as

    Download full text from publisher

    File URL: http://dx.doi.org/10.1287/opre.2013.1163
    Download Restriction: no
    File URL: https://libkey.io/10.1287/opre.2013.1163?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
    ---><---

    References listed on IDEAS

    as
    1. Güzin Bayraksan & David P. Morton, 2011. "A Sequential Sampling Procedure for Stochastic Programming," Operations Research, INFORMS, vol. 59(4), pages 898-913, August.
    2. Raghu Pasupathy, 2010. "On Choosing Parameters in Retrospective-Approximation Algorithms for Stochastic Root Finding and Simulation Optimization," Operations Research, INFORMS, vol. 58(4-part-1), pages 889-901, August.
    3. Rockafellar, R.T. & Royset, J.O., 2010. "On buffered failure probability in design and optimization of structures," Reliability Engineering and System Safety, Elsevier, vol. 95(5), pages 499-510.
    4. Jeff Linderoth & Alexander Shapiro & Stephen Wright, 2006. "The empirical behavior of sampling methods for stochastic programming," Annals of Operations Research, Springer, vol. 142(1), pages 215-241, February.
    5. Fabian Bastin & Cinzia Cirillo & Philippe Toint, 2006. "An adaptive Monte Carlo algorithm for computing mixed logit estimators," Computational Management Science, Springer, vol. 3(1), pages 55-79, January.
    6. Alexander, S. & Coleman, T.F. & Li, Y., 2006. "Minimizing CVaR and VaR for a portfolio of derivatives," Journal of Banking & Finance, Elsevier, vol. 30(2), pages 583-605, February.
    7. Rockafellar, R. Tyrrell & Uryasev, Stanislav, 2002. "Conditional value-at-risk for general loss distributions," Journal of Banking & Finance, Elsevier, vol. 26(7), pages 1443-1471, July.
    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. Johannes O. Royset & Roger J-B Wets, 2016. "Optimality Functions and Lopsided Convergence," Journal of Optimization Theory and Applications, Springer, vol. 169(3), pages 965-983, June.
    2. Jamie Fairbrother & Amanda Turner & Stein W. Wallace, 2018. "Scenario Generation for Single-Period Portfolio Selection Problems with Tail Risk Measures: Coping with High Dimensions and Integer Variables," INFORMS Journal on Computing, INFORMS, vol. 30(3), pages 472-491, August.
    3. Suvrajeet Sen & Yifan Liu, 2016. "Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction," Operations Research, INFORMS, vol. 64(6), pages 1422-1437, December.
    4. Bismark Singh & David P. Morton & Surya Santoso, 2018. "An adaptive model with joint chance constraints for a hybrid wind-conventional generator system," Computational Management Science, Springer, vol. 15(3), pages 563-582, October.
    5. Kyle Cooper & Susan R. Hunter & Kalyani Nagaraj, 2020. "Biobjective Simulation Optimization on Integer Lattices Using the Epsilon-Constraint Method in a Retrospective Approximation Framework," INFORMS Journal on Computing, INFORMS, vol. 32(4), pages 1080-1100, October.
    6. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    7. Yunxiao Deng & Suvrajeet Sen, 2022. "Predictive stochastic programming," Computational Management Science, Springer, vol. 19(1), pages 65-98, January.

    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. Johannes Royset, 2013. "On sample size control in sample average approximations for solving smooth stochastic programs," Computational Optimization and Applications, Springer, vol. 55(2), pages 265-309, June.
    2. Emelogu, Adindu & Chowdhury, Sudipta & Marufuzzaman, Mohammad & Bian, Linkan & Eksioglu, Burak, 2016. "An enhanced sample average approximation method for stochastic optimization," International Journal of Production Economics, Elsevier, vol. 182(C), pages 230-252.
    3. Nataša Krejić & Nataša Krklec Jerinkić, 2019. "Spectral projected gradient method for stochastic optimization," Journal of Global Optimization, Springer, vol. 73(1), pages 59-81, January.
    4. L. Jeff Hong & Zhaolin Hu & Liwei Zhang, 2014. "Conditional Value-at-Risk Approximation to Value-at-Risk Constrained Programs: A Remedy via Monte Carlo," INFORMS Journal on Computing, INFORMS, vol. 26(2), pages 385-400, May.
    5. Suvrajeet Sen & Yifan Liu, 2016. "Mitigating Uncertainty via Compromise Decisions in Two-Stage Stochastic Linear Programming: Variance Reduction," Operations Research, INFORMS, vol. 64(6), pages 1422-1437, December.
    6. Cui, Xueting & Zhu, Shushang & Sun, Xiaoling & Li, Duan, 2013. "Nonlinear portfolio selection using approximate parametric Value-at-Risk," Journal of Banking & Finance, Elsevier, vol. 37(6), pages 2124-2139.
    7. Matthew Norton & Valentyn Khokhlov & Stan Uryasev, 2021. "Calculating CVaR and bPOE for common probability distributions with application to portfolio optimization and density estimation," Annals of Operations Research, Springer, vol. 299(1), pages 1281-1315, April.
    8. Ken Kobayashi & Yuichi Takano & Kazuhide Nakata, 2021. "Bilevel cutting-plane algorithm for cardinality-constrained mean-CVaR portfolio optimization," Journal of Global Optimization, Springer, vol. 81(2), pages 493-528, October.
    9. Xiaotie Chen & David L. Woodruff, 2024. "Distributions and bootstrap for data-based stochastic programming," Computational Management Science, Springer, vol. 21(1), pages 1-21, June.
    10. Löhndorf, Nils, 2016. "An empirical analysis of scenario generation methods for stochastic optimization," European Journal of Operational Research, Elsevier, vol. 255(1), pages 121-132.
    11. Stefania Bellavia & Nataša Krejić & Benedetta Morini, 2020. "Inexact restoration with subsampled trust-region methods for finite-sum minimization," Computational Optimization and Applications, Springer, vol. 76(3), pages 701-736, July.
    12. Hsieh, Chung-Chi & Lu, Yu-Ting, 2010. "Manufacturer's return policy in a two-stage supply chain with two risk-averse retailers and random demand," European Journal of Operational Research, Elsevier, vol. 207(1), pages 514-523, November.
    13. Fengmin Xu & Jieao Ma, 2023. "Intelligent option portfolio model with perspective of shadow price and risk-free profit," Financial Innovation, Springer;Southwestern University of Finance and Economics, vol. 9(1), pages 1-28, December.
    14. Soleimani, Hamed & Govindan, Kannan, 2014. "Reverse logistics network design and planning utilizing conditional value at risk," European Journal of Operational Research, Elsevier, vol. 237(2), pages 487-497.
    15. Mohd Azdi Maasar & Diana Roman & Paresh Date, 2022. "Risk minimisation using options and risky assets," Operational Research, Springer, vol. 22(1), pages 485-506, March.
    16. Yuichi Takano & Keisuke Nanjo & Noriyoshi Sukegawa & Shinji Mizuno, 2015. "Cutting plane algorithms for mean-CVaR portfolio optimization with nonconvex transaction costs," Computational Management Science, Springer, vol. 12(2), pages 319-340, April.
    17. E. G. Birgin & J. M. Martínez, 2016. "On the application of an Augmented Lagrangian algorithm to some portfolio problems," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 4(1), pages 79-92, February.
    18. Martin Šmíd & Václav Kozmík, 2024. "Approximation of multistage stochastic programming problems by smoothed quantization," Review of Managerial Science, Springer, vol. 18(7), pages 2079-2114, July.
    19. Mafusalov, Alexander & Uryasev, Stan, 2016. "CVaR (superquantile) norm: Stochastic case," European Journal of Operational Research, Elsevier, vol. 249(1), pages 200-208.
    20. Fernández, Arturo J., 2017. "Economic lot sampling inspection from defect counts with minimum conditional value-at-risk," European Journal of Operational Research, Elsevier, vol. 258(2), pages 573-580.

    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:inm:oropre:v:61:y:2013:i:3:p:762-776. 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: Chris Asher (email available below). General contact details of provider: https://edirc.repec.org/data/inforea.html .

    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.