close
Skip to main content
Springer Nature Link
Log in

An inertial forward–backward algorithm for the minimization of the sum of two nonconvex functions

  • Original Paper
  • Published:
Save article
View saved research
EURO Journal on Computational Optimization

Abstract

We propose a forward–backward proximal-type algorithm with inertial/memory effects for minimizing the sum of a nonsmooth function with a smooth one in the nonconvex setting. Every sequence of iterates generated by the algorithm converges to a critical point of the objective function provided an appropriate regularization of the objective satisfies the Kurdyka-Łojasiewicz inequality, which is for instance fulfilled for semi-algebraic functions. We illustrate the theoretical results by considering two numerical experiments: the first one concerns the ability of recovering the local optimal solutions of nonconvex optimization problems, while the second one refers to the restoration of a noisy blurred image.

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

Access this article

Log in via an institution
Fig. 1
Fig. 2
Fig. 3

Similar content being viewed by others

Explore related subjects

Discover the latest articles, books and news in related subjects, suggested using machine learning.

References

  • Alvarez F (2000) On the minimizing property of a second order dissipative system in Hilbert spaces. SIAM J Control Optim 38(4):1102–1119

    Article  Google Scholar 

  • Alvarez F (2004) Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space. SIAM J Optim 14(3):773–782

    Article  Google Scholar 

  • Alvarez F, Attouch H (2001) An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. Set Valued Anal 9:3–11

    Article  Google Scholar 

  • Attouch H, Bolte J (2009) On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math Program 116(1–2):5–16 Series B

    Article  Google Scholar 

  • Attouch H, Bolte J, Redont P, Soubeyran A (2010) Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math Operat Res 35(2):438–457

    Article  Google Scholar 

  • Attouch H, Bolte J, Svaiter BF (2013) Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math Program Ser A 137(1–2):91–129

    Article  Google Scholar 

  • Attouch H, Peypouquet J, Redont P (2014) A dynamical approach to an inertial forward-backward algorithm for convex minimization. SIAM J Optim 24(1):232–256

    Article  Google Scholar 

  • Bauschke HH, Combettes PL (2011) Convex analysis and monotone operator theory in hilbert spaces, CMS books in mathematics. Springer, New York

    Book  Google Scholar 

  • Beck A, Teboulle M (2009) A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imag Sci 2(1):183–202

    Article  Google Scholar 

  • Bertsekas DP (1999) Nonlinear programming, 2nd edn. Athena Scientific, Cambridge

    Google Scholar 

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

    Article  Google Scholar 

  • Bolte J, Daniilidis A, Lewis A, Shiota M (2007) Clarke subgradients of stratifiable functions. SIAM J Optim 18(2):556–572

    Article  Google Scholar 

  • Bolte J, Daniilidis A, Ley O, Mazet L (2010) Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Trans Am Math Soc 362(6):3319–3363

    Article  Google Scholar 

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

    Article  Google Scholar 

  • Boţ RI, Csetnek ER (2015) An inertial forward-backward-forward primal-dual splitting algorithm for solving monotone inclusion problems. Numer Algorithms. doi:10.1007/s11075-015-0007-5

  • Boţ RI, Csetnek ER (2015) An inertial alternating direction method of multipliers. Minimax Theory Appl, 1(1). arXiv:1404.4582

  • Boţ RI, Csetnek ER (2015) A hybrid proximal-extragradient algorithm with inertial effects. Numer Funct Anal Optim. 36(8):951–963

    Article  Google Scholar 

  • Boţ RI, Csetnek ER (2015) An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems. J Optim Theory Appl. doi:10.1007/s10957-015-0730-z

  • Boţ RI, Csetnek ER, Hendrich C (2015) Inertial Douglas-Rachford splitting for monotone inclusion problems. Appl Math Comput 256:472–487

    Article  Google Scholar 

  • Cabot A, Frankel P (2011) Asymptotics for some proximal-like method involving inertia and memory aspects. Set Valued Var Anal 19:59–74

    Article  Google Scholar 

  • Chan RH, Yang J, MA S (2014) Inertial primal-dual algorithms for structured convex optimization. arXiv:1409.2992v1

  • Chen C, Yang J, Ma S (2014) A general inertial proximal point method for mixed variational inequality problem. arXiv:1407.8238v2

  • Chouzenoux E, Pesquet J-C, Repetti A (2014) Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function. J Optim Theory Appl 162(1):107–132

    Article  Google Scholar 

  • Combettes PL (2004) Solving monotone inclusions via compositions of nonexpansive averaged operators. Optimization 53(5–6):475–504

    Article  Google Scholar 

  • Frankel P, Garrigos G, Peypouquet J (2015) Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates. J Optim Theory Appl 165(3):874–900

    Article  Google Scholar 

  • Hesse R, Luke DR, Sabach S, Tam MK (2014) Proximal heterogeneous block input-output method and application to blind ptychographic diffraction imaging. arXiv:1408.1887v1

  • Kurdyka K (1998) On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier (Grenoble) 48(3):769–783

    Article  Google Scholar 

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

  • Maingé P-E (2008) Convergence theorems for inertial KM-type algorithms. J Comput Appl Math 219:223–236

    Article  Google Scholar 

  • Maingé P-E, Moudafi A (2008) Convergence of new inertial proximal methods for dc programming. SIAM J Optim 19(1):397–413

    Article  Google Scholar 

  • Mordukhovich B (2006) Variational analysis and generalized differentiation, I: basic theory, II: applications. Springer, Berlin

    Google Scholar 

  • Moudafi A, Oliny M (2003) Convergence of a splitting inertial proximal method for monotone operators. J Comput Appl Math 155:447–454

    Article  Google Scholar 

  • Nesterov Y (2004) Introductory lectures on convex optimization: a basic course. Kluwer Academic Publishers, Dordrecht

    Book  Google Scholar 

  • Ochs P, Chen Y, Brox T, Pock T (2014) iPiano: inertial proximal algorithm for non-convex optimization. SIAM J Imag Sci 7(2):1388–1419

    Article  Google Scholar 

  • Pesquet J-C, Pustelnik N (2012) A parallel inertial proximal optimization method. Pac J Optim 8(2):273–306

    Google Scholar 

  • Rockafellar RT, Wets RJ-B (1998) Variational analysis, fundamental principles of mathematical sciences 317. Springer, Berlin

    Google Scholar 

Download references

Acknowledgments

The authors are thankful to two anonymous reviewers for pertinent comments and remarks which improved the quality of the paper.

Author information

Authors and Affiliations

  1. Faculty of Mathematics, University of Vienna, Oskar-Morgenstern-Platz 1, 1090, Vienna, Austria

    Radu Ioan Boţ & Ernö Robert Csetnek

  2. Department of Mathematics, Technical University of Cluj-Napoca, 400027, Cluj-Napoca, Romania

    Szilárd Csaba László

Authors
  1. Radu Ioan Boţ
    View author publications

    Search author on:PubMed Google Scholar

  2. Ernö Robert Csetnek
    View author publications

    Search author on:PubMed Google Scholar

  3. Szilárd Csaba László
    View author publications

    Search author on:PubMed Google Scholar

Corresponding author

Correspondence to Radu Ioan Boţ.

Additional information

R. I. Boţ: Research partially supported by DFG (German Research Foundation), project BO 2516/4-1.

E. R. Csetnek: Research supported by DFG (German Research Foundation), project BO 2516/4-1.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Boţ, R.I., Csetnek, E.R. & László, S.C. An inertial forward–backward algorithm for the minimization of the sum of two nonconvex functions. EURO J Comput Optim 4, 3–25 (2016). https://doi.org/10.1007/s13675-015-0045-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue date:

  • DOI: https://doi.org/10.1007/s13675-015-0045-8

Keywords

Mathematics subject classification

Profiles

  1. Szilárd Csaba László View author profile