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.
Keywords: Dynamical systems, continuous forward-backward method, nonsmooth optimization, limiting subdifferential, Kurdyka−Łojasiewicz property
@article{COCV_2018__24_2_463_0, author = {Ioan Bo\c{t}, Radu and Robert Csetnek, Ern\"o}, title = {A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function}, journal = {ESAIM: Control, Optimisation and Calculus of Variations}, pages = {463--477}, publisher = {EDP-Sciences}, volume = {24}, number = {2}, year = {2018}, doi = {10.1051/cocv/2017020}, zbl = {1428.90128}, mrnumber = {3816401}, language = {en}, url = {http://archive.numdam.org/articles/10.1051/cocv/2017020/} }
TY - JOUR AU - Ioan Boţ, Radu AU - Robert Csetnek, Ernö TI - A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function JO - ESAIM: Control, Optimisation and Calculus of Variations PY - 2018 SP - 463 EP - 477 VL - 24 IS - 2 PB - EDP-Sciences UR - http://archive.numdam.org/articles/10.1051/cocv/2017020/ DO - 10.1051/cocv/2017020 LA - en ID - COCV_2018__24_2_463_0 ER -
%0 Journal Article %A Ioan Boţ, Radu %A Robert Csetnek, Ernö %T A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function %J ESAIM: Control, Optimisation and Calculus of Variations %D 2018 %P 463-477 %V 24 %N 2 %I EDP-Sciences %U http://archive.numdam.org/articles/10.1051/cocv/2017020/ %R 10.1051/cocv/2017020 %G en %F COCV_2018__24_2_463_0
Ioan Boţ, Radu; Robert Csetnek, Ernö. A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function. ESAIM: Control, Optimisation and Calculus of Variations, Volume 24 (2018) no. 2, pp. 463-477. doi : 10.1051/cocv/2017020. http://archive.numdam.org/articles/10.1051/cocv/2017020/
[1] 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
and ,[2] 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
, and ,[3] 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] 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] 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
and ,[6] 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
, , and ,[7] 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] Variational Analysis in Sobolev and BV Spaces: Applications to PDEs and Optimization. Second Edition. MOS-SIAM Series on Optimization. Philadelphia (2014) | MR | Zbl
, and ,[10] A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1∕n2). J. Convex Anal. 23 (2016) 139–180 | MR | Zbl
, and ,[11] On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Program. Series B 116 (2009) 5–16 | DOI | MR | Zbl
and ,[12] 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
, , and ,[13] 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
, and ,[14] Asymptotic behavior of coupled dynamical systems with multiscale aspects. J. Differ. Equ. 248 (2010) 1315–1344 | DOI | MR | Zbl
and ,[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] A continuous dynamical Newton-like approach to solving monotone inclusions. SIAM J. Control Optimiz. 49 (2011) 574–598 | DOI | MR | Zbl
and ,[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] Convex Analysis and Monotone Operator Theory in Hilbert Spaces. CMS Books in Math., Springer, New York (2011) | MR | Zbl
and ,[19] 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
, and ,[20] Continuous gradient projection method in Hilbert spaces. J. Optimiz. Theory Appl. 119 (2003) 235–259 | DOI | MR | Zbl
,[21] The Łojasiewicz inequality for nonsmooth subanalytic functions with applications to subgradient dynamical systems. SIAM J. Optimiz. 17 (2006) 1205–1223 | DOI | MR | Zbl
, and ,[22] Clarke subgradients of stratifiable functions. SIAM J. Optimiz. 18 (2007) 556–572 | DOI | MR | Zbl
, , and ,[23] Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Transactions of the Amer. Math. Soc. 362 (2010) 3319–3363 | DOI | MR | Zbl
, , and ,[24] Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Program. Ser. A 146 (2014) 459–494 | DOI | MR | Zbl
, and ,[25] An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems. J. Optimiz. Theory Appl. 171 (2016) 600–616 | DOI | MR | Zbl
and ,[26] 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
and ,[27] Approaching the solving of constrained variational inequalities via penalty term-based dynamical systems. J. Math. Anal. Appl. 435 (2016) 1688–1700 | DOI | MR | Zbl
and ,[28] Second order forward-backward dynamical systems for monotone inclusion problems. SIAM J. Control Optimiz. 54 (2016) 1423–1443 | DOI | MR | Zbl
and ,[29] Convergence rates for forward-backward dynamical systems associated with strongly monotone inclusions. J. Math. Anal. Appl. 457 (2018) 1135–1152 | DOI | MR | Zbl
and ,[30] 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
, and ,[31] 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] 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
, and ,[33] 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
, and ,[34] Systèmes Dynamiques Dissipatifs et Applications. Recherches Math. Appl. Masson, Paris 17 (1991) | MR | Zbl
,[35] Convergence of solutions of second-order gradient-like systems with analytic nonlinearities. J. Differ.Equ. 144 (1998) 313–320 | DOI | MR | Zbl
and ,[36] Proximal heterogeneous block input-output method and application to blind ptychographic diffraction imaging. SIAM J. Imaging Sci. 8 (2015) 426–457 | DOI | MR | Zbl
, , and ,[37] On gradients of functions definable in o-minimal structures. Annales de l’institut Fourier (Grenoble) 48 (1998) 769–783 | DOI | Numdam | MR | Zbl
,[38] 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] Variational Analysis and Generalized Differentiation I: Basic Theory, II: Applications. Springer Verlag, Berlin (2006) | MR | Zbl
,[40] iPiano: Inertial proximal algorithm for non-convex optimization. SIAM J. Imaging Sci. 7 (2014) 1388–1419 | DOI | MR | Zbl
, , and ,[41] Variational Analysis. Vol. 317 of Fundamental Principles of Mathematical Sciences. Springer Verlag, Berlin (1998) | MR | Zbl
and ,[42] Asymptotics for a class of nonlinear evolution equations, with applications to geometric problems. Ann. Math. 118 (1983) 525–571 | DOI | MR | Zbl
,Cited by Sources: