doi: 10.3934/eect.2021010

Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling

1. 

IMAG, Univ. Montpellier, CNRS, Montpellier, France

2. 

Cadi Ayyad University, Sémlalia Faculty of Sciences, 40000 Marrakech, Morocco

Received  December 2020 Published  January 2021

In a Hilbert setting, we develop fast methods for convex unconstrained optimization. We rely on the asymptotic behavior of an inertial system combining geometric damping with temporal scaling. The convex function to minimize enters the dynamic via its gradient. The dynamic includes three coefficients varying with time, one is a viscous damping coefficient, the second is attached to the Hessian-driven damping, the third is a time scaling coefficient. We study the convergence rate of the values under general conditions involving the damping and the time scale coefficients. The obtained results are based on a new Lyapunov analysis and they encompass known results on the subject. We pay particular attention to the case of an asymptotically vanishing viscous damping, which is directly related to the accelerated gradient method of Nesterov. The Hessian-driven damping significantly reduces the oscillatory aspects. We obtain an exponential rate of convergence of values without assuming the strong convexity of the objective function. The temporal discretization of these dynamics opens the gate to a large class of inertial optimization algorithms.

Citation: 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, doi: 10.3934/eect.2021010
References:
[1]

F. Alvarez, On the minimizing property of a second-order dissipative system in Hilbert spaces, SIAM J. Control Optim., 38 (2000), 1102-1119.  doi: 10.1137/S0363012998335802.  Google Scholar

[2]

F. AlvarezH. AttouchJ. Bolte and P. Redont, A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics, J. Math. Pures Appl. (9), 81 (2002), 747-779.  doi: 10.1016/S0021-7824(01)01253-3.  Google Scholar

[3]

V. ApidopoulosJ.-F. Aujol and C. Dossal, Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule, Math. Program., 180 (2020), 137-156.  doi: 10.1007/s10107-018-1350-9.  Google Scholar

[4]

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

[5]

H. Attouch and A. Cabot, Convergence rates of inertial forward-backward algorithms, SIAM J. Optim., 28 (2018), 849-874.  doi: 10.1137/17M1114739.  Google Scholar

[6]

H. AttouchA. CabotZ. Chbani and H. Riahi, Inertial forward-backward algorithms with perturbations: Application to Tikhonov regularization, J. Optim. Theory Appl., 179 (2018), 1-36.  doi: 10.1007/s10957-018-1369-3.  Google Scholar

[7]

H. AttouchA. CabotZ. Chbani and H. Riahi, Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient, Evol. Equ. Control Theory, 7 (2018), 353-371.  doi: 10.3934/eect.2018018.  Google Scholar

[8]

H. Attouch, Z. Chbani, J. Fadili and H. Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, Math. Program., (2020). doi: 10.1007/s10107-020-01591-1.  Google Scholar

[9]

H. AttouchZ. ChbaniJ. Peypouquet and P. Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Math. Program., 168 (2018), 123-175.  doi: 10.1007/s10107-016-0992-8.  Google Scholar

[10]

H. AttouchZ. Chbani and H. Riahi, Convergence rates of inertial proximal algorithms with general extrapolation and proximal coefficients, Vietnam J. Math., 48 (2020), 247-276.  doi: 10.1007/s10013-020-00399-y.  Google Scholar

[11]

H. Attouch, Z. Chbani and H. Riahi, Fast convex optimization via time scaling of damped inertial gradient dynamics, Pure Appl. Functional Anal., to appear. Google Scholar

[12]

H. AttouchZ. Chbani and H. Riahi, Fast proximal methods via time scaling of damped inertial dynamics, SIAM J. Optim., 29 (2019), 2227-2256.  doi: 10.1137/18M1230207.  Google Scholar

[13]

H. Attouch, Z. Chbani and H. Riahi, Rate of convergence of the Nesterov accelerated gradient method in the subcritical case $\alpha \leq3$, ESAIM Control Optim. Calc. Var., 25 (2019), 34pp. doi: 10.1051/cocv/2017083.  Google Scholar

[14]

H. AttouchX. Goudou and P. Redont, The heavy ball with friction method. I. The continuous dynamical system: Global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system, Commun. Contemp. Math., 2 (2000), 1-34.  doi: 10.1142/S0219199700000025.  Google Scholar

[15]

H. Attouch and S. C. László, Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators, SIAM J. Optim., 30 (2020), 3252-3283.  doi: 10.1137/20M1333316.  Google Scholar

[16]

H. Attouch and J. Peypouquet, The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$, SIAM J. Optim., 26 (2016), 1824-1834.  doi: 10.1137/15M1046095.  Google Scholar

[17]

H. AttouchJ. Peypouquet and P. Redont, Fast convex optimization via inertial dynamics with Hessian driven damping, J. Differential Equations, 261 (2016), 5734-5783.  doi: 10.1016/j.jde.2016.08.020.  Google Scholar

[18]

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

[19]

R. I. Boţ 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

[20]

R. I. BoţE. R. Csetnek and S. C. László, Approaching nonsmooth nonconvex minimization through second-order proximal-gradient dynamical systems, J. Evol. Equ., 18 (2018), 1291-1318.  doi: 10.1007/s00028-018-0441-7.  Google Scholar

[21]

R. I. Boţ, E. R. Csetnek and S. C. László, Tikhonov regularization of a second order dynamical system with Hessian damping, Math. Program., (2020). doi: 10.1007/s10107-020-01528-8.  Google Scholar

[22]

O. Güler, New proximal point algorithms for convex minimization, SIAM J. Optim., 2 (1992), 649-664.  doi: 10.1137/0802032.  Google Scholar

[23]

O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29 (1991), 403-419.  doi: 10.1137/0329022.  Google Scholar

[24]

A. Haraux, Systèmes Dynamiques Dissipatifs et Applications, Recherches en Mathématiques Appliquées, 17, Masson, Paris, 1991.  Google Scholar

[25]

A. Haraux and M. A. Jendoubi, The Convergence Problem for Dissipative Autonomous Systems. Classical Methods and Recent Advances, SpringerBriefs in Mathematics, BCAM SpringerBriefs, Springer, Cham; BCAM Basque Center for Applied Mathematics, Bilbao, 2015. doi: 10.1007/978-3-319-23407-6.  Google Scholar

[26]

R. May, Asymptotic for a second-order evolution equation with convex potential and vanishing damping term, Turkish J. Math., 41 (2017), 681-685.  doi: 10.3906/mat-1512-28.  Google Scholar

[27]

Y. Nesterov, A method of solving a convex programming problem with convergence rate $\mathcal O(1/k2)$, Soviet Math. Doklady, 27 (1983), 372-376.   Google Scholar

[28]

Y. Nesterov, Introductory Lectures on Convex Optimization. A Basic Course, Applied Optimization, 87, Kluwer Academic Publishers, Boston, MA, 2004. doi: 10.1007/978-1-4419-8853-9.  Google Scholar

[29]

J. Peypouquet and S. Sorin, Evolution equations for maximal monotone operators: Asymptotic analysis in continuous and discrete time, J. Convex Anal., 17 (2010), 1113-1163.   Google Scholar

[30]

B. T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys., 4 (1964), 1-17.  doi: 10.1016/0041-5553(64)90137-5.  Google Scholar

[31]

B. Shi, S. S. Du, M. I. Jordan and W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, preprint, arXiv: 1810.08907. Google Scholar

[32]

J. W. Siegel, Accelerated first-order methods: Differential equations and Lyapunov functions, preprint, arXiv: 1903.05671v1. Google Scholar

[33]

W. Su, S. Boyd and E. J. Candès, A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 17 (2016), 43pp.  Google Scholar

show all references

References:
[1]

F. Alvarez, On the minimizing property of a second-order dissipative system in Hilbert spaces, SIAM J. Control Optim., 38 (2000), 1102-1119.  doi: 10.1137/S0363012998335802.  Google Scholar

[2]

F. AlvarezH. AttouchJ. Bolte and P. Redont, A second-order gradient-like dissipative dynamical system with Hessian-driven damping. Application to optimization and mechanics, J. Math. Pures Appl. (9), 81 (2002), 747-779.  doi: 10.1016/S0021-7824(01)01253-3.  Google Scholar

[3]

V. ApidopoulosJ.-F. Aujol and C. Dossal, Convergence rate of inertial forward-backward algorithm beyond Nesterov's rule, Math. Program., 180 (2020), 137-156.  doi: 10.1007/s10107-018-1350-9.  Google Scholar

[4]

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

[5]

H. Attouch and A. Cabot, Convergence rates of inertial forward-backward algorithms, SIAM J. Optim., 28 (2018), 849-874.  doi: 10.1137/17M1114739.  Google Scholar

[6]

H. AttouchA. CabotZ. Chbani and H. Riahi, Inertial forward-backward algorithms with perturbations: Application to Tikhonov regularization, J. Optim. Theory Appl., 179 (2018), 1-36.  doi: 10.1007/s10957-018-1369-3.  Google Scholar

[7]

H. AttouchA. CabotZ. Chbani and H. Riahi, Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient, Evol. Equ. Control Theory, 7 (2018), 353-371.  doi: 10.3934/eect.2018018.  Google Scholar

[8]

H. Attouch, Z. Chbani, J. Fadili and H. Riahi, First-order optimization algorithms via inertial systems with Hessian driven damping, Math. Program., (2020). doi: 10.1007/s10107-020-01591-1.  Google Scholar

[9]

H. AttouchZ. ChbaniJ. Peypouquet and P. Redont, Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity, Math. Program., 168 (2018), 123-175.  doi: 10.1007/s10107-016-0992-8.  Google Scholar

[10]

H. AttouchZ. Chbani and H. Riahi, Convergence rates of inertial proximal algorithms with general extrapolation and proximal coefficients, Vietnam J. Math., 48 (2020), 247-276.  doi: 10.1007/s10013-020-00399-y.  Google Scholar

[11]

H. Attouch, Z. Chbani and H. Riahi, Fast convex optimization via time scaling of damped inertial gradient dynamics, Pure Appl. Functional Anal., to appear. Google Scholar

[12]

H. AttouchZ. Chbani and H. Riahi, Fast proximal methods via time scaling of damped inertial dynamics, SIAM J. Optim., 29 (2019), 2227-2256.  doi: 10.1137/18M1230207.  Google Scholar

[13]

H. Attouch, Z. Chbani and H. Riahi, Rate of convergence of the Nesterov accelerated gradient method in the subcritical case $\alpha \leq3$, ESAIM Control Optim. Calc. Var., 25 (2019), 34pp. doi: 10.1051/cocv/2017083.  Google Scholar

[14]

H. AttouchX. Goudou and P. Redont, The heavy ball with friction method. I. The continuous dynamical system: Global exploration of the local minima of a real-valued function by asymptotic analysis of a dissipative dynamical system, Commun. Contemp. Math., 2 (2000), 1-34.  doi: 10.1142/S0219199700000025.  Google Scholar

[15]

H. Attouch and S. C. László, Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators, SIAM J. Optim., 30 (2020), 3252-3283.  doi: 10.1137/20M1333316.  Google Scholar

[16]

H. Attouch and J. Peypouquet, The rate of convergence of Nesterov's accelerated forward-backward method is actually faster than $1/k^2$, SIAM J. Optim., 26 (2016), 1824-1834.  doi: 10.1137/15M1046095.  Google Scholar

[17]

H. AttouchJ. Peypouquet and P. Redont, Fast convex optimization via inertial dynamics with Hessian driven damping, J. Differential Equations, 261 (2016), 5734-5783.  doi: 10.1016/j.jde.2016.08.020.  Google Scholar

[18]

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

[19]

R. I. Boţ 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

[20]

R. I. BoţE. R. Csetnek and S. C. László, Approaching nonsmooth nonconvex minimization through second-order proximal-gradient dynamical systems, J. Evol. Equ., 18 (2018), 1291-1318.  doi: 10.1007/s00028-018-0441-7.  Google Scholar

[21]

R. I. Boţ, E. R. Csetnek and S. C. László, Tikhonov regularization of a second order dynamical system with Hessian damping, Math. Program., (2020). doi: 10.1007/s10107-020-01528-8.  Google Scholar

[22]

O. Güler, New proximal point algorithms for convex minimization, SIAM J. Optim., 2 (1992), 649-664.  doi: 10.1137/0802032.  Google Scholar

[23]

O. Güler, On the convergence of the proximal point algorithm for convex minimization, SIAM J. Control Optim., 29 (1991), 403-419.  doi: 10.1137/0329022.  Google Scholar

[24]

A. Haraux, Systèmes Dynamiques Dissipatifs et Applications, Recherches en Mathématiques Appliquées, 17, Masson, Paris, 1991.  Google Scholar

[25]

A. Haraux and M. A. Jendoubi, The Convergence Problem for Dissipative Autonomous Systems. Classical Methods and Recent Advances, SpringerBriefs in Mathematics, BCAM SpringerBriefs, Springer, Cham; BCAM Basque Center for Applied Mathematics, Bilbao, 2015. doi: 10.1007/978-3-319-23407-6.  Google Scholar

[26]

R. May, Asymptotic for a second-order evolution equation with convex potential and vanishing damping term, Turkish J. Math., 41 (2017), 681-685.  doi: 10.3906/mat-1512-28.  Google Scholar

[27]

Y. Nesterov, A method of solving a convex programming problem with convergence rate $\mathcal O(1/k2)$, Soviet Math. Doklady, 27 (1983), 372-376.   Google Scholar

[28]

Y. Nesterov, Introductory Lectures on Convex Optimization. A Basic Course, Applied Optimization, 87, Kluwer Academic Publishers, Boston, MA, 2004. doi: 10.1007/978-1-4419-8853-9.  Google Scholar

[29]

J. Peypouquet and S. Sorin, Evolution equations for maximal monotone operators: Asymptotic analysis in continuous and discrete time, J. Convex Anal., 17 (2010), 1113-1163.   Google Scholar

[30]

B. T. Polyak, Some methods of speeding up the convergence of iteration methods, USSR Comput. Math. Math. Phys., 4 (1964), 1-17.  doi: 10.1016/0041-5553(64)90137-5.  Google Scholar

[31]

B. Shi, S. S. Du, M. I. Jordan and W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, preprint, arXiv: 1810.08907. Google Scholar

[32]

J. W. Siegel, Accelerated first-order methods: Differential equations and Lyapunov functions, preprint, arXiv: 1903.05671v1. Google Scholar

[33]

W. Su, S. Boyd and E. J. Candès, A differential equation for modeling Nesterov's accelerated gradient method: Theory and insights, J. Mach. Learn. Res., 17 (2016), 43pp.  Google Scholar

Figure 1.  $ t \mapsto f (x(t)) - \min f $ for solutions of (51), (52), $ f(x_1,x_2) = \frac12\left(x_1^2+x_2^2\right)-\ln(x_1x_2) $
Figure 2.  Convergence rate of $ f(x(t))-\min f $ for instances of Theorem 2.1 and general $ f $
Figure 3.  Evolution of $ f (x(t)) - \min f $ for systems in Figure 2, and $ f(x_1,x_2) = \frac12\left(x_1^2+10^3x_2^2\right) $
[1]

Hong Seng Sim, Wah June Leong, Chuei Yee Chen, Siti Nur Iqmal Ibrahim. Multi-step spectral gradient methods with modified weak secant relation for large scale unconstrained optimization. Numerical Algebra, Control & Optimization, 2018, 8 (3) : 377-387. doi: 10.3934/naco.2018024

[2]

Min Li. A three term Polak-Ribière-Polyak conjugate gradient method close to the memoryless BFGS quasi-Newton method. Journal of Industrial & Management Optimization, 2020, 16 (1) : 245-260. doi: 10.3934/jimo.2018149

[3]

Tuan Hiep Pham, Jérôme Laverne, Jean-Jacques Marigo. Stress gradient effects on the nucleation and propagation of cohesive cracks. Discrete & Continuous Dynamical Systems - S, 2016, 9 (2) : 557-584. doi: 10.3934/dcdss.2016012

[4]

Matthias Erbar, Jan Maas. Gradient flow structures for discrete porous medium equations. Discrete & Continuous Dynamical Systems - A, 2014, 34 (4) : 1355-1374. doi: 10.3934/dcds.2014.34.1355

[5]

Kin Ming Hui, Soojung Kim. Asymptotic large time behavior of singular solutions of the fast diffusion equation. Discrete & Continuous Dynamical Systems - A, 2017, 37 (11) : 5943-5977. doi: 10.3934/dcds.2017258

[6]

Andrea Cianchi, Adele Ferone. Improving sharp Sobolev type inequalities by optimal remainder gradient norms. Communications on Pure & Applied Analysis, 2012, 11 (3) : 1363-1386. doi: 10.3934/cpaa.2012.11.1363

[7]

Paula A. González-Parra, Sunmi Lee, Leticia Velázquez, Carlos Castillo-Chavez. A note on the use of optimal control on a discrete time model of influenza dynamics. Mathematical Biosciences & Engineering, 2011, 8 (1) : 183-197. doi: 10.3934/mbe.2011.8.183

[8]

Mohsen Abdolhosseinzadeh, Mir Mohammad Alipour. Design of experiment for tuning parameters of an ant colony optimization method for the constrained shortest Hamiltonian path problem in the grid networks. Numerical Algebra, Control & Optimization, 2021, 11 (2) : 321-332. doi: 10.3934/naco.2020028

[9]

Xiaomao Deng, Xiao-Chuan Cai, Jun Zou. A parallel space-time domain decomposition method for unsteady source inversion problems. Inverse Problems & Imaging, 2015, 9 (4) : 1069-1091. doi: 10.3934/ipi.2015.9.1069

[10]

Alessandro Gondolo, Fernando Guevara Vasquez. Characterization and synthesis of Rayleigh damped elastodynamic networks. Networks & Heterogeneous Media, 2014, 9 (2) : 299-314. doi: 10.3934/nhm.2014.9.299

[11]

Jan Prüss, Laurent Pujo-Menjouet, G.F. Webb, Rico Zacher. Analysis of a model for the dynamics of prions. Discrete & Continuous Dynamical Systems - B, 2006, 6 (1) : 225-235. doi: 10.3934/dcdsb.2006.6.225

[12]

Simone Calogero, Juan Calvo, Óscar Sánchez, Juan Soler. Dispersive behavior in galactic dynamics. Discrete & Continuous Dynamical Systems - B, 2010, 14 (1) : 1-16. doi: 10.3934/dcdsb.2010.14.1

[13]

Joel Fotso Tachago, Giuliano Gargiulo, Hubert Nnang, Elvira Zappale. Multiscale homogenization of integral convex functionals in Orlicz Sobolev setting. Evolution Equations & Control Theory, 2021, 10 (2) : 297-320. doi: 10.3934/eect.2020067

[14]

Xianming Liu, Guangyue Han. A Wong-Zakai approximation of stochastic differential equations driven by a general semimartingale. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2499-2508. doi: 10.3934/dcdsb.2020192

[15]

Olena Naboka. On synchronization of oscillations of two coupled Berger plates with nonlinear interior damping. Communications on Pure & Applied Analysis, 2009, 8 (6) : 1933-1956. doi: 10.3934/cpaa.2009.8.1933

[16]

Andrea Tosin, Mattia Zanella. Uncertainty damping in kinetic traffic models by driver-assist controls. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021018

[17]

Juan Manuel Pastor, Javier García-Algarra, Javier Galeano, José María Iriondo, José J. Ramasco. A simple and bounded model of population dynamics for mutualistic networks. Networks & Heterogeneous Media, 2015, 10 (1) : 53-70. doi: 10.3934/nhm.2015.10.53

[18]

Eduardo Casas, Christian Clason, Arnd Rösch. Preface special issue on system modeling and optimization. Mathematical Control & Related Fields, 2021  doi: 10.3934/mcrf.2021008

[19]

Bin Pei, Yong Xu, Yuzhen Bai. Convergence of p-th mean in an averaging principle for stochastic partial differential equations driven by fractional Brownian motion. Discrete & Continuous Dynamical Systems - B, 2020, 25 (3) : 1141-1158. doi: 10.3934/dcdsb.2019213

[20]

Xiaohu Wang, Dingshi Li, Jun Shen. Wong-Zakai approximations and attractors for stochastic wave equations driven by additive noise. Discrete & Continuous Dynamical Systems - B, 2021, 26 (5) : 2829-2855. doi: 10.3934/dcdsb.2020207

2019 Impact Factor: 0.953

Metrics

  • PDF downloads (26)
  • HTML views (79)
  • Cited by (0)

[Back to Top]