April  2022, 11(2): 487-514. 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  April 2022 Early access  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 and Control Theory, 2022, 11 (2) : 487-514. 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.

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

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

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

[5]

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

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

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

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

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

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

[11]

H. Attouch, Z. Chbani and H. Riahi, Fast convex optimization via time scaling of damped inertial gradient dynamics, Pure Appl. Functional Anal., 6 (2021).

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

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

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

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

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

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

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

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

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

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

[22]

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

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

[24]

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

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

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

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

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

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

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

[31]

B. Shi, S. S. Du, M. I. Jordan and W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, Math. Program., 2021 doi: 10.1007/s10107-021-01681-8.

[32]

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

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

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.

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

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

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

[5]

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

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

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

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

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

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

[11]

H. Attouch, Z. Chbani and H. Riahi, Fast convex optimization via time scaling of damped inertial gradient dynamics, Pure Appl. Functional Anal., 6 (2021).

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

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

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

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

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

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

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

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

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

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

[22]

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

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

[24]

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

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

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

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

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

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

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

[31]

B. Shi, S. S. Du, M. I. Jordan and W. J. Su, Understanding the acceleration phenomenon via high-resolution differential equations, Math. Program., 2021 doi: 10.1007/s10107-021-01681-8.

[32]

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

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

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]

Hedy Attouch, Alexandre Cabot, Zaki Chbani, Hassan Riahi. Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient. Evolution Equations and Control Theory, 2018, 7 (3) : 353-371. doi: 10.3934/eect.2018018

[2]

Igor Griva, Roman A. Polyak. Proximal point nonlinear rescaling method for convex optimization. Numerical Algebra, Control and Optimization, 2011, 1 (2) : 283-299. doi: 10.3934/naco.2011.1.283

[3]

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

[4]

Hai Huyen Dam, Siow Yong Low, Sven Nordholm. Two-level optimization approach with accelerated proximal gradient for objective measures in sparse speech reconstruction. Journal of Industrial and Management Optimization, 2021  doi: 10.3934/jimo.2021131

[5]

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

[6]

Hedy Attouch, Jalal Fadili, Vyacheslav Kungurtsev. On the effect of perturbations in first-order optimization methods with inertia and Hessian driven damping. Evolution Equations and Control Theory, 2022  doi: 10.3934/eect.2022022

[7]

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

[8]

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

[9]

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 and Management Optimization, 2017, 13 (4) : 1841-1857. doi: 10.3934/jimo.2017021

[10]

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

[11]

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

[12]

Xinqun Mei, Jundong Zhou. The interior gradient estimate of prescribed Hessian quotient curvature equation in the hyperbolic space. Communications on Pure and Applied Analysis, 2021, 20 (3) : 1187-1198. doi: 10.3934/cpaa.2021012

[13]

Xueyong Wang, Yiju Wang, Gang Wang. An accelerated augmented Lagrangian method for multi-criteria optimization problem. Journal of Industrial and Management Optimization, 2020, 16 (1) : 1-9. doi: 10.3934/jimo.2018136

[14]

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

[15]

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 and Management Optimization, 2021  doi: 10.3934/jimo.2021143

[16]

Yigui Ou, Haichan Lin. A class of accelerated conjugate-gradient-like methods based on a modified secant equation. Journal of Industrial and Management Optimization, 2020, 16 (3) : 1503-1518. doi: 10.3934/jimo.2019013

[17]

Predrag S. Stanimirović, Branislav Ivanov, Haifeng Ma, Dijana Mosić. A survey of gradient methods for solving nonlinear optimization. Electronic Research Archive, 2020, 28 (4) : 1573-1624. doi: 10.3934/era.2020115

[18]

Zhiyong Sun, Toshiharu Sugie. Identification of Hessian matrix in distributed gradient-based multi-agent coordination control systems. Numerical Algebra, Control and Optimization, 2019, 9 (3) : 297-318. doi: 10.3934/naco.2019020

[19]

Jianjun Zhang, Yunyi Hu, James G. Nagy. A scaled gradient method for digital tomographic image reconstruction. Inverse Problems and Imaging, 2018, 12 (1) : 239-259. doi: 10.3934/ipi.2018010

[20]

José Antonio Carrillo, Yanghong Huang, Francesco Saverio Patacchini, Gershon Wolansky. Numerical study of a particle method for gradient flows. Kinetic and Related Models, 2017, 10 (3) : 613-641. doi: 10.3934/krm.2017025

2020 Impact Factor: 1.081

Metrics

  • PDF downloads (435)
  • HTML views (527)
  • Cited by (0)

[Back to Top]