IDEAS home Printed from https://ideas.repec.org/a/spr/jglopt/v75y2019i3d10.1007_s10898-019-00789-8.html
   My bibliography  Save this article

On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems

Author

Listed:
  • Bo Wen

    (Hebei University of Technology
    Harbin Institute of Technology)

  • Xiaoping Xue

    (Harbin Institute of Technology
    Harbin Institute of Technology)

Abstract

In this paper, we consider the proximal gradient algorithm with extrapolation for solving a class of convex nonsmooth minimization problems. We show that for a large class of extrapolation parameters including the extrapolation parameters chosen in FISTA (Beck and Teboulle in SIAM J Imaging Sci 2:183–202, 2009), the successive changes of iterates go to 0. Moreover, based on the Łojasiewicz inequality, we establish the global convergence of iterates generated by the proximal gradient algorithm with extrapolation with an additional assumption on the extrapolation coefficients. The assumption is general enough to allow the threshold of the extrapolation coefficients to be 1. In particular, we prove the length of the iterates is finite. Finally, we perform numerical experiments on the least squares problems with $$\ell _1$$ ℓ 1 regularization to illustrate our theoretical results.

Suggested Citation

  • Bo Wen & Xiaoping Xue, 2019. "On the convergence of the iterates of proximal gradient algorithm with extrapolation for convex nonsmooth minimization problems," Journal of Global Optimization, Springer, vol. 75(3), pages 767-787, November.
    • Handle: RePEc:spr:jglopt:v:75:y:2019:i:3:d:10.1007_s10898-019-00789-8
    DOI: 10.1007/s10898-019-00789-8
    as

    Download full text from publisher

    File URL: http://link.springer.com/10.1007/s10898-019-00789-8
    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/s10898-019-00789-8?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. Hédy Attouch & Jérôme Bolte & Patrick Redont & Antoine Soubeyran, 2010. "Proximal Alternating Minimization and Projection Methods for Nonconvex Problems: An Approach Based on the Kurdyka-Łojasiewicz Inequality," Mathematics of Operations Research, INFORMS, vol. 35(2), pages 438-457, May.
    2. NESTEROV, Yu., 2007. "Gradient methods for minimizing composite objective function," LIDAM Discussion Papers CORE 2007076, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    3. NESTEROV, Yu., 2005. "Smooth minimization of non-smooth functions," LIDAM Reprints CORE 1819, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    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. Zhili Ge & Zhongming Wu & Xin Zhang & Qin Ni, 2023. "An extrapolated proximal iteratively reweighted method for nonconvex composite optimization problems," Journal of Global Optimization, Springer, vol. 86(4), pages 821-844, August.

    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. Silvia Villa & Lorenzo Rosasco & Sofia Mosci & Alessandro Verri, 2014. "Proximal methods for the latent group lasso penalty," Computational Optimization and Applications, Springer, vol. 58(2), pages 381-407, June.
    2. Qihang Lin & Xi Chen & Javier Peña, 2014. "A sparsity preserving stochastic gradient methods for sparse regression," Computational Optimization and Applications, Springer, vol. 58(2), pages 455-482, June.
    3. Xiubo Liang & Guoqiang Wang & Bo Yu, 2022. "A reduced proximal-point homotopy method for large-scale non-convex BQP," Computational Optimization and Applications, Springer, vol. 81(2), pages 539-567, March.
    4. Renato D. C. Monteiro & Camilo Ortiz & Benar F. Svaiter, 2016. "An adaptive accelerated first-order method for convex optimization," Computational Optimization and Applications, Springer, vol. 64(1), pages 31-73, May.
    5. Guoqiang Wang & Bo Yu, 2019. "PAL-Hom method for QP and an application to LP," Computational Optimization and Applications, Springer, vol. 73(1), pages 311-352, May.
    6. Lingxue Zhang & Seyoung Kim, 2014. "Learning Gene Networks under SNP Perturbations Using eQTL Datasets," PLOS Computational Biology, Public Library of Science, vol. 10(2), pages 1-20, February.
    7. Majid Jahani & Naga Venkata C. Gudapati & Chenxin Ma & Rachael Tappenden & Martin Takáč, 2021. "Fast and safe: accelerated gradient methods with optimality certificates and underestimate sequences," Computational Optimization and Applications, Springer, vol. 79(2), pages 369-404, June.
    8. Le Thi Khanh Hien & Duy Nhat Phan & Nicolas Gillis, 2022. "Inertial alternating direction method of multipliers for non-convex non-smooth optimization," Computational Optimization and Applications, Springer, vol. 83(1), pages 247-285, September.
    9. Umberto Amato & Anestis Antoniadis & Italia De Feis & Irene Gijbels, 2021. "Penalised robust estimators for sparse and high-dimensional linear models," Statistical Methods & Applications, Springer;Società Italiana di Statistica, vol. 30(1), pages 1-48, March.
    10. Francesco Rinaldi & Damiano Zeffiro, 2023. "Avoiding bad steps in Frank-Wolfe variants," Computational Optimization and Applications, Springer, vol. 84(1), pages 225-264, January.
    11. Mingqiang Li & Congying Han & Ruxin Wang & Tiande Guo, 2017. "Shrinking gradient descent algorithms for total variation regularized image denoising," Computational Optimization and Applications, Springer, vol. 68(3), pages 643-660, December.
    12. Hansen, Christian & Liao, Yuan, 2019. "The Factor-Lasso And K-Step Bootstrap Approach For Inference In High-Dimensional Economic Applications," Econometric Theory, Cambridge University Press, vol. 35(3), pages 465-509, June.
    13. Kely D. V. Villacorta & Paulo R. Oliveira & Antoine Soubeyran, 2014. "A Trust-Region Method for Unconstrained Multiobjective Problems with Applications in Satisficing Processes," Journal of Optimization Theory and Applications, Springer, vol. 160(3), pages 865-889, March.
    14. Masaru Ito, 2016. "New results on subgradient methods for strongly convex optimization problems with a unified analysis," Computational Optimization and Applications, Springer, vol. 65(1), pages 127-172, September.
    15. TAYLOR, Adrien B. & HENDRICKX, Julien M. & François GLINEUR, 2016. "Exact worst-case performance of first-order methods for composite convex optimization," LIDAM Discussion Papers CORE 2016052, Université catholique de Louvain, Center for Operations Research and Econometrics (CORE).
    16. Bo Jiang & Tianyi Lin & Shiqian Ma & Shuzhong Zhang, 2019. "Structured nonconvex and nonsmooth optimization: algorithms and iteration complexity analysis," Computational Optimization and Applications, Springer, vol. 72(1), pages 115-157, January.
    17. Dimitris Bertsimas & Nishanth Mundru, 2021. "Sparse Convex Regression," INFORMS Journal on Computing, INFORMS, vol. 33(1), pages 262-279, January.
    18. Zehui Jia & Jieru Huang & Xingju Cai, 2021. "Proximal-like incremental aggregated gradient method with Bregman distance in weakly convex optimization problems," Journal of Global Optimization, Springer, vol. 80(4), pages 841-864, August.
    19. Glaydston Carvalho Bento & João Xavier Cruz Neto & Antoine Soubeyran & Valdinês Leite Sousa Júnior, 2016. "Dual Descent Methods as Tension Reduction Systems," Journal of Optimization Theory and Applications, Springer, vol. 171(1), pages 209-227, October.
    20. Bolte, Jérôme & Le, Tam & Pauwels, Edouard & Silveti-Falls, Antonio, 2022. "Nonsmooth Implicit Differentiation for Machine Learning and Optimization," TSE Working Papers 22-1314, Toulouse School of Economics (TSE).

    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:jglopt:v:75:y:2019:i:3:d:10.1007_s10898-019-00789-8. 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.