A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function

Ioan Boţ, Radu; Robert Csetnek, Ernö

ESAIM: Control, Optimisation and Calculus of Variations, Tome 24 (2018) no. 2, pp. 463-477.

We address the minimization of the sum of a proper, convex and lower semicontinuous function with a (possibly nonconvex) smooth function from the perspective of an implicit dynamical system of forward-backward type. The latter is formulated by means of the gradient of the smooth function and of the proximal point operator of the nonsmooth one. The trajectory generated by the dynamical system is proved to asymptotically converge to a critical point of the objective, provided a regularization of the latter satisfies the Kurdyka−Łojasiewicz property. Convergence rates for the trajectory in terms of the Łojasiewicz exponent of the regularized objective function are also provided.

[1] B. Abbas and H. Attouch, Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator. Optimiz. 64 (2015) 2223–2252 | DOI | MR | Zbl

[2] B. Abbas, H. Attouch and B.F. Svaiter, Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces. J. Optimiz. Theory Appl. 161 (2014) 331–360 | DOI | MR | Zbl

[3] F. Alvarez, On the minimizing property of a second order dissipative system in Hilbert spaces. SIAM J. Control Optimiz. 38 (2000) 1102–1119 | DOI | MR | Zbl

[4] F. Alvarez, Weak convergence of a relaxed and inertial hybrid projection-proximal point algorithm for maximal monotone operators in Hilbert space. SIAM J. Optimiz. 14 (2004) 773–782 | DOI | MR | Zbl

[5] F. Alvarez and H. Attouch, An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. Set-Valued Anal. 9 (2001) 311 | DOI | MR | Zbl

[6] F. Alvarez, H. Attouch, J. Bolte and P. Redont, A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics. J. Math. Pures Appl. 81 (2002) 747–779 | DOI | MR | Zbl

[7] A.S. Antipin, Minimization of convex functions on convex sets by means of differential equations. (Russian) Differentsial’nye Uravneniya 30 (1994) 1475–1486; Translation Differ. Equ. 30 (1994) 1365–1375 | MR | Zbl

[8] H. Attouch and F. Alvarez, The heavy ball with friction dynamical system for convex constrained minimization problems. Optimization (Namur, 1998). In vol. 481 of Lecture Notes in Economics and Mathematical Systems. Springer, Berlin 2000 25–35 | MR | Zbl

[9] H. Attouch, G. Buttazzo and G. Michaille, Variational Analysis in Sobolev and BV Spaces: Applications to PDEs and Optimization. Second Edition. MOS-SIAM Series on Optimization. Philadelphia (2014) | MR | Zbl

[10] H. Attouch, M. Marques Alves and B.F. Svaiter, A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1∕n²). J. Convex Anal. 23 (2016) 139–180 | MR | Zbl

[11] H. Attouch and J. Bolte, On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. Series B 116 (2009) 5–16 | DOI | MR | Zbl

[12] H. Attouch, J. Bolte, P. Redont and A. Soubeyran, Proximal alternating minimization and projection methods for nonconvex problems:an approach based on the Kurdyka−Łojasiewicz inequality. Math. Operat. Res. 35 (2010) 438–457 | DOI | MR | Zbl

[13] H. Attouch, J. Bolte and B.F. Svaiter, Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Program. Series A 137 (2013) 91–129 | DOI | MR | Zbl

[14] H. Attouch and M.-O. Czarnecki, Asymptotic behavior of coupled dynamical systems with multiscale aspects. J. Differ. Equ. 248 (2010) 1315–1344 | DOI | MR | Zbl

[15] H. Attouch, X. Goudou and P. Redont, The heavy ball with friction method. I. The continuous dynamical system: global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system. Commun. Contemporary Math. 2 (2000) 1–34 | MR | Zbl

[16] H. Attouch and B.F. Svaiter, A continuous dynamical Newton-like approach to solving monotone inclusions. SIAM J. Control Optimiz. 49 (2011) 574–598 | DOI | MR | Zbl

[17] S. Banert and R.I. Boţ, A forward-backward-forward differential equation and its asymptotic properties. J. Convex Anal. 18 (to appear) | MR

[18] H.H. Bauschke and P.L. Combettes, Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Math., Springer, New York (2011) | MR | Zbl

[19] H.H. Bauschke, P.L. Combettes and D.R. Luke, Phase retrieval, error reduction algorithm, and Fienup variants: a view from convex optimization. J. Optical Society of America A. Optics, Image Science, and Vision 19 (2002) 1334–1345 | DOI | MR

[20] J. Bolte, Continuous gradient projection method in Hilbert spaces. J. Optimiz. Theory Appl. 119 (2003) 235–259 | DOI | MR | Zbl

[21] J. Bolte, A. Daniilidis and A. Lewis, The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optimiz. 17 (2006) 1205–1223 | DOI | MR | Zbl

[22] J. Bolte, A. Daniilidis, A. Lewis and M. Shiota, Clarke subgradients of stratifiable functions. SIAM J. Optimiz. 18 (2007) 556–572 | DOI | MR | Zbl

[23] J. Bolte, A. Daniilidis, O. Ley and L. Mazet, Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Transactions of the Amer. Math. Soc. 362 (2010) 3319–3363 | DOI | MR | Zbl

[24] J. Bolte, S. Sabach and M. Teboulle, Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. Ser. A 146 (2014) 459–494 | DOI | MR | Zbl

[25] R.I. Boţ and E.R. Csetnek, An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems. J. Optimiz. Theory Appl. 171 (2016) 600–616 | DOI | MR | Zbl

[26] R.I. Boţ and E.R. Csetnek, A dynamical system associated with the fixed points set of a nonexpansive operator. J. Dynamics Differ. Equ.0 29 (2017) 155–168 | DOI | MR | Zbl

[27] R.I. Boţ and E.R. Csetnek, Approaching the solving of constrained variational inequalities via penalty term-based dynamical systems. J. Math. Anal. Appl. 435 (2016) 1688–1700 | DOI | MR | Zbl

[28] R.I. Boţ and E.R. Csetnek, Second order forward-backward dynamical systems for monotone inclusion problems. SIAM J. Control Optimiz. 54 (2016) 1423–1443 | DOI | MR | Zbl

[29] R.I. Boţ and E.R. Csetnek, Convergence rates for forward-backward dynamical systems associated with strongly monotone inclusions. J. Math. Anal. Appl. 457 (2018) 1135–1152 | DOI | MR | Zbl

[30] R.I. Boţ, E.R. Csetnek and S. László, An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions. Euro J. Comput. Optimiz. 4 (2016) 3–25 | DOI | MR | Zbl

[31] H. Brézis, Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. North-Holland Mathematics Studies No. 5, Notas de Matemática 50. North-Holland/Elsevier, New York (1973) | MR | Zbl

[32] E. Chouzenoux, J.-C. Pesquet and A. Repetti, Variable metric forward-backward algorithm for minimizing the sum of a differentiable function and a convex function. J. Optimiz. Theory Appl. 162 (2014) 107–132 | DOI | MR | Zbl

[33] P. Frankel, G. Garrigos and J. Peypouquet, Splitting methods with variable metric for Kurdyka−Łojasiewicz functions and general convergence rates. J. Optimiz. Theory and its Appl. 165 (2015) 874–900 | DOI | MR | Zbl

[34] A. Haraux, Systèmes Dynamiques Dissipatifs et Applications. Recherches Math. Appl. Masson, Paris 17 (1991) | MR | Zbl

[35] A. Haraux and M. Jendoubi, Convergence of solutions of second-order gradient-like systems with analytic nonlinearities. J. Differ.Equ. 144 (1998) 313–320 | DOI | MR | Zbl

[36] R. Hesse,D.R. Luke, S. Sabach and M.K. Tam, Proximal heterogeneous block input-output method and application to blind ptychographic diffraction imaging. SIAM J. Imaging Sci. 8 (2015) 426–457 | DOI | MR | Zbl

[37] K. Kurdyka, On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier (Grenoble) 48 (1998) 769–783 | DOI | Numdam | MR | Zbl

[38] S. Łojasiewicz, Une propriété topologique des sous-ensembles analytiques réels. Les Équations aux Dérivées Partielles, Éditionsdu Centre National de la Recherche Scientifique Paris (1963) 87–89 | MR | Zbl

[39] B. Mordukhovich, Variational Analysis and Generalized Differentiation I: Basic Theory, II: Applications. Springer Verlag, Berlin (2006) | MR | Zbl

[40] P. Ochs, Y. Chen, T. Brox and T. Pock, iPiano: Inertial proximal algorithm for non-convex optimization. SIAM J. Imaging Sci. 7 (2014) 1388–1419 | DOI | MR | Zbl

[41] R.T. Rockafellar and R.J.-B. Wets, Variational Analysis. Vol. 317 of Fundamental Principles of Mathematical Sciences. Springer Verlag, Berlin (1998) | MR | Zbl

[42] L. Simon, Asymptotics for a class of nonlinear evolution equations, with applications to geometric problems. Ann. Math. 118 (1983) 525–571 | DOI | MR | Zbl