Monotone Inclusions, Acceleration, and Closed-Loop Control

References

• [1] Abbas B, Attouch H, Svaiter BF (2014) Newton-like dynamics and forward-backward methods for structured monotone inclusions in Hilbert spaces. J. Optim. Theory Appl. 161(2):331–360.Crossref, Google Scholar
• [2] Adly S, Attouch H (2020) Finite convergence of proximal-gradient inertial algorithms combining dry friction with Hessian-driven damping. SIAM J. Optim. 30(3):2134–2162.Crossref, Google Scholar
• [3] Adly S, Attouch H (2022) First-order inertial algorithms involving dry friction damping. Math. Programming 193(1):405–445.Crossref, Google Scholar
• [4] Alvarez F (2000) On the minimizing property of a second order dissipative system in Hilbert spaces. SIAM J. Control Optim. 38(4):1102–1119.Crossref, Google Scholar
• [5] Alvarez F, Attouch H (2001) An inertial proximal method for maximal monotone operators via discretization of a nonlinear oscillator with damping. Set-Valued Anal. 9(1):3–11.Crossref, Google Scholar
• [6] Alvarez F, Pérez JM (1998) A dynamical system associated with Newton’s method for parametric approximations of convex minimization problems. Appl. Math. Optim. 38(2):193–217.Crossref, Google Scholar
• [7] Alvarez F, Attouch H, Bolte J, Redont P (2002) A second-order gradient-like dissipative dynamical system with Hessian-driven damping: Application to optimization and mechanics. J. Math. Pures Appl. 81(8):747–779.Crossref, Google Scholar
• [8] Apidopoulos V, Aujol JF, Dossal C (2020) Convergence rate of inertial forward-backward algorithm beyond Nesterov’s rule. Math. Programming 180(1):137–156.Crossref, Google Scholar
• [9] Attouch H, Baillon JB (2018) Weak vs. strong convergence of a regularized Newton dynamic for maximal monotone operators. Vietnam J. Math. 46(1):177–195.Crossref, Google Scholar
• [10] Attouch H, Cabot A (2017) Asymptotic stabilization of inertial gradient dynamics with time-dependent viscosity. J. Differential Equations 263(9):5412–5458.Crossref, Google Scholar
• [11] Attouch H, Cabot A (2018) Convergence of damped inertial dynamics governed by regularized maximally monotone operators. J. Differential Equations 264(12):7138–7182.Crossref, Google Scholar
• [12] Attouch H, Cabot A (2020) Convergence of a relaxed inertial proximal algorithm for maximally monotone operators. Math. Programming 184(1):243–287.Crossref, Google Scholar
• [13] Attouch H, László SC (2020) Newton-like inertial dynamics and proximal algorithms governed by maximally monotone operators. SIAM J. Optim. 30(4):3252–3283.Crossref, Google Scholar
• [14] Attouch H, László SC (2021) Continuous Newton-like inertial dynamics for monotone inclusions. Set-Valued Variational Anal. 29(3):555–581.Crossref, Google Scholar
• [15] Attouch H, Maingé PE (2011) Asymptotic behavior of second-order dissipative evolution equations combining potential with non-potential effects. ESAIM Control Optim. Calculus Variations 17(3):836–857.Crossref, Google Scholar
• [16] Attouch H, Peypouquet J (2016) The rate of convergence of Nesterov’s accelerated forward-backward method is actually faster than 1/k^2. SIAM J. Optim. 26(3):1824–1834.Crossref, Google Scholar
• [17] Attouch H, Peypouquet J (2019) Convergence of inertial dynamics and proximal algorithms governed by maximally monotone operators. Math. Programming 174(1):391–432.Crossref, Google Scholar
• [18] Attouch H, Redont P (2001) The second-order in time continuous Newton method. Lassonde M, ed. Approximation, Optimization and Mathematical Economics (Physica, Heidelberg, Germany), 25–36.Crossref, Google Scholar
• [19] Attouch H, Svaiter BF (2011) A continuous dynamical Newton-like approach to solving monotone inclusions. SIAM J. Control Optim. 49(2):574–598.Crossref, Google Scholar
• [20] Attouch H, Alves MM, Svaiter BF (2016) A dynamic approach to a proximal-Newton method for monotone inclusions in Hilbert spaces, with complexity o (1/n2). J. Convex Anal. 23(1):139–180.Google Scholar
• [21] Attouch H, Boţ RI, Csetnek ER (2022) Fast optimization via inertial dynamics with closed-loop damping. J. Eur. Math. Soc., ePub ahead of print March 16, https://ems.press/journals/jems/articles/5016211.Crossref, Google Scholar
• [22] Attouch H, Chbani Z, Riahi H (2019) Fast proximal methods via time scaling of damped inertial dynamics. SIAM J. Optim. 29(3):2227–2256.Crossref, Google Scholar
• [23] Attouch H, Goudou X, Redont P (2000) 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. Comm. Contemporary Math. 2(01):1–34.Crossref, Google Scholar
• [24] Attouch H, Maingé PE, Redont P (2012) A second-order differential system with Hessian-driven damping: Application to non-elastic shock laws. Differential Equations Appl. 4(1):27–65.Crossref, Google Scholar
• [25] Attouch H, Peypouquet J, Redont P (2016) Fast convex optimization via inertial dynamics with Hessian driven damping. J. Differential Equations 261(10):5734–5783.Crossref, Google Scholar
• [26] Attouch H, Redont P, Svaiter BF (2013) Global convergence of a closed-loop regularized Newton method for solving monotone inclusions in Hilbert spaces. J. Optim. Theory Appl. 157(3):624–650.Crossref, Google Scholar
• [27] Attouch H, Balhag A, Chbani Z, Riahi H (2022) Fast convex optimization via inertial dynamics combining viscous and Hessian-driven damping with time rescaling. Evolution Equations Control Theory 11(2):487–514.Crossref, Google Scholar
• [28] Attouch H, Chbani Z, Fadili J, Riahi H (2022) First-order optimization algorithms via inertial systems with Hessian driven damping. Math. Programming 193(1):113–155.Crossref, Google Scholar
• [29] Attouch H, Chbani Z, Peypouquet J, Redont P (2018) Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity. Math. Programming 168(1–2):123–175.Crossref, Google Scholar
• [30] Baillon JB (1978) Un exemple concernant le comportement asymptotique de la solution du problème du dt+ ∂ϑ (μ) ∈ 0. J. Functional Anal. 28(3):369–376.Crossref, Google Scholar
• [31] Bauschke HH, Combettes PL (2001) A weak-to-strong convergence principle for Fejér-monotone methods in Hilbert spaces. Math. Oper. Res. 26(2):248–264.Link, Google Scholar
• [32] Bellman R (1943) The stability of solutions of linear differential equations. Duke Math. J. 10(4):643–647.Crossref, Google Scholar
• [33] Borwein J, Lewis AS (2010) Convex Analysis and Nonlinear Optimization: Theory and Examples (Springer Science & Business Media, Berlin).Google Scholar
• [34] Bose T, Meyer F (2003) Digital Signal and Image Processing (John Wiley & Sons, Inc., New York).Google Scholar
• [35] Bot RI, Csetnek ER (2016) Second order forward-backward dynamical systems for monotone inclusion problems. SIAM J. Control Optim. 54(3):1423–1443.Crossref, Google Scholar
• [36] Brézis H (1973) Operateurs Maximaux Monotones: Et semi-groupes de contractions dans les espaces de Hilbert (Elsevier, Amsterdam).Google Scholar
• [37] Brézis H (1978) Asymptotic behavior of some evolution systems. Crandall MG, ed. Nonlinear Evolution Equations (Elsevier, Amsterdam), 141–154.Google Scholar
• [38] Briceno-Arias LM, Combettes PL (2011) A monotone+ skew splitting model for composite monotone inclusions in duality. SIAM J. Optim. 21(4):1230–1250.Crossref, Google Scholar
• [39] Briceno-Arias LM, Davis D (2018) Forward-backward-half forward algorithm for solving monotone inclusions. SIAM J. Optim. 28(4):2839–2871.Crossref, Google Scholar
• [40] Bruck RE Jr (1977) On the weak convergence of an ergodic iteration for the solution of variational inequalities for monotone operators in Hilbert space. J. Math. Anal. Appl. 61(1):159–164.Crossref, Google Scholar
• [41] Bullins B, Lai KA (2022) Higher-order methods for convex-concave min-max optimization and monotone variational inequalities. SIAM J. Optim. 32(3):2208–2229.Crossref, Google Scholar
• [42] Cesa-Bianchi N, Lugosi G (2006) Prediction, Learning, and Games (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• [43] Coddington EA, Levinson N (1955) Theory of Ordinary Differential Equations (Tata McGraw-Hill Education, New York).Google Scholar
• [44] Combettes PL (2013) Systems of structured monotone inclusions: Duality, algorithms, and applications. SIAM J. Optim. 23(4):2420–2447.Crossref, Google Scholar
• [45] Combettes PL, Eckstein J (2018) Asynchronous block-iterative primal-dual decomposition methods for monotone inclusions. Math. Programming 168(1):645–672.Crossref, Google Scholar
• [46] Csetnek ER, Eberhard A, Tam MK (2021) Convergence rates for boundedly regular systems. Adv. Comput. Math. 47(5):1–18.Crossref, Google Scholar
• [47] Cui S, Shanbhag U, Staudigl M, Vuong P (2022) Stochastic relaxed inertial forward-backward-forward splitting for monotone inclusions in Hilbert spaces. Comput. Optim. Appl. 83(2):465–524.Crossref, Google Scholar
• [48] Davis D (2015) Convergence rate analysis of primal-dual splitting schemes. SIAM J. Optim. 25(3):1912–1943.Crossref, Google Scholar
• [49] Diakonikolas J (2020) Halpern iteration for near-optimal and parameter-free monotone inclusion and strong solutions to variational inequalities. Proc. Thirty Third Conf. Learn. Theory (PMLR), 1428–1451.Google Scholar
• [50] Diakonikolas J, Jordan MI (2021) Generalized momentum-based methods: A Hamiltonian perspective. SIAM J. Optim. 31(1):915–944.Crossref, Google Scholar
• [51] Diakonikolas J, Orecchia L (2019) The approximate duality gap technique: A unified theory of first-order methods. SIAM J. Optim. 29(1):660–689.Crossref, Google Scholar
• [52] Drusvyatskiy D, Lewis AS (2018) Error bounds, quadratic growth, and linear convergence of proximal methods. Math. Oper. Res. 43(3):919–948.Link, Google Scholar
• [53] Drusvyatskiy D, Ioffe AD, Lewis AS (2021) Nonsmooth optimization using taylor-like models: Error bounds, convergence, and termination criteria. Math. Programming 185(1):357–383.Crossref, Google Scholar
• [54] Eckstein J, Svaiter BF (2009) General projective splitting methods for sums of maximal monotone operators. SIAM J. Control Optim. 48(2):787–811.Crossref, Google Scholar
• [55] Facchinei F, Pang JS (2007) Finite-Dimensional Variational Inequalities and Complementarity Problems (Springer Science & Business Media, Berlin).Google Scholar
• [56] Farahani RZ, Hekmatfar M (2009) Facility Location: Concepts, Models, Algorithms and Case Studies (Springer Science & Business Media, Berlin).Crossref, Google Scholar
• [57] França G, Jordan MI, Vidal R (2021) On dissipative symplectic integration with applications to gradient-based optimization. J. Statist. Mech. Theory Experiment 2021(4):043402.Crossref, Google Scholar
• [58] Gasnikov A, Dvurechensky P, Gorbunov E, Vorontsova E, Selikhanovych D, Uribe CA, Jiang B, Wang H, Zhang S, Bubeck S, Jiang Q, Lee YT, Li Y, Sidford A (2019) Near optimal methods for minimizing convex functions with Lipschitz p-th derivatives. Proc. Thirty-Second Conf. Learn. Theory (PMLR), 1392–1393.Google Scholar
• [59] Goebel K, Kirk WA (1990) Topics in Metric Fixed Point Theory (Cambridge University Press, Cambridge, United Kingdom).Crossref, Google Scholar
• [60] Golowich N, Pattathil S, Daskalakis C (2020) Tight last-iterate convergence rates for no-regret learning in multi-player games. NeurIPS, 20766–20778.Google Scholar
• [61] Goodfellow I, Pouget-Abadie J, Mirza M, Xu B, Warde-Farley D, Ozair S, Courville A, Bengio Y (2014) Generative adversarial nets. NIPS, 2672–2680.Google Scholar
• [62] Gronwall TH (1919) Note on the derivatives with respect to a parameter of the solutions of a system of differential equations. Ann. Math. 20(4):292–296.Crossref, Google Scholar
• [63] Güler O (1991) On the convergence of the proximal point algorithm for convex minimization. SIAM J. Control Optim. 29(2):403–419.Crossref, Google Scholar
• [64] Güler O (1992) New proximal point algorithms for convex minimization. SIAM J. Optim. 2(4):649–664.Crossref, Google Scholar
• [65] Karamardian S (1972) The complementarity problem. Math. Programming 2(1):107–129.Crossref, Google Scholar
• [66] Kelley CT (1995) Iterative Methods for Linear and Nonlinear Equations (SIAM, Philadelphia).Crossref, Google Scholar
• [67] Kim D (2021) Accelerated proximal point method for maximally monotone operators. Math. Programming 190(1):57–87.Crossref, Google Scholar
• [68] Lemaire B (1996) An asymptotical variational principle associated with the steepest descent method for a convex function. J. Convex Anal. 3:63–70.Google Scholar
• [69] Lewis AS, Pang JS (1998) Error bounds for convex inequality systems. Crouzeix JP, Martinez-Legaz JE, Volle M, eds. Generalized Convexity, Generalized Monotonicity: Recent Results, Nonconvex Optimization and Its Applications, vol. 27 (Springer, Boston), 75–110.Crossref, Google Scholar
• [70] Lin T, Jordan MI (2022) A control-theoretic perspective on optimal high-order optimization. Math. Programming 195(1):929–975.Crossref, Google Scholar
• [71] Lions PL (1978) Une méthode itérative de résolution d’une inéquation variationnelle. Israel J. Math. 31(2):204–208.Crossref, Google Scholar
• [72] Maingé PE (2013) First-order continuous Newton-like systems for monotone inclusions. SIAM J. Control Optim. 51(2):1615–1638.Crossref, Google Scholar
• [73] Martinet B (1970) Regularisation d’inequations variationelles par approximations successives. Revue Francaise d’Informatique et de Recherche Operationelle. 4(R3):154–159.Google Scholar
• [74] Martinet B (1972) Détermination approchée d’un point fixe d’une application pseudo-contractante. C. R. Acad. Sci. Paris 274(2):163–165.Google Scholar
• [75] Monteiro RDC, Svaiter BF (2010) On the complexity of the hybrid proximal extragradient method for the iterates and the ergodic mean. SIAM J. Optim. 20(6):2755–2787.Crossref, Google Scholar
• [76] Monteiro RDC, Svaiter BF (2011) Complexity of variants of Tseng’s modified FB splitting and Korpelevich’s methods for hemivariational inequalities with applications to saddle-point and convex optimization problems. SIAM J. Optim. 21(4):1688–1720.Crossref, Google Scholar
• [77] Monteiro RDC, Svaiter BF (2012) Iteration-complexity of a Newton proximal extragradient method for monotone variational inequalities and inclusion problems. SIAM J. Optim. 22(3):914–935.Crossref, Google Scholar
• [78] Monteiro RDC, Svaiter BF (2013) An accelerated hybrid proximal extragradient method for convex optimization and its implications to second-order methods. SIAM J. Optim. 23(2):1092–1125.Crossref, Google Scholar
• [79] Muehlebach M, Jordan MI (2021) Optimization with momentum: Dynamical, control-theoretic, and symplectic perspectives. J. Machine Learn. Res. 22(73):1–50.Google Scholar
• [80] Nemirovski AS (1981) Effective iterative methods for solving equations with monotone operators. Ekon. Mat. Metody 17(2):344–359.Google Scholar
• [81] Nemirovski A (2004) Prox-method with rate of convergence o(1/t) for variational inequalities with Lipschitz continuous monotone operators and smooth convex-concave saddle point problems. SIAM J. Optim. 15(1):229–251.Crossref, Google Scholar
• [82] Nemirovski AS, Yudin DB (1978) Cesari convergence of the gradient method of approximating saddle points of convex-concave functions. Dokl. Akad. Nauk. 239(5):1056–1059.Google Scholar
• [83] Nesterov Y (1983) A method for solving the convex programming problem with convergence rate O (1/k2). Dokl. Akad. Nauk SSSR 269:543–547.Google Scholar
• [84] Nesterov Y (2021) Implementable tensor methods in unconstrained convex optimization. Math. Programming 186(1):157–183.Crossref, Google Scholar
• [85] Opial Z (1967) Weak convergence of the sequence of successive approximations for nonexpansive mappings. Bull. Amer. Math. Soc. 73(4):591–597.Crossref, Google Scholar
• [86] Osborne MJ (2004) An Introduction to Game Theory (Oxford University Press, New York).Google Scholar
• [87] Ouyang Y, Xu Y (2021) Lower complexity bounds of first-order methods for convex-concave bilinear saddle-point problems. Math. Programming 185(1):1–35.Crossref, Google Scholar
• [88] Polyak BT (1964) Some methods of speeding up the convergence of iteration methods. USSR Comput. Math. Math. Phys. 4(5):1–17.Crossref, Google Scholar
• [89] Polyanin AD, Zaitsev VF (2003) Handbook of Nonlinear Partial Differential Equations: Exact Solutions, Methods, and Problems (Chapman & Hall/CRC, Boca Raton, FL).Crossref, Google Scholar
• [90] Robinson SM (1987) Local structure of feasible sets in nonlinear programming. Part III. Stability and sensitivity. Cornet B, Nguyen VH, Vial JP, eds. Nonlinear Analysis and Optimization, Mathematical Programming Studies, vol. 30 (Springer, Berlin), 45–66.Crossref, Google Scholar
• [91] Rockafellar RT (1970) Convex Analysis, vol. 18 (Princeton University Press, Princeton, NJ).Crossref, Google Scholar
• [92] Rockafellar RT (1976) Monotone operators and the proximal point algorithm. SIAM J. Control Optim. 14(5):877–898.Crossref, Google Scholar
• [93] Shamma J (2008) Cooperative Control of Distributed Multi-Agent Systems (John Wiley & Sons, New York).Google Scholar
• [94] Shi B, Du SS, Jordan MI, Su WJ (2022) Understanding the acceleration phenomenon via high-resolution differential equations. Math. Programming 195(1):79–148.Crossref, Google Scholar
• [95] Sinha A, Namkoong H, Duchi J (2018) Certifiable distributional robustness with principled adversarial training. Proc. Internat. Conf. Learn. Representations.Google Scholar
• [96] Solodov MV (2003) Convergence rate analysis of iteractive algorithms for solving variational inequality problems. Math. Programming 96(3):513–528.Crossref, Google Scholar
• [97] Solodov MV, Svaiter BF (2000) Forcing strong convergence of proximal point iterations in a Hilbert space. Math. Programming 87(1):189–202.Crossref, Google Scholar
• [98] Song C, Jiang Y, Ma Y (2021) Unified acceleration of high-order algorithms under general Hölder continuity. SIAM J. Optim. 31(3):1797–1826.Crossref, Google Scholar
• [99] Su W, Boyd S, Candes EJ (2016) A differential equation for modeling Nesterov’s accelerated gradient method: Theory and insights. J. Machine Learn. Res. 17(1):5312–5354.Google Scholar
• [100] Tseng P (1995) On linear convergence of iterative methods for the variational inequality problem. J. Comput. Appl. Math. 60(1–2):237–252.Crossref, Google Scholar
• [101] Wibisono A, Wilson AC, Jordan MI (2016) A variational perspective on accelerated methods in optimization. Proc. Natl. Acad. Sci. USA 113(47):E7351–E7358.Crossref, Google Scholar
• [102] Wilson AC, Recht B, Jordan MI (2021) A Lyapunov analysis of accelerated methods in optimization. J. Machine Learn. Res. 22(113):1–34.Google Scholar