Abstract
This paper deals with aa perturbed heavy ball system with vanishing damping that contains a Tikhonov regularization term, in connection to the minimization problem of a convex Fréchet differentiable function. We show that the value of the objective function in a generated trajectory converges in order o (1/t2) to the global minimum of the objective function. We also obtain the fast convergence of the velocities towards zero. Moreover, we obtain that a trajectory generated by the dynamical system converges weakly to a minimizer of the objective function. Finally, we show that the presence of the Tikhonov regularization term assures the strong convergence of the generated trajectories to an element of minimal norm from the argmin set of the objective function.
Authors
Cristian Daniel Alecsa,
(“Tiberiu Popoviciu” Institute of Numerical Analysis, Romanian Academy,
Romanian Institute of Science and Technology)
Note on author affiliation
The paper has been elaborated by the first author while working at ICTP, according to the version of the preprint posted on ResearchGate, at http://doi.org/10.13140/RG.2.2.29212.92801.
However, for the final/published version of the paper, the first author has deleted his affiliation at ICTP.
Keywords
convex optimization; heavy ball method; continuous second order dynamical system; Tikhonov regularization; convergence rate; strong convergence
Preprint available at http://doi.org/10.13140/RG.2.2.29212.92801, where the first author is affiliated at ICTP.
Cite this paper as:
C.D. Alecsa, L.S. Csaba, Tikhonov regularization of a perturbed heavy ball system with vanishing damping, SIAM J. Optim., 31 (2021) no. 4, pp. 2921-2954, http://doi.org/10.1137/20M1382027
About this paper
Journal
SIAM J. Optim.
Publisher Name
SIAM
DOI
published version: http://doi.org/10.1137/20M1382027
preprint version: DOI: 10.13140/RG.2.2.29212.92801
Print ISSN
1052-6234
Online ISSN
1095-7189
Google Scholar Profile
References
[1] B. Abbas, H. Attouch, B.F. Svaiter, Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces, Journal of Optimization Theory and its Applications, 161(2) (2014), 331-360748
[2] C.D. Alecsa, The long time behavior and the rate of convergence of symplectic convex algorithms obtained via splitting discretizations of inertial damping systems, (2020), arxiv.org/abs/2001.10831750
[3] C.D. Alecsa, S.C. Laszlo, T. Pinta, An Extension of the Second Order Dynamical System that Models Nesterov’s Convex Gradient Method, Applied Mathematics and Optimization, (2020), https://doi.org/10.1007/s00245-020-09692-1752
[4] C.D. Alecsa, S.C. Laszlo, A. Viorel, A gradient type algorithm with backward inertial steps associated to a nonconvex minimization problem, Numerical Algorithms, 84(2) (2020), 485-512754
[5] V. Apidopoulos, J.F. Aujol, Ch. Dossal, Convergence rate of inertial Forward-Backward algorithm beyond Nesterov’s rule, Mathematical Programming, 180 (2020), 137-156756
[6] H. Attouch, A. Balhag, Z. Chbani, H. Riahi, Fast convex optimization via inertial dynamics combining vis-757 cous and Hessian-driven damping with time rescaling, Evolution Equations and Control Theory, (2021), https://doi.org/10.3934/eect.202101759
[7] H. Attouch, A. Cabot, Convergence rates of inertial forward-backward algorithms, SIAM J. Optim., 28(1) (2018), 849-874
[8] H. Attouch, Z. Chbani, J. Fadili, H. Riahi, First-order algorithms via inertial systems with Hessian driven damping, Math. Program., (2020), https://doi.org/10.1007/s10107-020-01591-1762
[9] H. Attouch, Z. Chbani, J. Peypouquet, P. Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Math. Program. Ser. B, 168 (2018), 123-175764
[10] H. Attouch, Z. Chbani, H. Riahi, Combining fast inertial dynamics for convex optimization with Tikhonov regularization, Journal of Mathematical Analysis and Applications, 457(2) (2018), 1065-1094766
[11] H. Attouch, Z. Chbani, R. Riahi, Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α≤3. ESAIM-COCV, 25 (2019), Article number 2768
[12] H. Attouch, M.-O. Czarnecki, Asymptotic Control and Stabilization of Nonlinear Oscillators with Non-isolated Equilibria, J. Differential Equations, 179 (2002), 278-310770
[13] H. Attouch, R. Cominetti, A dynamical approach to convex minimization coupling approximation with the steepest descent method, J. Differential Equations, 128 (1996), 519-540772
[14] H. Attouch, S.C. Laszlo, Newton-like Inertial Dynamics and Proximal Algorithms Governed by Maximally Monotone Operators, SIAM Journal on Optimization, 30(4) (2020), 3252–3283774
[15] H. Attouch, S.C. Laszlo, Continuous Newton-like Inertial Dynamics for Monotone Inclusions, Set-Valued and Variational Analysis, (2020), doi:10.1007/s11228-020-00564-y776
[16] H. Attouch, S.C. Laszlo, Convex optimization via inertial algorithms with vanishing Tikhonov regularization: fast convergence to the minimum norm solution, (2021), https://arxiv.org/abs/2104.11987778
[17] H. Attouch, J. Peypouquet, The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than 1/k2. SIAM J. Optim., 26(3) (2016), 1824-1834780
[18] H. Attouch, J. Peypouquet, Convergence of inertial dynamics and proximal algorithms governed by maximal monotone operators, Mathematical Programming, 174(1-2) (2019), 391–432782
[19] H. Attouch, J. Peypouquet, P. Redont, Fast convex optimization via inertial dynamics with Hessian driven damping, Journal of Differential Equations, 261(10) (2016), 5734-5783784
[20] R.I. Bot¸, E.R. Csetnek, S.C. Laszlo, Tikhonov regularization of a second order dynamical system with Hessian damping, Math. Program., (2020), https://doi.org/10.1007/s10107-020-01528-8786
[21] R.I. Bot¸, E.R. Csetnek, S.C. Laszlo, A second-order dynamical approach with variable damping to nonconvex smooth minimization Applicable Analysis, 99(3) (2020), 361-378788
[22] R.I. Bot¸, S.M. Grad, D. Meier, M. Staudigl, Inducing strong convergence of trajectories in dynamical systems associated to monotone inclusions with composite structure, Adv. Nonlinear Anal., 10 (2021), 450–476790
[23] A. Cabot, H. Engler, S. Gadat, On the long time behavior of second order differential equations with asymptotically small dissipation, Transactions of the American Mathematical Society, 361 (2009), 5983-6017792
[24] A. Chambolle, Ch. Dossal, On the convergence of the iterates of the Fast Iterative Shrinkage Thresholding Algorithm, Journal of Optimization Theory and Applications, 166 (2015), 968-982794
[25] R. Cominetti, J. Peypouquet, S. Sorin, Strong asymptotic convergence of evolution equations governed by maximal monotone operators with Tikhonov regularization, J. Differential Equations, 245 (2008), 3753-3763796
[26] M.A. Jendoubi, R. May, Asymptotics for a second-order differential equation with nonautonomous damping and an integrable source term, Appl. Anal., 94(2) (2015), 435–443798
[27] S.C. Laszlo, Convergence rates for an inertial algorithm of gradient type associated to a smooth nonconvex minimization, Mathematical Programming, (2020), https://doi.org/doi.org/10.1007/s10107-020-01534-w800
[28] S.C. Laszlo, Forward-backward algorithms with different inertial terms for structured non-convex minimization problems, (2020), arxiv.org/abs/2002.07154802
[29] T. Lin, M.I. Jordan, A Control-Theoretic Perspective on Optimal High-Order Optimization, (2019), arXiv:1912.07168v1803
[30] R. May, Asymptotic for a second-order evolution equation with convex potential and vanishing damping term, Turkish Journal of Math., 41(3) (2017), 681-685805
[31] Y. Nesterov, A method of solving a convex programming problem with convergence rate O(1/k2), Soviet Mathematics Doklady, 27 (1983), 372-376807
[32] B. Shi, S.S. Du, M.I. Jordan, W.J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, (2018), arXiv:1810.08907v3809
[33] W. Su, S. Boyd, E.J. Candes, A differential equation for modeling Nesterov’s accelerated gradient method: theory and insights, Journal of Machine Learning Research 17(153) (2016), 1-43