×

Continuous Newton-like inertial dynamics for monotone inclusions. (English) Zbl 1477.37101

Summary: In a Hilbert framework \(\mathcal{H}\), we study the convergence properties of a Newton-like inertial dynamical system governed by a general maximally monotone operator \(A:\mathcal{H}\rightarrow 2^{\mathcal{H}}\). When \(A\) is equal to the subdifferential of a convex lower semicontinuous proper function, the dynamic corresponds to the introduction of the Hessian-driven damping in the continuous version of the accelerated gradient method of Nesterov. As a result, the oscillations are significantly attenuated. According to the technique introduced by H. Attouch and J. Peypouquet [Math. Program. 174, No. 1–2 (B), 391–432 (2019; Zbl 1412.37083)], the maximally monotone operator is replaced by its Yosida approximation with an appropriate adjustment of the regularization parameter. The introduction into the dynamic of the Newton-like correction term (corresponding to the Hessian driven term in the case of convex minimization) provides a well-posed evolution system for which we will obtain the weak convergence of the generated trajectories towards the zeroes of \(A\). We also obtain the fast convergence of the velocities towards zero. The results tolerate the presence of errors, perturbations. Then, we specialize our results to the case where the operator \(A\) is the subdifferential of a convex lower semicontinuous function, and obtain fast optimization results.

MSC:

37N40 Dynamical systems in optimization and economics
46N10 Applications of functional analysis in optimization, convex analysis, mathematical programming, economics
65K05 Numerical mathematical programming methods
65K10 Numerical optimization and variational techniques
90B50 Management decision making, including multiple objectives
90C25 Convex programming

Citations:

Zbl 1412.37083

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., An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping, Set-Valued Analysis, 9, 1-2, 3-11 (2001) · Zbl 0991.65056 · doi:10.1023/A:1011253113155
[3] 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
[4] Apidopoulos, V.; Aujol, J-F; Dossal, Ch, Convergence rate of inertial Forward-Backward algorithm beyond Nesterov’s rule, Math. Program., 180, 137-156 (2020) · Zbl 1439.90055 · doi:10.1007/s10107-018-1350-9
[5] Attouch, H., Cabot, A.: Convergence of a relaxed inertial proximal algorithm for maximally monotone operators. Math Program. doi:10.1007/s10107-019-01412-0 (2019) · Zbl 07263694
[6] Attouch, H.; Cabot, A., Convergence rates of inertial forward-backward algorithms, SIAM J. Optim., 28, 1, 849-874 (2018) · Zbl 1387.49047 · doi:10.1137/17M1114739
[7] Attouch, H., Chbani, Z., Fadili, J., Riahi, H.: First-order algorithms via inertial systems with Hessian driven damping. HAL-02193846 (2019)
[8] Attouch, H.; Chbani, Z.; Peypouquet, J.; Redont, P., Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Math. Program. B, 168, 123-175 (2018) · Zbl 1395.34068 · doi:10.1007/s10107-016-0992-8
[9] Attouch, H.; Chbani, Z.; Riahi, H., Fast proximal methods via time scaling of damped inertial dynamics, SIAM J. Optim., 29, 3, 2227-2256 (2019) · Zbl 07105235 · doi:10.1137/18M1230207
[10] Attouch, H., Chbani, Z., Riahi, H.: Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α ≤ 3. ESAIM-COCV 25, Article number 2 (2019) · Zbl 1437.49045
[11] Attouch, H.; Goudou, X.; Redont, P., The heavy ball with friction method. The continuous dynamical system, global exploration of the local minima of a real-valued function by asymptotical analysis of a dissipative dynamical system, Commun. Contemp. Math., 2, 1, 1-34 (2000) · Zbl 0983.37016 · doi:10.1142/S0219199700000025
[12] Attouch, H., László, S.C.: Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators. HAL-02549730 (2020) · Zbl 1477.90058
[13] Attouch, H.; Maingé, PE, Asymptotic behavior of second order dissipative evolution equations combining potential with non-potential effects, ESAIM Control Optim. Calc. Var., 17, 3, 836-857 (2011) · Zbl 1230.34051 · doi:10.1051/cocv/2010024
[14] Attouch, H.; Maingé, PE; 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) · Zbl 1248.34091
[15] Attouch, H.; Marques Alves, M.; Svaiter, BF, A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert Spaces, with complexity \(\mathcal{O}(1/n^2)O\)(1/n2), J. Convex Anal., 23, 1, 139-180 (2016) · Zbl 1348.47053
[16] Attouch, H.; Peypouquet, J., Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators, Math. Program., 174, 1-2, 391-432 (2019) · Zbl 1412.37083 · doi:10.1007/s10107-018-1252-x
[17] Attouch, H.; Peypouquet, J., The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than 1/k2, SIAM J. Optim., 26, 3, 1824-1834 (2016) · Zbl 1346.49048 · doi:10.1137/15M1046095
[18] Attouch, H.; Peypouquet, J.; Redont, P., Fast convex minimization via inertial dynamics with Hessian driven damping, J. Differ. Equ., 261, 10, 5734-5783 (2016) · Zbl 1375.49028 · doi:10.1016/j.jde.2016.08.020
[19] Attouch, H.; Redont, P.; Svaiter, BF, Global convergence of a closed-loop regularized Newton method for solving monotone inclusions in Hilbert spaces, J. Optim. Theory Appl., 157, 3, 624-650 (2013) · Zbl 1290.90061 · doi:10.1007/s10957-012-0222-3
[20] Attouch, H.; Svaiter, BF, A continuous dynamical Newton-Like approach to solving monotone inclusions, SIAM J. Control Optim., 49, 2, 574-598 (2011) · Zbl 1229.34097 · doi:10.1137/100784114
[21] Bauschke, H., Combettes, P.L.: Convex Analysis and Monotone Operator Theory in Hilbert spaces. CMS Books in Mathematics. Springer (2011) · Zbl 1218.47001
[22] Brézis, H.: Opérateurs maximaux monotones dans les espaces de Hilbert et équations d’évolution. Lecture Notes 5 North Holland (1972)
[23] Boţ, RI; Csetnek, ER, Second order forward-backward dynamical systems for monotone inclusion problems, SIAM J. Control Optim., 54, 1423-1443 (2016) · Zbl 1339.34070 · doi:10.1137/15M1012657
[24] Boţ, RI; Csetnek, ER; László, SC, A second-order dynamical approach with variable damping to nonconvex smooth minimization, Appl. Anal., 99, 3, 361-378 (2020) · Zbl 1428.90129 · doi:10.1080/00036811.2018.1495330
[25] Boţ, R.I., Csetnek, E.R., László, S.C.: Tikhonov regularization of a second order dynamical system with Hessian damping. Mathematical Programming. doi:10.1007/s10107-020-01528-8 (2020)
[26] Castera, C., Bolte, J., Févotte, C., Pauwels, E.: An Inertial Newton Algorithm for Deep Learning. HAL-02140748 (2019)
[27] Chambolle, A.; Dossal, Ch, On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm, J. Optim. Theory Appl., 166, 968-982 (2015) · Zbl 1371.65047 · doi:10.1007/s10957-015-0746-4
[28] Haraux, A.: Systèmes dynamiques dissipatifs et applications. RMA 17 Masson (1991) · Zbl 0726.58001
[29] Kim, D.: Accelerated Proximal Point Method for Maximally Monotone Operators. arXiv:1905.05149v3 (2020)
[30] László, S.C.: Convergence rates for an inertial algorithm of gradient type associated to a smooth nonconvex minimization. Mathematical Programming. doi:10.1007/s10107-020-01534-w (2020) · Zbl 1478.90097
[31] Lin, T., Jordan, M.I.: A Control-Theoretic Perspective on Optimal High-Order Optimization. arXiv:1912.07168v1 (2019)
[32] May, R., Asymptotic for a second-order evolution equation with convex potential and vanishing damping term, Turkish J. Math., 41, 3, 681-685 (2017) · Zbl 1424.34186 · doi:10.3906/mat-1512-28
[33] Nesterov, Y., A method for solving the convex programming problem with convergence rate o(1/k2), (Russian) Dokl. Akad. Nauk SSSR, 269, 3, 543-547 (1983) · Zbl 0535.90071
[34] Polyak, BT, Some methods of speeding up the convergence of iterative methods, Z. Vylist. Math. Fiz., 4, 1-17 (1964) · Zbl 0147.35301
[35] Shi, B., Du, S.S., Jordan, M.I., Su, W.J.: Understanding the acceleration phenomenon via high-resolution differential equations. arXiv:submit/2440124[cs.LG] (2018)
[36] Su, WJ; Boyd, S.; Candès, EJ, A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights, Neural Information Processing Systems, 27, 2510-2518 (2014) · Zbl 1391.90667
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.