The DOI matches its Crossref record; 18 of the 18 references it cites were found in a registry or an index.
Fast convergence of inertial dynamics and algorithms with asymptotic vanishing viscosity
Open accessAbstract
In a Hilbert space setting $${{\mathcal {H}}}$$H, we study the fast convergence properties as $$t \rightarrow + \infty $$t→+∞ of the trajectories of the second-order differential equation $$\begin{aligned} \ddot{x}(t) + \frac{\alpha }{t} \dot{x}(t) + \nabla \Phi (x(t)) = g(t), \end{aligned}$$x¨(t)+αtx˙(t)+∇Φ(x(t))=g(t),where $$\nabla \Phi $$∇Φ is the gradient of a convex continuously differentiable function $$\Phi : {{\mathcal {H}}} \rightarrow {{\mathbb {R}}}, \alpha $$Φ:H→R,α is a positive parameter, and $$g: [t_0, + \infty [ \rightarrow {{\mathcal {H}}}$$g:[t0,+∞[→H is a small perturbation term. In this inertial system, the viscous damping coefficient $$\frac{\alpha }{t}$$αt vanishes asymptotically, but not too rapidly. For $$\alpha \ge 3$$α≥3, and $$\int _{t_0}^{+\infty } t \Vert g(t)\Vert dt < + \infty $$∫t0+∞t‖g(t)‖dt<+∞, just assuming that $${{\mathrm{argmin\,}}}\Phi \ne \emptyset $$argminΦ≠∅, we show that any trajectory of the above system satisfies the fast convergence property $$\begin{aligned} \Phi (x(t))- \min _{{{\mathcal {H}}}}\Phi \le \frac{C}{t^2}. \end{aligned}$$Φ(x(t))-minHΦ≤Ct2.Moreover, for $$\alpha > 3$$α>3, any trajectory converges weakly to a minimizer of $$\Phi $$Φ. The strong convergence is established in various practical situations. These results complement the $${{\mathcal {O}}}(t^{-2})$$O(t-2) rate of convergence for the values obtained by Su, Boyd and Candès in the unperturbed case $$g=0$$g=0. Time discretization of this system, and some of its variants, provides new fast converging algorithms, expanding the field of rapid methods for structured convex minimization introduced by Nesterov, and further developed by Beck and Teboulle with FISTA. This study also complements recent advances due to Chambolle and Dossal.
Overview
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
The claims and statistics of this paper haven’t been checked yet.
Free: it reads the open-access text and checks the first 5 claims that cite a source we can check. Create a free account to check every claim.
Self-check
Percentages, sums and reported differences re-computed from the paper’s own numbers.
The self-check needs the paper’s full text.
Citations
Cites
A Fast Iterative Shrinkage-Thresholding Algorithm for Linear Inverse Problems
Beck, A., & Teboulle, M. (2009) · SIAM Journal on Imaging Sciences · doi:10.1137/080716542 · Cited by 11,952
Parikh, N., & Boyd, S. (2014) · Foundations and Trends® in Optimization · doi:10.1561/2400000003 · Cited by 4,102
Introductory Lectures on Convex Optimization: A Basic Course
Nesterov, Y. E. (2014) · Medical Entomology and Zoology · Cited by 3,557
Convex Analysis and Monotone Operator Theory in Hilbert Spaces
Bauschke, H. H., & Combettes, P. L. (2017) · CMS Books in Mathematics · doi:10.1007/978-3-319-48311-5 · Cited by 3,307
Convex Analysis and Monotone Operator Theory in Hilbert Spaces
Bauschke, H. H., & Combettes, P. L. (2011) · CMS Books in Mathematics · doi:10.1007/978-1-4419-9467-7 · Cited by 2,962
Introductory Lectures on Convex Optimization
Nesterov, Y. (2004) · Applied Optimization · doi:10.1007/978-1-4419-8853-9 · Cited by 2,698
Smooth minimization of non-smooth functions
Nesterov, Y. (2005) · Mathematical Programming · doi:10.1007/s10107-004-0552-5 · Cited by 2,455
Weak convergence of the sequence of successive approximations for nonexpansive mappings
Opial, Z. (1967) · Bulletin of the American Mathematical Society · doi:10.1090/s0002-9904-1967-11761-0 · Cited by 2,340
Gradient methods for minimizing composite objective function
Nesterov, Y. E. (2007) · Cited by 867
An Inertial Forward-Backward Algorithm for Monotone Inclusions
Lorenz, D. A., & Pock, T. (2015) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-014-0523-2 · Cited by 445
New Proximal Point Algorithms for Convex Minimization
Güler, O. (1992) · SIAM Journal on Optimization · doi:10.1137/0802032 · Cited by 231
Accelerated and Inexact Forward-Backward Algorithms
Villa, S., Salzo, S., Baldassarre, L., & Verri, A. (2013) · SIAM Journal on Optimization · doi:10.1137/110844805 · Cited by 197
A Dynamical Approach to an Inertial Forward-Backward Algorithm for Convex Minimization
Attouch, H., Peypouquet, J., & Redont, P. (2014) · SIAM Journal on Optimization · doi:10.1137/130910294 · Cited by 194
Self-citationConvex Optimization in Normed Spaces: Theory, Methods and Examples
Peypouquet, J. (2015) · SpringerBriefs in optimization · doi:10.1007/978-3-319-13710-0 · Cited by 187
Self-citationA Differential Equation for Modeling Nesterov’s Accelerated Gradient Method: Theory and Insights
Su, W., Boyd, S., & Candès, E. J. (2014) · neural information processing systems · Cited by 155
Cabot, A., Engler, H., & Gadat, S. (2009) · Transactions of the American Mathematical Society · doi:10.1090/s0002-9947-09-04785-0 · Cited by 132
Stability of Over-Relaxations for the Forward-Backward Algorithm, Application to FISTA
Aujol, J., & Dossal, C. (2015) · SIAM Journal on Optimization · doi:10.1137/140994964 · Cited by 90
Fast Exact Hyper-graph Matching with Dynamic Programming for Spatio-temporal Data
Çeliktutan, O., Wolf, C., Sankur, B., et al. (2014) · Journal of Mathematical Imaging and Vision · doi:10.1007/s10851-014-0503-6 · Cited by 28
Cited by
An operator splitting approach for distributed generalized Nash equilibria computation
Yi, P., & Pavel, L. (2019) · Automatica · doi:10.1016/j.automatica.2019.01.008 · Cited by 271
Inertial projection and contraction algorithms for variational inequalities
Dong, Q. L., Cho, Y. J., Zhong, L. L., & Rassias, T. M. (2018) · Journal of Global Optimization · doi:10.1007/s10898-017-0506-0 · Cited by 267
Metadata
- Authors
- Attouch, H., Chbani, Z., Peypouquet, J., & Redont, P.
- Venue
- Mathematical Programming
- Published
- 2016-03-24
- Volume
- 168
- Issue
- 1-2
- Pages
- 123-175
- ISSN
- 0025-5610 (ISSN-L)
- 1436-4646
- OpenAlex
- W2302721240
- Cited by
- 277
- References
- 18
- FWCI
- 14.59
- Type
- journal article
- Language
- en
- Open access
- green
About these checks
Registry, retraction, Cites and statistics results are computed, not judged, with one exception: a printed reference that no index lists is read once by a model before it counts as a citation error. Claims are extracted by a model and kept only when their quote appears verbatim in the text; each cited source is then checked, with a model’s help, for whether it says what the claim relies on. Those verdicts can be wrong — read the claim’s quote and the cited source before relying on one.
Statistics and arithmetic are recomputed, not judged.
Confidence bands are shown only for fields calibrated on our annotated test set. None is calibrated yet, so no band is shown.
What counts as a claim ›How we measure confidence ›How we check this ›
Are you an author, or do you see a problem with this page? Request a review
Data sources
Bibliographic data: Semantic Scholar, OpenAlex, Crossref.
Contains information from the Semantic Scholar Academic Graph Datasets, made available under the ODC Attribution License (ODC-BY 1.0).
Semantic Scholar’s data is described in: Kinney, R., et al. (2023). The Semantic Scholar Open Data Platform. arXiv:2301.10140.