Abstract
The aim of this survey is to present the main important techniques and tools from variational analysis used for first and second order dynamical systems of implicit type for solving monotone inclusions and non-smooth optimization problems. The differential equations are expressed by means of the resolvent (in case of a maximally monotone set valued operator) or the proximal operator for non-smooth functions. The asymptotic analysis of the trajectories generated relies on Lyapunov theory, where the appropriate energy functional plays a decisive role. While the most part of the paper is related to monotone inclusions and convex optimization problems in the variational case, we present also results for dynamical systems for solving non-convex optimization problems, where the Kurdyka-Łojasiewicz property is used.
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.: On the minimizing property of a second order dissipative system in Hilbert spaces. SIAM J. Control. Optim. 38(4), 1102–1119 (2000)
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)
Antipin, A. S.: Minimization of convex functions on convex sets by means of differential equations. (Russian) Differ. Uravnen. 30(9), 1475–1486 (1994). translation in Differential Equations 30(9), 1365–1375 (1994)
Attouch, H.: Fast inertial proximal ADMM algorithms for convex structured optimization with linear constraint, https://hal.archives-ouvertes.fr/hal-02501604, hal-02501604 (2020)
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, vol. 481, pp. 25–35. Springer, Berlin (2000)
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., 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., Cabot, A.: Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions. Appl. Math. Optim. 80(3), 547—598 (2019)
Attouch, H., Chbani, Z., Fadili, J., Riahi, H.: First-order optimization algorithms via inertial systems with Hessian driven damping. arXiv:1907.10536v1 (2019)
Attouch, H., Chbani, Z., Peypouquet, J., Redont, P.: Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Mathematical Programming 168(1-2), Ser B, 123–175 (2018)
Attouch, H., Chbani, Z., Riahi, H.: Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3. ESAIM: Control Optim Calc. Var., 25 (2019)
Attouch, H., Chbani, Z., Riahi, H.: Fast convex optimization via a third-order in time evolution equation, Optimization, online first
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., László, S. C.: Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators. HAL-02549730 (2020)
Attouch, H., László, S.C.: Continuous Newton-like Inertial Dynamics for Monotone Inclusions, https://hal.archives-ouvertes.fr/hal-02577331 (2020)
Attouch, H., Maingé, P. -E.: Asymptotic behavior of second-order dissipative evolution equations combining potential with non-potential effects. ESAIM: Control Optim. Calc. Var. 17(3), 836–857 (2011)
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/n2). J.. Convex Anal. 23(1), 139–180 (2016)
Attouch, H., Peypouquet, J.: Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operator. Math. Programm. 174, 391—432 (2019)
Attouch, H., Peypouquet, J., Redont, P.: Fast convex optimization via inertial dynamics with Hessian driven damping. J. Differ. Equ. 261(10), 5734–5783 (2016)
Attouch, H., Svaiter, B. F.: A continuous dynamical Newton-like approach to solving monotone inclusions. SIAM J. Control. Optim. 49(2), 574–598 (2011)
Baillon, J. B., Brézis, H.: Une remarque sur le comportement asymptotique des semigroupes non linéaires. Houst. J. Math. 2(1), 5–7 (1976)
Banert, S., Boţ, R.I.: A forward-backward-forward differential equation and its asymptotic properties. J. Convex Anal. 25(2), 371–388 (2018)
Banert, S., Boţ, R.I., Csetnek, E.R.: Fixing and extending some recent results on the ADMM algorithm, Numerical Algorithms, online first
Bauschke, H. H., Combettes, P. L., Analysis, Convex: Monotone Operator Theory in Hilbert Spaces CMS Books in Mathematics. Springer, New York (2011)
Beck, A., Teboulle, M.: A fast iterative shrinkage-tresholding algorithm for linear inverse problems. SIAM J. Imaging Sci. 2(1), 183–202 (2009)
Bertsekas, D. P.: Nonlinear Programming, 2nd edn. Athena Scientific, Cambridge (1999)
Bitterlich, S., Csetnek, E. R., Wanka, G.: A Dynamical Approach to Two-Block Separable Convex Optimization Problems with Linear Constraints, arXiv:2005.09953 (2020)
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. Am. Math. Soc. 362(6), 3319–3363 (2010)
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., Vanderwerff, J. D.: Convex Functions: Constructions, Characterizations and Counterexamples. Cambridge University Press, Cambridge (2010)
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.: A dynamical system associated with the fixed points set of a nonexpansive operator. J. Dyn. Diff. Equ. 29(1), 155–168 (2017)
Boţ, R.I., Csetnek, E.R.: Convergence rates for dynamical systems associated with monotone inclusion problems. J. Math. Anal. Appl. 457(2), 1135–1152 (2018)
Boţ, R.I., Csetnek, E.R.: A forward-backward dynamical approach to the minimization of the sum of a nonsmooth convex with a smooth nonconvex function. ESAIM Control Optim. Calc. Var. 24(2), 463–477 (2018)
Boţ, R.I., Csetnek, E.R.: ADMM For monotone operators: convergence analysis and rates. Adv. Comput. Math. 45(1), 327–359 (2019)
Boţ, R.I., Csetnek, E.R., Heinrich, A.: A primal-dual splitting algorithm for finding zeros of sums of maximally monotone operators. SIAM J. Optim. 23(4), 2011–2036 (2013)
Boţ, R.I., Csetnek, E.R., Heinrich, A., Hendrich, C.: On the convergence rate improvement of a primal-dual splitting algorithm for solving monotone inclusion problems. Math. Program. 150(2), 251–279 (2015)
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)
Boţ, R.I., Csetnek, E.R., László, S.C.: Approaching nonsmooth nonconvex minimization through second order proximal-gradient dynamical systems. J. Evol. Equ. 18(3), 1291–1318 (2018)
Boţ, R.I., Csetnek, E.R., László, S.C.: A primal-dual dynamical approach to structured convex minimization problems, arXiv:1905.08290 (2019)
Boţ, R.I., Csetnek, E.R., László, S.C.: Tikhonov regularization of a second order dynamical system with Hessian driven damping, Mathematical Programming, online first
Boţ, R.I., Csetnek, E.R., Vuong, P.T.: A The Forward-Backward-Forward Method from continuous and discrete perspective for pseudo-monotone variational inequalities in Hilbert spaces. Europ. J. Oper. Res. 287, 49–60 (2020)
Boţ, R.I., Grad, S.M., Meier, D., Staudigl, M.: Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure, arXiv:1911.04758 (2019)
Boţ, R.I., Kanzler, L: A forward-backward dynamical approach for nonsmooth problems with block structure coupled by a smooth function, arXiv:2001.10051 (2020)
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, vol. 50. North-Holland/Elsevier, New York (1973)
Bruck, R.E. Jr : Asymptotic convergence of nonlinear contraction semigroups in Hilbert space. J. Funct. Anal. 18, 15–26 (1975)
Chambolle, A., Pock, T.: A first-order primal-dual algorithm for convex problems with applications to imaging. J. Math. Imaging Vis. 40(1), 120–145 (2011)
Chen, G., Teboulle, M.: A proximal-based decomposition method for convex minimization problems. Math. Program. 64, 81–101 (1994)
Combettes, P.L., Glaudin, L.E.: Quasinonexpansive iterations on the affine hull of orbits: From Mann’s mean value algorithm to inertial methods. SIAM J. Optim. 27, 2356—2380 (2017)
Combettes, P.L., Pesquet, J.-C.: Primal-dual splitting algorithm for solving inclusions with mixtures of composite, Lipschitzian, and parallel-sum type monotone operators. Set-Valued Var. Anal. 20(2), 307–330 (2012)
Condat, L.: A primal-dual splitting method for convex optimization involving Lipschitzian, proximable and linear composite terms. J. Optim. Theory Appl. 158(2), 460–479 (2013)
Corman, E., Yuan, X.: A Generalized proximal point algorithm and its convergence rate. SIAM J. Optim. 24(4), 1614–1638 (2014)
Csetnek, E.R., Eberhard, A., Tam, M.K.: Convergence Rates for Boundedly Regular Systems, arXiv:2004.00818 (2020)
Csetnek, E.R., Malitsky, Y., Tam, M.K.: Shadow Douglas-Rachford splitting for monotone inclusions. Appl. Math. Optim. 80(3), 665–678 (2019)
Davis, D., Yin, W.: Convergence Rate Analysis of Several Splitting Schemes. In: Glowinski, R., Osher, S.J., Yin, W. (eds.) Splitting Methods in Communication, Imaging, Science, and Engineering, pp 115–163 (2017)
Fazel, M., Pong, T.K., Sun, D., Tseng, P.: Hankel matrix rank minimization with applications in system identification and realization. SIAM J. Matrix Anal. Appl. 34, 946–977 (2013)
Haraux, A.: Systèmes Dynamiques Dissipatifs Et Applications Recherches En Mathé- Matiques AppliquééEs, vol. 17. Masson, Paris (1991)
Haraux, A., Jendoubi, M.: Convergence of solutions of second-order gradient-like systems with analytic nonlinearities. J. Differ. Equ. 144(2), 313–320 (1998)
Kurdyka, K.: On gradients of functions definable in o-minimal structures. Ann. l’inst. Four. (Grenoble) 48(3), 769–783 (1998)
Liang, J., Fadili, J., Peyré, G.: Convergence rates with inexact nonexpansive operators. Math. Programm. 159, 403—434 (2016)
Łojasiewicz, S.: 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 (1963)
Malitsky, Y., Tam, M.K.: A Forward-Backward splitting method for monotone inclusions without cocoercivity. SIAM J. Optim. 30(2), 1451–1472 (2020)
Mordukhovich, B.: Variational Analysis and Generalized Differentiation I: Basic Theory II: Applications, Springer, Berlin (2006)
Nesterov, Y.: A method for unconstrained convex minimization problem with the rate of convergence o(1/k2). Doklady AN SSSR (transl. Sov. Math. Docl.) 269, 543–547 (1983)
Nesterov, Y.: Introductory Lectures on Convex Optimization: a Basic Course. Kluwer Academic Publishers, Dordrecht (2004)
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)
Ogura, N., Yamada, I.: Non-strictly convex minimization over the fixed point set of an asymptotically shrinking nonexpansive mapping. Numer. Funct. Anal. Optim. 23(1-2), 113–137 (2002)
Peypouquet, J., Sorin, S.: Evolution equations for maximal monotone operators: asymptotic analysis in continuous and discrete time. J. Convex Anal. 17 (3-4), 1113–1163 (2010)
Polyak, B.T.: Introduction to Optimization, (Translated from the Russian) Translations Series in Mathematics and Engineering. Optimization Software, Inc., Publications Division, New York (1987)
Rieger, J., Tam, M.K.: Backward-Forward-Reflected-Backward Splitting for three operator monotone inclusions. Applied Mathematics and Computation, 381 (2020)
Rockafellar, R.T.: On the maximal monotonicity of subdifferential mappings. Pac. J. Math. 33(1), 209–216 (1970)
Rockafellar, R.T.: Monotone operators and the proximal point algorithm. SIAM J. Control. Optim. 14(5), 877–898 (1976)
Rockafellar, R.T., Wets, R.J.-B.: Variational Analysis Fundamental Principles of Mathematical Sciences, vol. 317. Springer, Berlin (1998)
Shefi, R., Teboulle, M.: Rate of convergence analysis of decomposition methods based on the proximal method of multipliers for convex optimization. SIAM J. Optim. 24(1), 269–297 (2014)
Shi, B., Du, S.S., Su, W.J., Jordan, M.I.: Acceleration via symplectic discretization of high-resolution differential equations. arXiv:1902.03694v2 (2019)
Simon, L.: Asymptotics for a class of nonlinear evolution equations, with applications to geometric problems. Ann. Math. (2) 118, 525–571 (1983)
Simons, S.: From Hahn-Banach to Monotonicity. Springer, Berlin (2008)
Sontag, E.D.: Mathematical control theory. Deterministic finite-dimensional systems, 2nd Edn, vol. 6. Texts in Applied Mathematics. Springer, New York (1998)
Su, W., Boyd, S., Candès, E.J.: A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights. J. Mach. Learn. Res. 17 (153), 1–43 (2016)
Tseng, P.: Applications of a splitting algorithm to decomposition in convex programming and variational inequalities. SIAM J. Control. Optim. 29 (1), 119–138 (1991)
Tseng, P.: A modified forward-backward splitting method for maximal monotone mappings. SIAM J. Control. Optim. 38, 431–446 (2000)
Vũ, B.C.: A splitting algorithm for dual monotone inclusions involving cocoercive operators. Adv. Comput. Math. 38(3), 667–681 (2013)
Acknowledgments
The author is thankful to the handling editor and two reviewers for their comments which improved the presentation of the manuscript.
Funding
Open access funding provided by University of Vienna.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher’s Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Research supported by FWF (Austrian Science Fund), project P29809-N32.
Rights and permissions
Open Access This article is licensed under a Creative Commons Attribution 4.0 International License, which permits use, sharing, adaptation, distribution and reproduction in any medium or format, as long as you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons licence, and indicate if changes were made. The images or other third party material in this article are included in the article's Creative Commons licence, unless indicated otherwise in a credit line to the material. If material is not included in the article's Creative Commons licence and your intended use is not permitted by statutory regulation or exceeds the permitted use, you will need to obtain permission directly from the copyright holder. To view a copy of this licence, visit http://creativecommons.org/licenses/by/4.0/.
About this article
Cite this article
Csetnek, E.R. Continuous Dynamics Related to Monotone Inclusions and Non-Smooth Optimization Problems. Set-Valued Var. Anal 28, 611–642 (2020). https://doi.org/10.1007/s11228-020-00548-y
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11228-020-00548-y
Keywords
- Dynamical systems
- Lyapunov analysis
- Krasnosel’skiı̆–Mann algorithm
- Monotone inclusions
- Resolvent
- Proximal operator
- Forward-backward algorithm
- Non-smooth optimization problem
- Kurdyka-Łojasiewicz property