Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient

Hedy Attouch; Alexandre Cabot; Zaki Chbani; Hassan Riahi

doi:10.3934/eect.2018018

Article Contents

2018, Volume 7, Issue 3: 353-371. Doi: 10.3934/eect.2018018

This issue Previous Article Energy decay for the damped wave equation on an unbounded network Next Article Existence and continuous-discrete asymptotic behaviour for Tikhonov-like dynamical equilibrium systems

Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient

1.
IMAG, Univ. Montpellier, CNRS, Montpellier, France
2.
Institut de Mathématiques de Bourgogne, UMR 5584, Université Bourgogne Franche-Comté, 21000 Dijon, France
3.
Faculty of Sciences Semlalia, Mathematics, Cadi Ayyad university, 40000 Marrakech, Morroco

* Corresponding author
* Corresponding author

Received: December 2017

Revised: April 2018

Published: July 2018

Abstract Full Text(HTML) Related Papers Cited by

Abstract

In a Hilbert space $\mathcal H$ , we study the convergence properties when $t→+∞$ of the trajectories of the second-order differential equation

$\begin{equation*}\ddot{x}(t) + γ(t) \dot{x}(t) + \nabla Φ (x(t)) = 0, \;\;\;\;\;\;\;\;{{\rm (IGS)}_{γ}}\end{equation*}$

where $\nablaΦ$ is the gradient of a convex continuously differentiable function $Φ: \mathcal H→\mathbb R$ , and $γ(t)$ is a time-dependent positive viscous damping coefficient. This study aims to offer a unifying vision on the subject, and to complement the article by Attouch and Cabot (J. Diff. Equations, 2017). We obtain convergence rates for the values $Φ(x(t))-{\rm{inf}}_\mathcal{H} Φ$ and the velocities under general conditions involving only $γ(·)$ and its derivatives. In particular, in the case $γ(t) = \frac{α}{t}$ , which is directly connected to the Nesterov accelerated gradient method, our approach allows us to cover all the positive values of $α$ , including the subcritical case $α<3$ . Our approach is based on the introduction of a new class of Lyapunov functions.

Keywords:

Mathematics Subject Classification: 37N40, 49M30, 65K05, 65K10, 90C25.

Citation:

Full Text(HTML)

Related Papers

Cited by

References

[1]	V. Apidopoulos, J.-F. Aujol and Ch. Dossal, The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case $b \le 3$, SIAM J. Optim., 28 (2018), 551-574. doi: 10.1137/17M1128642.
[2]	H. Attouch and A. Cabot, Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity, J. Differential Equations, 263 (2017), 5412-5458. doi: 10.1016/j.jde.2017.06.024.
[3]	H. Attouch, A. Cabot and P. Redont, The dynamics of elastic shocks via epigraphical regularization of a differential inclusion, Adv. Math. Sci. Appl., 12 (2002), 273-306.
[4]	H. Attouch, Z. Chbani, J. Peypouquet and P. Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing damping, Math. Program. Ser. B, 168 (2018), 123-175. doi: 10.1007/s10107-016-0992-8.
[5]	H. Attouch, Z. Chbani and H. Riahi, Rate of convergence of the Nesterov accelerated gradient method in the subcritical case $\alpha \le 3$, arXiv: 1706.05671v1, [math. OC], accepted in $COCV$. doi: 10.1051/cocv/2017083.
[6]	H. Attouch and J. Peypouquet, The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $\frac{1}{k^2}$, SIAM J. Optim., 26 (2016), 1824-1834. doi: 10.1137/15M1046095.
[7]	J.-F. Aujol and Ch. Dossal, Stability of over-relaxations for the Forward-Backward algorithm, application to FISTA, SIAM J. Optim., 25 (2015), 2408-2433. doi: 10.1137/140994964.
[8]	J.-F. Aujol and Ch. Dossal, Optimal rate of convergence of an ODE associated to the Fast Gradient Descent schemes for $b>0$, HAL Preprint 01547251, 2017.
[9]	M. Balti and R. May, Asymptotic for the perturbed heavy ball system with vanishing damping term, Evolution Equations and Control Theory, 6 (2017), 177-186. doi: 10.3934/eect.2017010.
[10]	A. Beck and M. Teboulle, A fast iterative shrinkage-thresholding algorithm for linear inverse problems, SIAM J. Imaging Sci., 2 (2009), 183-202. doi: 10.1137/080716542.
[11]	R. I. Bot and E. R. Csetnek, Second order forward-backward dynamical systems for monotone inclusion problems, SIAM J. Control Optim., 54 (2016), 1423-1443. doi: 10.1137/15M1012657.
[12]	A. Cabot, H. Engler and 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-6017. doi: 10.1090/S0002-9947-09-04785-0.
[13]	A. Cabot, H. Engler and S. Gadat, Second order differential equations with asymptotically small dissipation and piecewise flat potentials, Electronic Journal of Differential Equations, 17 (2009), 33-38.
[14]	A. Cabot and P. Frankel, Asymptotics for some semilinear hyperbolic equations with non-autonomous damping, Journal of Differential Equations, 252 (2012), 294-322. doi: 10.1016/j.jde.2011.09.012.
[15]	A. Chambolle and Ch. Dossal, On the convergence of the iterates of the "Fast Iterative Shrinkage/Thresholding Algorithm", Journal of Optimization Theory and Applications, 166 (2015), 968-982. doi: 10.1007/s10957-015-0746-4.
[16]	Y. Drori and M. Teboulle, Performance of first-order methods for smooth convex minimization: A novel approach, Mathematical Programming, Series A, 145 (2014), 451-482. doi: 10.1007/s10107-013-0653-0.
[17]	M. Ghisi, M. Gobbino and A. Haraux, The remarkable effectiveness of time-dependent damping terms for second order evolution equations, SIAM J. Control Optim., 54 (2016), 1266-1294. doi: 10.1137/15M1029485.
[18]	A. Haraux, Systèmes Dynamiques Dissipatifs et Applications, Masson, Paris, 1991.
[19]	A. Haraux and M. A. Jendoubi, Asymptotics for a second order differential equation with a linear, slowly time-decaying damping term, Evolution Equations and Control Theory, 2 (2013), 461-470. doi: 10.3934/eect.2013.2.461.
[20]	M. A. Jendoubi and R. May, Asymptotics for a second-order differential equation with nonautonomous damping and an integrable source term, Applicable Analysis, 94 (2015), 436-444. doi: 10.1080/00036811.2014.903569.
[21]	R. May, Asymptotic for a second order evolution equation with convex potential and vanishing damping term, Turk. J. Math., 41 (2017), 681-685. doi: 10.3906/mat-1512-28.
[22]	Y. Nesterov, A method of solving a convex programming problem with convergence rate $O(1/k^2)$, Soviet Mathematics Doklady, 27 (1983), 372-376.
[23]	Y. Nesterov, Introductory Lectures on Convex Optimization: A Basic Course, volume 87 of Applied Optimization. Kluwer Academic Publishers, Boston, MA, 2004. doi: 10.1007/978-1-4419-8853-9.
[24]	M. Schmidt, N. Le Roux and F. Bach, Convergence rates of inexact proximal-gradient methods for convex optimization, NIPS'11 - 25 th Annual Conference on Neural Information Processing Systems, Dec 2011, Grenada, Spain. (2011) HAL inria-00618152v3.
[25]	M. V. Solodov and B. F. Svaiter, A unified framework for some inexact proximal point algorithms, Numer. Funct. Anal. Optim., 22 (2001), 1013-1035. doi: 10.1081/NFA-100108320.
[26]	W. Su, S. Boyd and E. J. Candès, A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights, Journal of Machine Learning Research, 17 (2016), 1-43.
[27]	S. Villa, S. Salzo, L. Baldassarres and A. Verri, Accelerated and inexact forward-backward, SIAM J. Optim., 23 (2013), 1607-1633. doi: 10.1137/110844805.