IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v76y2020i3d10.1007_s10589-020-00196-w.html
   My bibliography  Save this article

Inexact restoration with subsampled trust-region methods for finite-sum minimization

Author

Listed:
  • Stefania Bellavia

    (Università degli Studi di Firenze)

  • Nataša Krejić

    (University of Novi Sad)

  • Benedetta Morini

    (Università degli Studi di Firenze)

Abstract

Convex and nonconvex finite-sum minimization arises in many scientific computing and machine learning applications. Recently, first-order and second-order methods where objective functions, gradients and Hessians are approximated by randomly sampling components of the sum have received great attention. We propose a new trust-region method which employs suitable approximations of the objective function, gradient and Hessian built via random subsampling techniques. The choice of the sample size is deterministic and ruled by the inexact restoration approach. We discuss local and global properties for finding approximate first- and second-order optimal points and function evaluation complexity results. Numerical experience shows that the new procedure is more efficient, in terms of overall computational cost, than the standard trust-region scheme with subsampled Hessians.

Suggested Citation

  • 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.
    • Handle: RePEc:spr:coopap:v:76:y:2020:i:3:d:10.1007_s10589-020-00196-w
    DOI: 10.1007/s10589-020-00196-w
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-020-00196-w
    File Function: Abstract
    Download Restriction: Access to the full text of the articles in this series is restricted.
    File URL: https://libkey.io/10.1007/s10589-020-00196-w?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. Bastin, Fabian & Cirillo, Cinzia & Toint, Philippe L., 2006. "Application of an adaptive Monte Carlo algorithm to mixed logit estimation," Transportation Research Part B: Methodological, Elsevier, vol. 40(7), pages 577-593, August.
    2. 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.
    3. 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.
    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. Stefania Bellavia & Nataša Krejić & Benedetta Morini & Simone Rebegoldi, 2023. "A stochastic first-order trust-region method with inexact restoration for finite-sum minimization," Computational Optimization and Applications, Springer, vol. 84(1), pages 53-84, January.
    2. Ernesto G. Birgin, 2020. "Preface of the special issue dedicated to the XII Brazilian workshop on continuous optimization," Computational Optimization and Applications, Springer, vol. 76(3), pages 615-619, July.

    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. 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.
    2. 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.
    3. Carolina Osorio & Michel Bierlaire, 2013. "A Simulation-Based Optimization Framework for Urban Transportation Problems," Operations Research, INFORMS, vol. 61(6), pages 1333-1345, December.
    4. Johannes O. Royset & Roberto Szechtman, 2013. "Optimal Budget Allocation for Sample Average Approximation," Operations Research, INFORMS, vol. 61(3), pages 762-776, June.
    5. 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.
    6. Wang, Honggang, 2012. "Retrospective optimization of mixed-integer stochastic systems using dynamic simplex linear interpolation," European Journal of Operational Research, Elsevier, vol. 217(1), pages 141-148.
    7. J. O. Royset & E. Y. Pee, 2012. "Rate of Convergence Analysis of Discretization and Smoothing Algorithms for Semiinfinite Minimax Problems," Journal of Optimization Theory and Applications, Springer, vol. 155(3), pages 855-882, December.
    8. Jeffrey Larson & Stephen C. Billups, 2016. "Stochastic derivative-free optimization using a trust region framework," Computational Optimization and Applications, Springer, vol. 64(3), pages 619-645, July.
    9. Wang, Xinchang, 2016. "Optimal allocation of limited and random network resources to discrete stochastic demands for standardized cargo transportation networks," Transportation Research Part B: Methodological, Elsevier, vol. 91(C), pages 310-331.
    10. 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.
    11. Xiang He & Xiqun (Michael) Chen & Chenfeng Xiong & Zheng Zhu & Lei Zhang, 2017. "Optimal Time-Varying Pricing for Toll Roads Under Multiple Objectives: A Simulation-Based Optimization Approach," Transportation Science, INFORMS, vol. 51(2), pages 412-426, May.
    12. Cinzia Cirillo & Renting Xu & Fabian Bastin, 2016. "A Dynamic Formulation for Car Ownership Modeling," Transportation Science, INFORMS, vol. 50(1), pages 322-335, February.
    13. Anand Deo & Karthyek Murthy, 2023. "Importance Sampling for Minimization of Tail Risks: A Tutorial," Papers 2307.04676, arXiv.org.
    14. Akar, Gulsah & Clifton, Kelly J. & Doherty, Sean T., 2012. "Redefining activity types: Who participates in which leisure activity?," Transportation Research Part A: Policy and Practice, Elsevier, vol. 46(8), pages 1194-1204.
    15. Piergiacomo Sabino, 2011. "Implementing quasi-Monte Carlo simulations with linear transformations," Computational Management Science, Springer, vol. 8(1), pages 51-74, April.
    16. Gulsah Akar & Kelly Clifton & Sean Doherty, 2011. "Discretionary activity location choice: in-home or out-of-home?," Transportation, Springer, vol. 38(1), pages 101-122, January.
    17. 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.
    18. Honggang Wang, 2017. "Subspace dynamic‐simplex linear interpolation search for mixed‐integer black‐box optimization problems," Naval Research Logistics (NRL), John Wiley & Sons, vol. 64(4), pages 305-322, June.
    19. 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.
    20. Tsai, Shing Chih & Zheng, Ya-Xin, 2013. "A simulation optimization approach for a two-echelon inventory system with service level constraints," European Journal of Operational Research, Elsevier, vol. 229(2), pages 364-374.

    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:coopap:v:76:y:2020:i:3:d:10.1007_s10589-020-00196-w. 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.