Publication Cover
Applicable Analysis
An International Journal
Volume 102, 2023 - Issue 15
166
Views
3
CrossRef citations to date
0
Altmetric
Articles

Inertial primal-dual dynamics with damping and scaling for linearly constrained convex optimization problems

ORCID Icon, &
Pages 4114-4139 | Received 13 Apr 2022, Accepted 15 Jul 2022, Published online: 26 Jul 2022

References

  • Chen G, Yang Q, Song Y, et al. A distributed continuous-time algorithm for nonsmooth constrained optimization. IEEE Trans Automat Control. 2020;65(11):4914–4921.
  • Su W, Boyd S, Candès EJ. A differential equation for modeling Nesterov's accelerated gradient method: theory and insights. J Mach Learn Res. 2016;17(1):5312–5354.
  • Zeng X, Lei J, Chen J. Dynamical primal-dual accelerated method with applications to network optimization. IEEE Trans Automat Control. 2022. DOI: 10.1109/TAC.2022.3152720.
  • Boyd S, Parikh N, Chu E, et al. Distributed optimization and statistical learning via the alternating direction method of multipliers. Found Trends Mach Learn. 2010;3:1–122.
  • Lin Z, Li H, Fang C. Accelerated optimization for machine learning. Singapore: Springer; 2020.
  • He X, Hu R, Fang YP. Inertial accelerated primal-dual methods for linear equality constrained convex optimization problems. Numer Algor. 2022. DOI: 10.1007/s11075-021-01246-y.
  • He B, Ma F, Yuan X. Optimal proximal augmented Lagrangian method and its application to full Jacobian splitting for multi-block separable convex minimization problems. IMA J Numer Anal. 2020;40(2):1188–1216.
  • He B, Yuan X, Zhang W. A customized proximal point algorithm for convex minimization with linear constraints. Comput Optim Appl. 2013;56(3):559–572.
  • Attouch H, Cabot A. Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity. J Differ Equ. 2017;263(9):5412–5458.
  • Cabot A, Engler H, Gadat S. On the long time behavior of second order differential equations with asymptotically small dissipation. Trans Amer Math Soc. 2009;361(11):5983–6017.
  • Attouch H, Chbani Z, Riahi H. Fast proximal methods via time scaling of damped inertial dynamics. SIAM J Optim. 2019;29(3):2227–2256.
  • Nesterov Y. Introductory lectures on convex optimization: a basic course. Vol. 87. New York: Springer Science & Business Media; 2013.
  • Liu L, Chao SY, Yao JC. Convergence analysis of an inertial Tseng's extragradient algorithm for solving pseudomonotone variational inequalities and applications. J Nonlinear Var Anal. 2021;5:627–644.
  • Zhao X, Köbis MA, Yao Y, et al. A projected subgradient method for nondifferentiable quasiconvex multiobjective optimization problems. J Optim Theory Appl. 2021;190(1):82–107.
  • Wibisono A, Wilson AC, Jordan MI. A variational perspective on accelerated methods in optimization. Proc Natl Acad Sci USA. 2016;113(47):E7351–E7358.
  • Attouch H, Chbani Z, Fadili J, et al. Fast convergence of dynamical ADMM via time scaling of damped inertial dynamics. J Optim Theory Appl. 2022;193:704–736.
  • Boţ BI, Csetnek ER, Nguyen DK. Fast augmented Lagrangian method in the convex regime with convergence guarantees for the iterates. preprint 2021. Available from: arXiv: 2111.09370.
  • He X, Hu R, Fang YP. Fast primal-dual algorithm via dynamical system for a linearly constrained convex optimization problem. Automatica. preprint 2021. to appear. Available from: arXiv:2103.10118.
  • He X, Hu R, Fang YP. Convergence rates of inertial primal-dual dynamical methods for separable convex optimization problems. SIAM J Control Optim. 2021;59(5):3278–3301.
  • He X, Hu R, Fang YP. “Second-order primal”+“first-order dual” dynamical systems with time scaling for linear equality constrained convex optimization problems. IEEE Trans Automat Control. 2022; DOI: 10.1109/TAC.2022.3176527.
  • Polyak BT. Some methods of speeding up the convergence of iteration methods. USSR Comput Math Math Phys. 1964;4(5):1–17.
  • Alvarez F. On the minimizing property of a second order dissipative system in Hilbert spaces. SIAM J Control Optim. 2000;38(4):1102–1119.
  • Bégout P, Bolte J, Jendoubi MA. On damped second-order gradient systems. J Differ Equ. 2015;259(7):3115–3143.
  • Sun T, Yin P, Li D, et al. Non-ergodic convergence analysis of heavy-ball algorithms. The Thirty-Third AAAI Conference on Artificial Intelligence; 2019. Vol. 33, no. 1, p. 5033–5040.
  • Haraux A, Jendoubi MA. On a second order dissipative ODE in Hilbert space with an integrable source term. Acta Math Sci. 2012;32(1):155–163.
  • Cabot A, Frankel P. Asymptotics for some semilinear hyperbolic equations with non-autonomous damping. J Differ Equ. 2012;252(1):294–322.
  • May R. Long time behavior for a semilinear hyperbolic equation with asymptotically vanishing damping term and convex potential. J Math Anal Appl. 2015;430(1):410–416.
  • Jendoubi MA, May R. Asymptotics for a second-order differential equation with nonautonomous damping and an integrable source term. Appl Anal. 2015;94(2):435–443.
  • Balti M, May R. Asymptotic for the perturbed heavy ball system with vanishing damping term. Evol Equ Control Theory. 2017;6(2):177–186.
  • Sebbouh O, Dossal C, Rondepierre A. Convergence rates of damped inertial dynamics under geometric conditions and perturbations. SIAM J Optim. 2020;30(3):1850–1877.
  • Beck A, Teboulle M. A fast iterative shrinkage-thresholding algorithm for linear inverse problems. SIAM J Imaging Sci. 2009;2(1):183–202.
  • Nesterov Y. A method of solving a convex programming problem with convergence rate O(1/k2). InSov Math Dokl. 1983;27(2):372–376.
  • Attouch H, Chbani Z, Peypouquet J, et al. Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Math Program. 2018;168(1–2):123–175.
  • May R. Asymptotic for a second-order evolution equation with convex potential and vanishing damping term. Turkish J Math. 2017;41(3):681–785.
  • Attouch H, Chbani Z, Riahi H. Rate of convergence of the Nesterov accelerated gradient method in the subcritical case α≤3. ESAIM: Control Optim Calc Var. 2019;2:25.
  • Vassilis A, Jean-François A, Charles D. The differential inclusion modeling FISTA algorithm and optimality of convergence rate in the case b≤3. SIAM J Optim. 2018;28(1):551–574.
  • Aujol JF, Dossal C, Rondepierre A. Optimal convergence rates for Nesterov acceleration. SIAM J Optim. 2019;29(4):3131–3153.
  • Lin T, Jordan MI. A control-theoretic perspective on optimal high-order optimization. Math Program. 2021; DOI: 10.1007/s10107-021-01721-3.
  • Attouch H, Cabot A, Chbani Z, et al. Rate of convergence of inertial gradient dynamics with time-dependent viscous damping coefficient. Evol Equ Control Theor. 2018;7(3):353–371.
  • Balhag A, Chbani Z, Riahi H. Linear convergence of inertial gradient dynamics with constant viscous damping coefficient and time-dependent rescaling parameter. preprint 2020. Available From: Hal:hal-02610699.
  • Fazlyab M, Koppel A, Preciado VM, et al. A variational approach to dual methods for constrained convex optimization. 2017 American Control Conference (ACC); 2017. p. 5269–5275.
  • Attouch H, Balhag A, Chbani Z, et al. Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling. Evol Equ Control Theory. 2022;11(2):487–514.
  • Attouch H, Chbani Z, Riahi H. Fast convex optimization via time scaling of damped inertial gradient dynamics. Pure Appl Funct Anal. 2019;6(6):1081–1117.
  • Boţ RI, Csetnek ER. Second order forward-backward dynamical systems for monotone inclusion problems. SIAM J Control Optim. 2016;54(3):1423–1443.
  • Wilson AC, Recht B, Jordan MI. A Lyapunov analysis of accelerated methods in optimization. J Mach Learn Res. 2021;22(113):1–34.
  • Boţ RI, Csetnek ER, László SC. A primal-dual dynamical approach to structured convex minimization problems. J Differ Equ. 2020;269(12):10717–10757.
  • Chen X, Li N. Exponential stability of primal-dual gradient dynamics with non-strong convexity. 2020 American Control Conference (ACC); 2020. p. 1612–1618.
  • Luo H. A primal-dual flow for affine constrained convex optimization. ESAIM: Control Optim Calc Var. 2022;33:28.
  • Qu G, Li N. On the exponential stability of primal-dual gradient dynamics. IEEE Contr Syst Lett. 2018;3(1):43–48.
  • Zhang C, Zhu Z, Yao Y, et al. Homotopy method for solving mathematical programs with bounded box-constrained variational inequalities. Optimization. 2019;68(12):2297–2316.
  • Boţ RI, Nguyen DK. Improved convergence rates and trajectory convergence for primal-dual dynamical systems with vanishing damping. J Differ Equ. 2021;303:369–406.
  • Ghadimi E, Feyzmahdavian HR, Johansson M. Global convergence of the heavy-ball method for convex optimization. 2015 European Control Conference (ECC); 2015. p. 310–315.
  • Brezis H. Operateurs maximaux monotones et semi-groupes de contractions dans les espaces de Hilbert. New York (NY): North-Holland/Elsevier; 1973 (North-Holl. Math. Stud.; 5).

Reprints and Corporate Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

To request a reprint or corporate permissions for this article, please click on the relevant link below:

Academic Permissions

Please note: Selecting permissions does not provide access to the full text of the article, please see our help page How do I view content?

Obtain permissions instantly via Rightslink by clicking on the button below:

If you are unable to obtain permissions via Rightslink, please complete and submit this Permissions form. For more information, please visit our Permissions help page.