American Institute of Mathematical Sciences

Advanced
September  2018, 7(3): 353-371. doi: 10.3934/eect.2018018

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

Hedy Attouch 1, , Alexandre Cabot 2,, , Zaki Chbani 3, and  Hassan Riahi 3,

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

Received  December 2017 Revised  April 2018 Published  July 2018

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: Asymptotic stabilization, convex optimization, inertial gradient dynamics, fast gradient method, Lyapunov analysis, time-dependent viscosity.
Mathematics Subject Classification: 37N40, 49M30, 65K05, 65K10, 90C25.
Citation: Hedy Attouch, Alexandre Cabot, Zaki Chbani, Hassan Riahi. Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient. Evolution Equations & Control Theory, 2018, 7 (3) : 353-371. doi: 10.3934/eect.2018018
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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

A. Haraux, Systèmes Dynamiques Dissipatifs et Applications, Masson, Paris, 1991.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

show all references

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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[18]

A. Haraux, Systèmes Dynamiques Dissipatifs et Applications, Masson, Paris, 1991.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[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. Google Scholar

[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.  Google Scholar

[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.   Google Scholar

[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.  Google Scholar

[1]

Hedy Attouch, Aïcha Balhag, Zaki Chbani, Hassan Riahi. Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling. Evolution Equations & Control Theory, 2021  doi: 10.3934/eect.2021010
[2]

Jin-Zan Liu, Xin-Wei Liu. A dual Bregman proximal gradient method for relatively-strongly convex optimization. Numerical Algebra, Control & Optimization, 2021  doi: 10.3934/naco.2021028
[3]

Yanmei Sun, Yakui Huang. An alternate gradient method for optimization problems with orthogonality constraints. Numerical Algebra, Control & Optimization, 2021, 11 (4) : 665-676. doi: 10.3934/naco.2021003
[4]

Gaohang Yu, Shanzhou Niu, Jianhua Ma. Multivariate spectral gradient projection method for nonlinear monotone equations with convex constraints. Journal of Industrial & Management Optimization, 2013, 9 (1) : 117-129. doi: 10.3934/jimo.2013.9.117
[5]

Sanming Liu, Zhijie Wang, Chongyang Liu. On convergence analysis of dual proximal-gradient methods with approximate gradient for a class of nonsmooth convex minimization problems. Journal of Industrial & Management Optimization, 2016, 12 (1) : 389-402. doi: 10.3934/jimo.2016.12.389
[6]

Jan Sokołowski, Jan Stebel. Shape optimization for non-Newtonian fluids in time-dependent domains. Evolution Equations & Control Theory, 2014, 3 (2) : 331-348. doi: 10.3934/eect.2014.3.331
[7]

Guanghui Zhou, Qin Ni, Meilan Zeng. A scaled conjugate gradient method with moving asymptotes for unconstrained optimization problems. Journal of Industrial & Management Optimization, 2017, 13 (2) : 595-608. doi: 10.3934/jimo.2016034
[8]

Jueyou Li, Guoquan Li, Zhiyou Wu, Changzhi Wu, Xiangyu Wang, Jae-Myung Lee, Kwang-Hyo Jung. Incremental gradient-free method for nonsmooth distributed optimization. Journal of Industrial & Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021
[9]

El-Sayed M.E. Mostafa. A nonlinear conjugate gradient method for a special class of matrix optimization problems. Journal of Industrial & Management Optimization, 2014, 10 (3) : 883-903. doi: 10.3934/jimo.2014.10.883
[10]

Tingting Liu, Qiaozhen Ma. Time-dependent asymptotic behavior of the solution for plate equations with linear memory. Discrete & Continuous Dynamical Systems - B, 2018, 23 (10) : 4595-4616. doi: 10.3934/dcdsb.2018178
[11]

P. D. Howell, J. J. Wylie, Huaxiong Huang, Robert M. Miura. Stretching of heated threads with temperature-dependent viscosity: Asymptotic analysis. Discrete & Continuous Dynamical Systems - B, 2007, 7 (3) : 553-572. doi: 10.3934/dcdsb.2007.7.553
[12]

Feng Zhou, Chunyou Sun, Xin Li. Dynamics for the damped wave equations on time-dependent domains. Discrete & Continuous Dynamical Systems - B, 2018, 23 (4) : 1645-1674. doi: 10.3934/dcdsb.2018068
[13]

Yuhong Dai, Ya-xiang Yuan. Analysis of monotone gradient methods. Journal of Industrial & Management Optimization, 2005, 1 (2) : 181-192. doi: 10.3934/jimo.2005.1.181
[14]

Yigui Ou, Xin Zhou. A modified scaled memoryless BFGS preconditioned conjugate gradient algorithm for nonsmooth convex optimization. Journal of Industrial & Management Optimization, 2018, 14 (2) : 785-801. doi: 10.3934/jimo.2017075
[15]

Sergio Grillo, Jerrold E. Marsden, Sujit Nair. Lyapunov constraints and global asymptotic stabilization. Journal of Geometric Mechanics, 2011, 3 (2) : 145-196. doi: 10.3934/jgm.2011.3.145
[16]

Boumedièene Chentouf, Sabeur Mansouri. Boundary stabilization of a flexible structure with dynamic boundary conditions via one time-dependent delayed boundary control. Discrete & Continuous Dynamical Systems - S, 2021  doi: 10.3934/dcdss.2021090
[17]

Aowen Kong, Carlos Nonato, Wenjun Liu, Manoel Jeremias dos Santos, Carlos Raposo. Equivalence between exponential stabilization and observability inequality for magnetic effected piezoelectric beams with time-varying delay and time-dependent weights. Discrete & Continuous Dynamical Systems - B, 2021  doi: 10.3934/dcdsb.2021168
[18]

Rouhollah Tavakoli, Hongchao Zhang. A nonmonotone spectral projected gradient method for large-scale topology optimization problems. Numerical Algebra, Control & Optimization, 2012, 2 (2) : 395-412. doi: 10.3934/naco.2012.2.395
[19]

Hong Seng Sim, Chuei Yee Chen, Wah June Leong, Jiao Li. Nonmonotone spectral gradient method based on memoryless symmetric rank-one update for large-scale unconstrained optimization. Journal of Industrial & Management Optimization, 2021  doi: 10.3934/jimo.2021143
[20]

Juan C. Jara, Felipe Rivero. Asymptotic behaviour for prey-predator systems and logistic equations with unbounded time-dependent coefficients. Discrete & Continuous Dynamical Systems, 2014, 34 (10) : 4127-4137. doi: 10.3934/dcds.2014.34.4127

2020 Impact Factor: 1.081

Tools

Metrics

  • PDF downloads (334)
  • HTML views (292)
  • Cited by (6)

Other articles
by authors

[Back to Top]

Copyright © 2021 American Institute of Mathematical Sciences | Privacy Policy