×

Fast continuous dynamics inside the graph of maximally monotone operators. (English) Zbl 07660559

Summary: In a Hilbert framework, we introduce a new class of fast continuous dissipative dynamical systems for approximating zeroes of an arbitrary maximally monotone operator. This system originates from some change of variable operated in a continuous Nesterov-like model that is driven by the Yosida regularization of the operator and that involves an asymptotic vanishing damping. The proposed model (based upon the Minty representation of maximally monotone operators) is investigated through a first-order reformulation that amounts to dynamics involving three variables: a couple of two variables that lies in the graph of the considered operator, along with an auxiliary variable. We establish the weak convergence towards zeroes of the operator for two of the trajectories, as well as fast convergence to zero of their velocities. We also prove a fast convergence property to zero for the third trajectory and for its velocity. It turns out that our model offers a new and well-adapted framework for discrete counterparts. Several algorithms are then suggested relative to monotone inclusions. Some of them recover some recently developed inertial proximal algorithms that incorporate a correction term in addition to the classical momentum term.

MSC:

37N40 Dynamical systems in optimization and economics
47H05 Monotone operators and generalizations
46N10 Applications of functional analysis in optimization, convex analysis, mathematical programming, economics
49M30 Other numerical methods in calculus of variations (MSC2010)
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
90B50 Management decision making, including multiple objectives
90C25 Convex programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Abbas, B.; Attouch, H.; Svaiter, BF, Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces, J. Optim. Theory Appl., 161, 2, 331-360 (2014) · Zbl 1339.47080 · doi:10.1007/s10957-013-0414-5
[2] 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., 81, 8, 747-779 (2002) · Zbl 1036.34072 · doi:10.1016/S0021-7824(01)01253-3
[3] Attouch, H.; Bolte, J.; Redont, P., Optimizing properties of an inertial dynamical system with geometric damping: Link with proximal methods, Control. Cybern., 31, 643-657 (2002) · Zbl 1136.90474
[4] Attouch, H.; Cabot, A., Convergence of a relaxed inertial forward-backward algorithm for structured monotone inclusions, App. Math. Optim., 80, 547-598 (2019) · Zbl 1434.90129 · doi:10.1007/s00245-019-09584-z
[5] Attouch, H., Chbani, Z., Fadili, J., Riahi, H.: First-order optimization algorithms via inertial systems with Hessian driven damping. Math. Programm. doi:10.1007/s10107-020-01591-1, arXiv:1907.10536 (2019) · Zbl 1497.37121
[6] Attouch, H.; Chbani, Z.; Peypouquet, J.; Redont, P., Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Math. Program., 168, 1-2, 123-175 (2018) · Zbl 1395.34068 · doi:10.1007/s10107-016-0992-8
[7] Attouch, H., László, S.C.: Continuous Newton-like inertial dynamics for monotone inclusions. Set-valued and variational Analysis. doi:10.1007/s11228-020-00564-y (2020)
[8] Attouch, H.; Peypouquet, J., Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators, Math. Program., 174, 391-432 (2019) · Zbl 1412.37083 · doi:10.1007/s10107-018-1252-x
[9] Attouch, H.; Peypouquet, J.; Redont, P., Fast convex minimization via inertial dynamics with Hessian driven damping, J. Diff. Equat., 261, 5734-5783 (2016) · Zbl 1375.49028 · doi:10.1016/j.jde.2016.08.020
[10] Brezis, H.: Opérateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert, Math Stud, 5, North-Holland, Amsterdam (1973) · Zbl 0252.47055
[11] Brezis, H., Function Analysis, Sobolev Spaces and Partial Differential Equations (2010), New York: Springer, New York
[12] Cabot, A.; Engler, H.; Gadat, S., On the long time behavior of second order differential equations with asymptotically small dissipation, Trans. Amer. Math. Soc., 361, 5983-6017 (2009) · Zbl 1191.34078 · doi:10.1090/S0002-9947-09-04785-0
[13] Cabot, A.; Engler, H.; Gadat, S., Second order differential equations with asymptotically small dissipation and piecewise flat potentials, Electr. J. Differ. Equat., 17, 33-38 (2009) · Zbl 1171.34323
[14] Kim, D., Accelerated proximal point method for maximally monotone operators, Math. Programm., 190, 57-87 (2021) · Zbl 1478.90089 · doi:10.1007/s10107-021-01643-0
[15] Labarre, F., Maingé, P.E.: First-order frameworks for continuous Newton-like dynamics governed by maximally monotone operators. Set-Valued Var. Anal. doi:10.1007/s11228-021-00593-1 (2021)
[16] Maingé, PE, Accelerated proximal algorithms with a correction term for monotone inclusions, Appl. Math. Optim., 84, 2027-2061 (2021) · Zbl 07498429 · doi:10.1007/s00245-021-09819-y
[17] Maingé, P.E.: Fast convergence of generalized forward-backward algorithms for structured monotone inclusions. J. Convex Anal. 29(3) (2022) · Zbl 1496.90058
[18] May, R.: Asymptotic for a second order evolution equation with convex potential and vanishing damping term. Turk. J. Math. 41(3). doi:10.3906/mat-1512-28 (2015) · Zbl 1424.34186
[19] Minty, GJ, Monotone (nonlinear) operators in Hilbert spaces, Duke Math. J., 29, 341-346 (1962) · Zbl 0111.31202 · doi:10.1215/S0012-7094-62-02933-2
[20] Opial, Z., Weak convergence of the sequence of successive approximations for nonexpansive mappings, Bull. Amer. Math. Soc., 73, 591-597 (1967) · Zbl 0179.19902 · doi:10.1090/S0002-9904-1967-11761-0
[21] Shi, B., Du, S.S., Jordan, M.I., Su, W.J.: Understanding the acceleration phenomenon via high-resolution differential equations. arXiv:1810.08907v3 (2018)
[22] Su, W.; Boyd, S.; Candès, EJ, A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights, Neural Inf. Process.Syst., 27, 2510-2518 (2014)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.