CoChat
Sign Up
Cited by 123Distributed Control Multi-Agent SystemsStochastic Gradient Optimization TechniquesAdvanced Optimization Algorithms Research

The DOI matches its Crossref record; 1 of the 1 references it cites were found in a registry or an index.

Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms

Jakovetic, Dusan, Moura, Jose M. F., Xavier, Joao·2015·IEEE Transactions on Automatic Control
DOI 10.1109/tac.2014.2363299
Open this paper in CoChat — free account

Abstract

We study distributed optimization where nodes cooperatively minimize the sum of their individual, locally known, convex costs fi(x)'s; x ϵ ℝdis global. Distributed augmented Lagrangian (AL) methods have good empirical performance on several signal processing and learning applications, but there is limited understanding of their convergence rates and how it depends on the underlying network. This paper establishes globally linear (geometric) convergence rates of a class of deterministic and randomized distributed AL methods, when the fi's are twice continuously differentiable and have a bounded Hessian. We give explicit dependence of the convergence rates on the underlying network parameters. Simulations illustrate our analytical findings.

Overview

Integrity signals

Registry

Crossref · 10.1109/tac.2014.2363299

Cites

1 of 1 references verified0 citation errors · 0 not checkable

Statistics

Recomputing p-values needs the paper’s full text.

Verification

Claims the paper makes

We couldn’t retrieve this paper’s full text, so its claims and self-check weren’t run. The registry and citation checks still apply.

Claims other papers make about this one

Each is checked against this paper’s own text: does it say what the citing paper says it does?

  • Augmented Lagrangian based primal-dual methods have linear convergence under strong convexity and Lipschitz gradient assumptions or under the positive-definite bounded Hessian assumption.

    “The augmented Lagrangian based primal-dual methods have linear convergence under strong convexity and Lipschitz gradient assumptions [4,30] or under the positive-definite bounded Hessian assumption [12,13].”

    From EXTRA: An Exact First-Order Algorithm for Decentralized Consensus Optimization (2015) · cites this paper as [13]

Citations

Cites

Flagged first, then by citations

Research works printed but not linked: 55

  1. kallio, 1994, Perturbation Methods for Saddle Point Computation
  2. maistroskii, 1977, Gradient methods for finding saddle points, Matekon, 13, 3
  3. lemaréchal, 2001, Lagrangian relaxation, Lecture Notes in Computer Science Springer, 2241, 112, 10.1007/3-540-45586-8_4 · DOI
  4. h urruty, 1996, Convex Analysis and Minimization Algorithms Fundamentals
  5. deng, 2012, On the Global and Linear Convergence of the Generalized Alternating Direction Method of Multipliers, 10.21236/ADA567407 · DOI
  6. hong, 2012, On the linear convergence of the alternating direction method of multipliers
  7. gol'shtein, 1974, A generalized gradient method for finding saddle points, Matekon, 10, 36
  8. arrow, 1958, Studies in Linear and Nonlinear Programming
  9. powell, 1969, A method for nonlinear constraints in minimization problems, Optimization
  10. 10.1007/BF00927673 · DOI
  11. 10.1137/0314020 · DOI
  12. 10.1137/0330025 · DOI
  13. 10.1287/moor.1.2.97 · DOI
  14. 10.1145/984622.984626 · DOI · Paper page
  15. 10.1109/TIT.2012.2191450 · DOI
  16. 10.1109/ALLERTON.2010.5706956 · DOI
  17. lan, 2008, Iteration-Complexity of First-Order Augmented Lagrangian Methods for Convex Programming
  18. 10.1109/CDC.2011.6161503 · DOI
  19. 10.1007/BF01581204 · DOI
  20. nedelcu, 2013, Computational complexity of inexact gradient augmented Lagrangian methods Application to constrained MPC
  21. glowinski, 1975, Sur l'approximation, par éléments finis d'ordre 1, et la résolution, par pénalisation-dualité, d'une classe de problémes de Dirichlet non-linéaires, Revue Francaise d Automatique informatique et Recherche Operationelle, 9, 41
  22. 10.1016/0898-1221(76)90003-1 · DOI
  23. 10.1016/0024-3795(69)90028-7 · DOI
  24. kleptsyn, 0, Effect of small synchronization errors on stability of complex systems. I, Automation and Remote Control, 44
  25. 10.1561/2200000016 · DOI · Paper page
  26. marsden, 1996, Vector Calculus
  27. 10.1109/TAC.2014.2298712 · DOI · Paper page
  28. kleptsyn, 0, Effect of small synchronization errors on stability of complex systems. III, Automation and Remote Control, 45
  29. kleptsyn, 0, Effect of small synchronization errors on stability of complex systems. II, Automation and Remote Control, 45
  30. 10.1109/TSP.2014.2304432 · DOI · Paper page
  31. 10.1007/s10957-009-9522-7 · DOI
  32. 10.1109/ICASSP.2013.6638534 · DOI
  33. yuan, 2013, On the Convergence of Decentralized Gradient Descent
  34. 10.1109/JSTSP.2011.2120593 · DOI
  35. 10.1109/CDC.2012.6425904 · DOI
  36. ghadimi, 2012, Accelerated Gradient Methods for Networked Optimization
  37. 10.1109/TSP.2011.2162831 · DOI
  38. zhu, 2012, On distributed convex optimization under inequality and equality constraints, IEEE Trans Autom Control, 57, 151, 10.1109/TAC.2011.2167817 · DOI · Paper page
  39. 10.1109/CDC.2012.6426897 · DOI · Paper page
  40. 10.1109/TSP.2010.2055862 · DOI
  41. 10.1109/TSP.2011.2182347 · DOI
  42. 10.1109/TSP.2007.906734 · DOI
  43. 10.1109/TSP.2009.2038417 · DOI
  44. 10.1109/TSP.2011.2146776 · DOI
  45. 10.1109/TSP.2007.908943 · DOI
  46. 10.1007/BF01407866 · DOI
  47. terelius, 0, Decentralized multi-agent optimization via dual decomposition, Proc Int Federation Automatic Control World Congr (IFAC)
  48. ortega, 1970, Iterative Solution of Nonlinear Equations in Several Variables
  49. lu, 2012, Convergence analysis of the modified nonlinear inexact Uzawa algorithm for saddle point problem, Int J Contemp Math Sci, 7, 1067
  50. bertsekas, 1989, Parallel and Distributed Computation
  51. 10.1007/978-1-4612-1346-8 · DOI
  52. 10.1137/S0036142994273343 · DOI
  53. chen, 1995, Global and superlinear convergence of inexact Uzawa methods for saddle point problems with nondifferentiable mappings
  54. 10.1137/S1052623403428683 · DOI
  55. chambolle, 2010, A first-order primal-dual algorithm for convex problems with applications to imaging

Cited by

Sorted by citations

Metadata

Authors
Jakovetic, D., Moura, J. M. F., & Xavier, J.
Venue
IEEE Transactions on Automatic Control
Publisher
Institute of Electrical and Electronics Engineers (IEEE)
Published
2015-04
Volume
60
Issue
4
Pages
922-936
ISSN
  • 0018-9286 (ISSN-L)
  • 1558-2523
DOI
10.1109/tac.2014.2363299
OpenAlex
W2057873962
Cited by
123
References
1
Citations by year
2026: 3 · 2025: 2 · 2024: 5 · 2023: 6 · 2022: 11 · 2021: 19 · 2020: 20 · 2019: 16 · 2018: 12 · 2017: 10 · 2016: 10 · 2015: 6
FWCI
11.11
Type
journal article
Language
en
Open access
closed
Licence
ieeexplore.ieee.org/Xplorehelp/downloads/license-information/IEEE.html (vor)
Locations
IEEE Transactions on Automatic Control (publishedVersion)
Funders
  • Carnegie Mellon|Portugal Program under a grant from the Fundação de Ciência e Tecnologia (FCT) from Portugal
  • FCT (CMU-PT/SIA/0026/2009, PTDC/EMS-CRO/2042/2012)
  • SFRH/BD/33518/2008 (through the Carnegie Mellon|Portugal Program managed by ICTI)
  • ISR/IST plurianual funding (POSC program, FEDER)
  • AFOSR (FA95501010291)
  • NSF (CCF1011903)
Topics
  • Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
  • Physical Sciences › Computer Science › Artificial Intelligence › Stochastic Gradient Optimization Techniques
  • Physical Sciences › Mathematics › Numerical Analysis › Advanced Optimization Algorithms Research
Keywords
distributed optimization, augmented Lagrangian method, linear convergence, geometric convergence, convex optimization, randomized algorithms, network parameters, cooperative optimization

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