Abstract
In this paper we carry out an asymptotic analysis of the proximal-gradient dynamical system
where f is a proper, convex and lower semicontinuous function, Φ a possibly nonconvex smooth function and γ,a and b are positive real numbers. We show that the generated trajectories approach the set of critical points of f + Φ, here understood as zeros of its limiting subdifferential, under the premise that a regularization of this sum function satisfies the Kurdyka-Łojasiewicz property. We also establish convergence rates for the trajectories, formulated in terms of the Łojasiewicz exponent of the considered regularization function.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Abbas, B., Attouch, H.: Dynamical systems and forward-backward algorithms associated with the sum of a convex subdifferential and a monotone cocoercive operator. Optimization 64(10), 2223–2252 (2015)
Abbas, B., Attouch, H., Svaiter, B.F.: Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces. J. Optim. Theory Appl. 161(2), 331–360 (2014)
Alvarez, F., Attouch, H., Bolte, J., Redont, P.: A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics. J. Math. Pures Appl. (9) 81(8), 747–779 (2002)
Alvarez, F., Pérez, J. M.: A dynamical system associated with Newton’s method for parametric approximations of convex minimization problems. Appl. Math. Optim. 38(2), 193–217 (1998)
Attouch, H., Alvarez, F. : The heavy ball with friction dynamical system for convex constrained minimization problems. In: Optimization (Namur, 1998). Lecture Notes in Economics and Mathematical Systems 481, pp. 25–35. Springer, Berlin (2000)
Antipin, A.S.: Minimization of convex functions on convex sets by means of differential equations. Russian Differentsial’nye Uravneniya 30(9), 1475–1486 (1994). translation in Differential Equations 30(9), 13651375, 1994
Attouch, H., Marques Alves, M., Svaiter, B.F.: A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity O(1/n 2). J. Convex Anal. 23(1), 139–180 (2016)
Attouch, H., Bolte, J.: On the convergence of the proximal algorithm for nonsmooth functions involving analytic features. Math. Programm. 116(1-2), Series B, 5–16 (2009)
Attouch, H., Bolte, J., Redont, P.: Optimizing properties of an inertial dynamical system with geometric damping. Link with proximal methods. Control Cybern. 31(3), 643–657 (2002)
Attouch, H., Bolte, J., Redont, P., Soubeyran, A.: Proximal alternating minimization and projection methods for nonconvex problems: an approach based on the Kurdyka-Łojasiewicz inequality. Math. Oper. Res. 35(2), 438–457 (2010)
Attouch, H., Bolte, J., Svaiter, B.F.: Convergence of descent methods for semi-algebraic and tame problems: proximal algorithms, forward-backward splitting, and regularized Gauss-Seidel methods. Math. Programm. 137(1-2), Series A, 91–129 (2013)
Attouch, H., Czarnecki, M.-O.: Asymptotic behavior of coupled dynamical systems with multiscale aspects. J. Differ. Equ. 248(6), 1315–1344 (2010)
Attouch, H., Goudou, X., Redont, P.: 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. Contemp. Math. 2(1), 1–34 (2000)
Attouch, H., Maingé, P.-E., Redont, P.: A second-order differential system with Hessian-driven damping; application to non-elastic shock laws. Differ. Equ. Appl. 4(1), 27–65 (2012)
Attouch, H., Peypouquet, J., Redont, P.: A dynamical approach to an inertial forward-backward algorithm for convex minimization. SIAM J. Optim. 24(1), 232–256 (2014)
Attouch, H., Peypouquet, J., Redont, P.: Fast convex optimization via inertial dynamics with Hessian driven damping. J. Differ. Equ. 261, 5734–5783 (2016)
Attouch, H., Redont, P.: The second-order in time continuous Newton method. In: Approximation, Optimization and Mathematical Economics (Pointe–Pitre, 1999), p. 2536. Physica, Heidelberg (2001)
Attouch, H., Svaiter, B.F.: A continuous dynamical Newton-like approach to solving monotone inclusions. SIAM J. Control Optim. 49(2), 574–598 (2011)
Banert, S., Boţ, R.I.: A forward-backward-forward differential equation and its asymptotic properties. J. Convex Anal. 25(2) (2018)
Bauschke, H.H., Combettes, P.L.: Convex analysis and monotone operator theory in hilbert spaces. CMS Books in Mathematics, Springer, New York (2011)
Bolte, J.: Continuous gradient projection method in Hilbert spaces. J. Optim. Theory Appl. 119(2), 235–259 (2003)
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)
Bolte, J., Daniilidis, A., Lewis, A., Shota, M.: Clarke subgradients of stratifiable functions. SIAM J. Optim. 18(2), 556–572 (2007)
Bolte, J., Daniilidis, A., Ley, O., Mazet, L.: Characterizations of Łojasiewicz inequalities: subgradient flows, talweg, convexity. Trans. Amer. Math. Soc. 362(6), 3319–3363 (2010)
Bolte, J., Nguyen, T.P., Peypouquet, J., Suter, B.W.: From error bounds to the complexity of first-order descent methods for convex functions, Mathematical Programming, doi:10.1007/s10107-016-1091-6
Bolte, J., Sabach, S., Teboulle, M.: Proximal alternating linearized minimization for nonconvex and nonsmooth problems. Math. Programm. Ser. A 146(1–2), 459–494 (2014)
Borwein, J.M., Zhu, Q.J.: Techniques of variational analysis. Springer, New York (2005)
Boţ, R.I., Csetnek, E.R.: An inertial Tseng’s type proximal algorithm for nonsmooth and nonconvex optimization problems. J. Optim. Theory Appl. 171(2), 600–616 (2016)
Boţ, R.I., Csetnek, E.R.: A dynamical system associated with the fixed points set of a nonexpansive operator, Journal of Dynamics and Differential Equations, doi:10.1007/s10884-015-9438-x (2015)
Boţ, R.I., Csetnek, E.R.: Approaching the solving of constrained variational inequalities via penalty term-based dynamical systems. J. Math. Anal. Appl. 435(2), 1688–1700 (2016)
Boţ, R.I., Csetnek, E.R.: Second order forward-backward dynamical systems for monotone inclusion problems. SIAM J. Control Optim. 54(3), 1423–1443 (2016)
Boţ, R.I., Csetnek, E.R.: Convergence rates for forward-backward dynamical systems associated with strongly monotone inclusions, Journal of Mathematical Analysis and Applications, doi:10.1016/j.jmaa.2016.07.007 (2016)
Boţ, R.I., Csetnek, E.R., László, S.: An inertial forward-backward algorithm for the minimization of the sum of two nonconvex functions. EURO J. Comput. Optim. 4, 3–25 (2016)
Brézis, H.: 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)
Chouzenoux, E., Pesquet, J.-C., Repetti, A.: 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 (2014)
Frankel, P., Garrigos, G., Peypouquet, J.: Splitting methods with variable metric for Kurdyka-Łojasiewicz functions and general convergence rates. J. Optim. Theory Appl. 165(3), 874–900 (2015)
Haraux, A.: Systèmes Dynamiques dissipatifs et applications. Recherches en Mathé- matiques Appliquéées 17, Masson, Paris (1991)
Hesse, R., Luke, D.R., Sabach, S., Tam, M.K.: Proximal heterogeneous block input-output method and application to blind ptychographic diffraction imaging. SIAM J. Imaging Sci. 8(1), 426–457 (2015)
Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. l’inst. Fourier (Grenoble) 48(3), 769–783 (1998)
Li, G., Pong, T.K.: Calculus of the exponent of Kurdyka-Łojasiewicz inequality and its applications to linear convergence of first-order methods arXiv:1602.02915v2 (2016)
Łojasiewicz, S.: Une propriéte ́topologique des sous-ensembles analytiques réels, pp. 87–89. Les Équations aux Dérivées Partielles, Éditions du Centre National de la Recherche Scientifique , Paris (1963)
Mordukhovich, B.: Variational Analysis and Generalized Differentiation I: Basic Theory, II: Applications. Springer-Verlag, Berlin (2006)
Ochs, P., Chen, Y., Brox, T., Pock, T.: iPiano: Inertial proximal algorithm for non-convex optimization. SIAM J. Imaging Sci. 7(2), 1388–1419 (2014)
Rockafellar, R.T., Wets, R. J.-B.: Variational analysis fundamental principles of mathematical sciences 317. Springer-Verlag, Berlin (1998)
Acknowledgments
Open access funding provided by Austrian Science Fund (FWF). The authors are thankful to two anonymous reviewers for comments and remarks which improved the presentation of the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Dedicated to the memory of Jon Borwein, who was so inspiring and motivating
Research partially supported by FWF (Austrian Science Fund), project I 2419-N32.
Research supported by FWF (Austrian Science Fund), Lise Meitner Programme, project M 1682-N25.
Rights and permissions
Open Access This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.
About this article
Cite this article
Boţ, R.I., Csetnek, E.R. Approaching Nonsmooth Nonconvex Optimization Problems Through First Order Dynamical Systems with Hidden Acceleration and Hessian Driven Damping Terms. Set-Valued Var. Anal 26, 227–245 (2018). https://doi.org/10.1007/s11228-017-0411-1
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-017-0411-1
Keywords
- Dynamical systems
- Lyapunov analysis
- Nonsmooth optimization
- Limiting subdifferential
- Kurdyka-Łojasiewicz property