IDEAS home Printed from https://ideas.repec.org/a/spr/coopap/v73y2019i1d10.1007_s10589-019-00071-3.html
   My bibliography  Save this article

Fast bundle-level methods for unconstrained and ball-constrained convex optimization

Author

Listed:
  • Yunmei Chen

    (University of Florida)

  • Guanghui Lan

    (Georgia Institute of Technology)

  • Yuyuan Ouyang

    (Clemson University)

  • Wei Zhang

    (University of Florida)

Abstract

In this paper, we study a special class of first-order methods, namely bundle-level (BL) type methods, which can utilize historical first-order information through cutting plane models to accelerate the solutions in practice. Recently, it has been shown in Lan (149(1–2):1–45, 2015) that an accelerated prox-level (APL) method and its variant, the uniform smoothing level (USL) method, have optimal iteration complexity for solving black-box and structured convex programming (CP) problems without requiring input of any smoothness information. However, these algorithms require the assumption on the boundedness of the feasible set and their efficiency relies on the solutions of two involved subproblems. Some other variants of BL methods which could handle unbounded feasible set have no iteration complexity provided. In this work we develop the fast APL (FAPL) method and fast USL (FUSL) method that can significantly improve the practical performance of the APL and USL methods in terms of both computational time and solution quality. Both FAPL and FUSL enjoy the same optimal iteration complexity as APL and USL, while the number of subproblems in each iteration is reduced from two to one, and an exact method is presented to solve the only subproblem in these algorithms. Furthermore, we introduce a generic algorithmic framework to solve unconstrained CP problems through solutions to a series of ball-constrained CP problems that also exhibits optimal iteration complexity. Our numerical results on solving some large-scale least squares problems and total variation based image reconstructions have shown advantages of these new BL type methods over APL, USL, and some other first-order methods.

Suggested Citation

  • Yunmei Chen & Guanghui Lan & Yuyuan Ouyang & Wei Zhang, 2019. "Fast bundle-level methods for unconstrained and ball-constrained convex optimization," Computational Optimization and Applications, Springer, vol. 73(1), pages 159-199, May.
    • Handle: RePEc:spr:coopap:v:73:y:2019:i:1:d:10.1007_s10589-019-00071-3
    DOI: 10.1007/s10589-019-00071-3
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10589-019-00071-3
    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-019-00071-3?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. Wim Ackooij & Welington Oliveira, 2014. "Level bundle methods for constrained convex optimization with various oracles," Computational Optimization and Applications, Springer, vol. 57(3), pages 555-597, April.
    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. Chunming Tang & Bo He & Zhenzhen Wang, 2020. "Modified Accelerated Bundle-Level Methods and Their Application in Two-Stage Stochastic Programming," Mathematics, MDPI, vol. 8(2), pages 1-26, February.
    2. Yunmei Chen & Xiaojing Ye & Wei Zhang, 2020. "Acceleration techniques for level bundle methods in weakly smooth convex constrained optimization," Computational Optimization and Applications, Springer, vol. 77(2), pages 411-432, November.
    3. Tang, Chunming & Liu, Shuai & Jian, Jinbao & Ou, Xiaomei, 2020. "A multi-step doubly stabilized bundle method for nonsmooth convex optimization," Applied Mathematics and Computation, Elsevier, vol. 376(C).

    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. Wim van Ackooij & Welington de Oliveira & Yongjia Song, 2018. "Adaptive Partition-Based Level Decomposition Methods for Solving Two-Stage Stochastic Programs with Fixed Recourse," INFORMS Journal on Computing, INFORMS, vol. 30(1), pages 57-70, February.
    2. Welington Oliveira, 2019. "Proximal bundle methods for nonsmooth DC programming," Journal of Global Optimization, Springer, vol. 75(2), pages 523-563, October.
    3. Murwan Siddig & Yongjia Song, 2022. "Adaptive partition-based SDDP algorithms for multistage stochastic linear programming with fixed recourse," Computational Optimization and Applications, Springer, vol. 81(1), pages 201-250, January.
    4. Yunmei Chen & Xiaojing Ye & Wei Zhang, 2020. "Acceleration techniques for level bundle methods in weakly smooth convex constrained optimization," Computational Optimization and Applications, Springer, vol. 77(2), pages 411-432, November.
    5. W. Ackooij & S. Demassey & P. Javal & H. Morais & W. Oliveira & B. Swaminathan, 2021. "A bundle method for nonsmooth DC programming with application to chance-constrained problems," Computational Optimization and Applications, Springer, vol. 78(2), pages 451-490, March.
    6. Butyn, Emerson & Karas, Elizabeth W. & de Oliveira, Welington, 2022. "A derivative-free trust-region algorithm with copula-based models for probability maximization problems," European Journal of Operational Research, Elsevier, vol. 298(1), pages 59-75.
    7. Wim Ackooij & Welington Oliveira & Yongjia Song, 2019. "On level regularization with normal solutions in decomposition methods for multistage stochastic programming problems," Computational Optimization and Applications, Springer, vol. 74(1), pages 1-42, September.
    8. Wim Ackooij, 2017. "A comparison of four approaches from stochastic programming for large-scale unit-commitment," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(1), pages 119-147, March.
    9. Martina Kuchlbauer & Frauke Liers & Michael Stingl, 2022. "Outer Approximation for Mixed-Integer Nonlinear Robust Optimization," Journal of Optimization Theory and Applications, Springer, vol. 195(3), pages 1056-1086, December.
    10. Tang, Chunming & Liu, Shuai & Jian, Jinbao & Ou, Xiaomei, 2020. "A multi-step doubly stabilized bundle method for nonsmooth convex optimization," Applied Mathematics and Computation, Elsevier, vol. 376(C).
    11. Blanchot, Xavier & Clautiaux, François & Detienne, Boris & Froger, Aurélien & Ruiz, Manuel, 2023. "The Benders by batch algorithm: Design and stabilization of an enhanced algorithm to solve multicut Benders reformulation of two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 309(1), pages 202-216.
    12. Byun, Ji-Eun & de Oliveira, Welington & Royset, Johannes O., 2023. "S-BORM: Reliability-based optimization of general systems using buffered optimization and reliability method," Reliability Engineering and System Safety, Elsevier, vol. 236(C).
    13. Álvaro Lorca & X. Andy Sun & Eugene Litvinov & Tongxin Zheng, 2016. "Multistage Adaptive Robust Optimization for the Unit Commitment Problem," Operations Research, INFORMS, vol. 64(1), pages 32-51, February.
    14. N. Hoseini Monjezi & S. Nobakhtian, 2022. "An inexact multiple proximal bundle algorithm for nonsmooth nonconvex multiobjective optimization problems," Annals of Operations Research, Springer, vol. 311(2), pages 1123-1154, April.
    15. Wim Ackooij & Nicolas Lebbe & Jérôme Malick, 2017. "Regularized decomposition of large scale block-structured robust optimization problems," Computational Management Science, Springer, vol. 14(3), pages 393-421, July.
    16. Tiago Andrade & Nikita Belyak & Andrew Eberhard & Silvio Hamacher & Fabricio Oliveira, 2022. "The p-Lagrangian relaxation for separable nonconvex MIQCQP problems," Journal of Global Optimization, Springer, vol. 84(1), pages 43-76, September.
    17. Mínguez, R. & van Ackooij, W. & García-Bertrand, R., 2021. "Constraint generation for risk averse two-stage stochastic programs," European Journal of Operational Research, Elsevier, vol. 288(1), pages 194-206.
    18. Babak Saleck Pay & Yongjia Song, 2020. "Partition-based decomposition algorithms for two-stage Stochastic integer programs with continuous recourse," Annals of Operations Research, Springer, vol. 284(2), pages 583-604, January.
    19. Jérôme Malick & Welington Oliveira & Sofia Zaourar, 2017. "Uncontrolled inexact information within bundle methods," EURO Journal on Computational Optimization, Springer;EURO - The Association of European Operational Research Societies, vol. 5(1), pages 5-29, March.
    20. Wim Ackooij, 2014. "Decomposition approaches for block-structured chance-constrained programs with application to hydro-thermal unit commitment," Mathematical Methods of Operations Research, Springer;Gesellschaft für Operations Research (GOR);Nederlands Genootschap voor Besliskunde (NGB), vol. 80(3), pages 227-253, December.

    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:73:y:2019:i:1:d:10.1007_s10589-019-00071-3. 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.