SpringerLink
Log in

A semi-Bregman proximal alternating method for a class of nonconvex problems: local and global convergence analysis

  • Published:
Journal of Global Optimization Aims and scope Submit manuscript

Abstract

We focus on nonconvex and non-smooth block optimization problems, where the smooth coupling part of the objective does not satisfy a global/partial Lipschitz gradient continuity assumption. A general alternating minimization algorithm is proposed that combines two proximal-based steps, one classical and another with respect to the Bregman divergence. Combining different analytical techniques, we provide a complete analysis of the behavior—from global to local—of the algorithm, and show when the iterates converge globally to critical points with a locally linear rate for sufficiently regular (though not necessarily convex) objectives. Numerical experiments illustrate the theoretical findings.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
EUR 32.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or Ebook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price includes VAT (Thailand)

Instant access to the full article PDF.

Institutional subscriptions

Algorithm 1
Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

References

  1. Ahookhosh, M., Hien, L.T.K., Gillis, N., Patrinos, P.: Multi-block Bregman proximal alternating linearized minimization and its application to orthogonal nonnegative matrix factorization. Comput. Optim. Appl. 79(3), 681–715 (2021)

    Article  MathSciNet  Google Scholar 

  2. Auslender, A., Teboulle, M.: Interior gradient and proximal methods for convex and conic optimization. SIAM J. Optim. 16(3), 697–725 (2006)

    Article  MathSciNet  Google Scholar 

  3. Bauschke, H.H., Bolte, J., Teboulle, M.: A descent lemma beyond lipschitz gradient continuity: first-order methods revisited and applications. Math. Oper. Res. 42(2), 330–348 (2016)

    Article  MathSciNet  Google Scholar 

  4. Bërdëllima, A., Lauster, F., Luke, D.R.: \(\alpha \)-firmly nonexpansive operators on metric spaces. J. Fixed Point Theory Appl. 24, 14 (2022)

    Article  MathSciNet  Google Scholar 

  5. Bertsekas, D.P.: Nonlinear Programming. Athena Scientific, Belmont (1999)

    Google Scholar 

  6. Bolte, J., Daniilidis, A., Lewis, A.: The łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optim. 17(4), 1205–1223 (2006)

    Article  MathSciNet  Google Scholar 

  7. Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. 146(1–2), 459–494 (2014)

    Article  MathSciNet  Google Scholar 

  8. Bolte, J., Sabach, S., Teboulle, M., Vaisbourd, Y.: First order methods beyond convexity and Lipschitz gradient continuity with applications to quadratic inverse problems. SIAM J. Optim. 28(3), 2131–2151 (2018)

    Article  MathSciNet  Google Scholar 

  9. Bregman, L.M.: The relaxation method of finding the common point of convex sets and its application to the solution of problems in convex programming. USSR Comp. Math. Math. Phys. 7(3), 200–217 (1967)

    Article  MathSciNet  Google Scholar 

  10. Dontchev, A.L., Rockafellar, R.T.: Implicit Functions and Solution Mapp**s, 2nd edn. Springer-Verlag, New York (2014)

    Book  Google Scholar 

  11. Hesse, R., Luke, D.R., Sabach, S., Tam, M.: The proximal heterogeneous block implicit-explicit method and application to blind ptychographic imaging. SIAM J. Imaging Sci. 8(1), 426–457 (2015)

    Article  MathSciNet  Google Scholar 

  12. Kruger, A.Y., Luke, D.R., Thao, N.H.: Set regularities and feasibility problems. Math. Program. 168(1–2), 279–311 (2018)

    Article  MathSciNet  Google Scholar 

  13. Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. Inst. Fourier (Grenoble) 48(3), 769–783 (1998)

    Article  MathSciNet  Google Scholar 

  14. Łojasiewicz, S.: Une propriété topologique des sous-ensembles analytiques réels. In Les Équations aux Dérivées Partielles (Paris, 1962), pages 87–89. Éditions du Centre National de la Recherche Scientifique, Paris, (1963)

  15. Luke, D.R.: ProxToolbox, https://gitlab.gwdg.de/nam/ProxPython. (2017)

  16. Luke, D.R., Martins, A.-L.: Convergence analysis of the relaxed Douglas–Rachford algorithm. SIAM J. Opt. 30(1), 542–584 (2020)

    Article  MathSciNet  Google Scholar 

  17. Luke, D.R., Teboulle, M., Thao, N.H.: Necessary conditions for linear convergence of iterated expansive, set-valued map**s. Math. Program. 180, 1–31 (2018)

    Article  MathSciNet  Google Scholar 

  18. Luke, D.R., Thao, N.H., Tam, M.K.: Quantitative convergence analysis of iterated expansive, set-valued map**s. Math. Oper. Res. 43(4), 1143–1176 (2018)

    Article  MathSciNet  Google Scholar 

  19. Minty, G.J.: Monotone (nonlinear) operators in Hilbert space. Duke Math. J. 29(3), 341–346 (1962)

    Article  MathSciNet  Google Scholar 

  20. Moreau, J.J.: Proximité et dualité dans un espace hilbertien. Bull. Soc. Math. France 93, 273–299 (1965)

    Article  MathSciNet  Google Scholar 

  21. Rockafellar, R.T., Wets, J.B.R.: Variational Analysis. Springer (2004)

  22. Teboulle, M.: A simplified view of first order methods for optimization. Math. Program. 170(1), 67–96 (2018)

    Article  MathSciNet  Google Scholar 

Download references

Author information

Authors and Affiliations

  1. School of Mathematical Sciences, Tel-Aviv University, 69978, Ramat-Aviv, Israel

    Eyal Cohen & Marc Teboulle

  2. Institut für Numerische und Angewandte Mathematik, Universität Göttingen, Lotzestr. 16–18, 37083, Göttingen, Germany

    D. Russell Luke & Titus Pinta

  3. Faculty of Data and Decision Sciences, Technion—Israel Institute of Technology, 3200003, Haifa, Israel

    Shoham Sabach

Authors
  1. Eyal Cohen
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. D. Russell Luke
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. Titus Pinta
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. Shoham Sabach
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. Marc Teboulle
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Shoham Sabach.

Additional information

Publisher's Note

Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.

All authors were supported in part by the Deutsche Forschungsgemeinschaft (DFG, German Research Foundation) Grant—LU 170211-1. Eyal Cohen: This research is also supported by a postdoctoral fellowship under ISF Grant 2619-20. Shoham Sabach: This research was partially supported by the Israel Science Foundation, under ISF Grant 2480-21. Marc Teboulle: This research was partially supported by the Israel Science Foundation,under ISF Grant 2619-20.

Rights and permissions

Springer Nature or its licensor (e.g. a society or other partner) holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Cohen, E., Luke, D.R., Pinta, T. et al. A semi-Bregman proximal alternating method for a class of nonconvex problems: local and global convergence analysis. J Glob Optim 89, 33–55 (2024). https://doi.org/10.1007/s10898-023-01334-4

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10898-023-01334-4

Keywords

Mathematics Subject Classification

Search

Navigation