Distributed Subgradient Methods for Multi-Agent Optimization
The DOI matches its Crossref record; 36 of the 36 references it cites were found in a registry or an index.
Abstract
We study a distributed computation model for optimizing a sum of convex objective functions corresponding to multiple agents. For solving this (not necessarily smooth) optimization problem, we consider a subgradient method that is distributed among the agents. The method involves every agent minimizing his/her own objective function while exchanging information locally with other agents in the network over a time-varying topology. We provide convergence results and convergence rate estimates for the subgradient method. Our convergence rate results explicitly characterize the tradeoff between a desired accuracy of the generated approximate optimal solutions and the number of iterations needed to achieve the accuracy.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Consensus Problems in Networks of Agents With Switching Topology and Time-Delays
Olfati-Saber, R., & Murray, R. M. (2004) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.834113 · Cited by 12,788 · cited 2×
“In addition, our work is also related to the literature on reaching consensus on a particular scalar value or computing exact averages of the initial values of the agents, which has attracted much recent attention as natural models of cooperative behavior in networked-systems (see Vicsek et al. [4], Jadbabaie et al. […”
BackgroundCoordination of groups of mobile autonomous agents using nearest neighbor rules
Jadbabaie, A., Lin, J., & Morse, A. S. (2003) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2003.812781 · Cited by 8,339
Novel Type of Phase Transition in a System of Self-Driven Particles
Vicsek, T., Czirók, A., Ben-Jacob, E., Cohen, I., & Shochet, O. (1995) · Physical Review Letters · doi:10.1103/physrevlett.75.1226 · Cited by 7,380 · cited 1×
“In addition, our work is also related to the literature on reaching consensus on a particular scalar value or computing exact averages of the initial values of the agents, which has attracted much recent attention as natural models of cooperative behavior in networked-systems (see Vicsek et al. [ 4 ], Jadbabaie et al.…”
BackgroundParallel and Distributed Computation: Numerical Methods
Bertsekas, D. P., & Tsitsiklis, J. N. (1989) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 5,293
Rate control for communication networks: shadow prices, proportional fairness and stability
Kelly, F. P., Maulloo, A. K., & Tan, D. K. H. (1998) · Journal of the Operational Research Society · doi:10.1057/palgrave.jors.2600523 · Cited by 5,021 · cited 1×
“[11], Low and Lapsley [12], Srikant [13], and Chiang et al.”
BackgroundRate control for communication networks: shadow prices, proportional fairness and stability
Kelly, F. P., Maulloo, A. K., & Tan, D. K. H. (1998) · Journal of the Operational Research Society · doi:10.1038/sj.jors.2600523 · Cited by 2,399
Convex Analysis and Optimization
Bertsekas, D. P., Nedić, A., & Ozdaglar, A. (2003) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 2,148
Self-citationConstrained Consensus and Optimization in Multi-Agent Networks
Nedic, A., Ozdaglar, A., & Parrilo, P. A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2041686 · Cited by 2,086
Self-citationOptimization flow control. I. Basic algorithm and convergence
Low, S. H., & Lapsely, D. E. (1999) · IEEE/ACM Transactions on Networking · doi:10.1109/90.811451 · Cited by 1,972 · cited 2×
“Our work is also related to the utility maximization framework for resource allocation in networks (see Kelly et al. [11], Low and Lapsley [12], Srikant [13], and Chiang et al. [14]).”
BackgroundDistributed asynchronous deterministic and stochastic gradient optimization algorithms
Tsitsiklis, J., Bertsekas, D., & Athans, M. (1986) · IEEE Transactions on Automatic Control · doi:10.1109/tac.1986.1104412 · Cited by 1,967
Minimization Methods for Non-Differentiable Functions
Shor, N. Z. (1985) · Springer Series in Computational Mathematics · doi:10.1007/978-3-642-82118-9 · Cited by 1,551
Layering as Optimization Decomposition: A Mathematical Theory of Network Architectures
Chiang, M., Low, S. H., Calderbank, A. R., & Doyle, J. C. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887322 · Cited by 1,352 · cited 1×
“Assumption 1: (Weights Rule) We have: a) There exists a scalar with such that for all , i) for all . ii) for all and all agents communicating directly with agent in the interval . iii) for all and otherwise. b) The vectors are stochastic, i.e., for all and .”
BackgroundPROBLEMS IN DECENTRALIZED DECISION MAKING AND COMPUTATION
Τσιτσικλής, Ι. (2014) · doi:10.12681/eadd/3778 · Cited by 1,278
Parallel and distributed computation
Bertsekas, D. P., Tsitsiklis, J. N., & Sennikov, A. N. (1989) · Cited by 1,187
Convergence in Multiagent Coordination, Consensus, and Flocking
Blondel, V. D., Hendrickx, J. M., Olshevsky, A., & Tsitsiklis, J. N. (2006) · Proceedings of the 44th IEEE Conference on Decision and Control · doi:10.1109/cdc.2005.1582620 · Cited by 859 · cited 2×
“[16]): • (Equal Neighbor Weights) Each agent assigns equal weight to his/her information and the information received from the other agents at slot , i.”
BackgroundDuclos-Lassalle, G. (2000) · Érudit (Université de Montréal) · Cited by 846
The Mathematics of Internet Congestion Control
(2005) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2004.841398 · Cited by 821 · cited 3×
“The authors wish to thank D. Shah, P. Parrilo, R. Srikant, the associate editor, three anonymous referees, and various seminar participants for useful comments and discussion.”
BackgroundThe Mathematics of Internet Congestion Control
Srikant, R. (2004) · Systems & Control: Foundations & Applications · doi:10.1007/978-0-8176-8216-3 · Cited by 800 · cited 1×
“Our work is also related to the utility maximization framework for resource allocation in networks (see Kelly et al. [11], Low and Lapsley [12], Srikant [ 13 ], and Chiang et al. [14]).”
Bayesian Learning in Social Networks
Acemoglu, D., Dahleh, M. A., Lobel, I., & Ozdaglar, A. (2011) · The Review of Economic Studies · doi:10.1093/restud/rdr004 · Cited by 754
Self-citationConvergence Speed in Distributed Consensus and Averaging
Olshevsky, A., & Tsitsiklis, J. N. (2009) · SIAM Journal on Control and Optimization · doi:10.1137/060678324 · Cited by 692 · cited 1×
“This framework focuses on the minimization of a (smooth) function by distributing the processing of the components of vector among agents.”
BackgroundIncremental Subgradient Methods for Nondifferentiable Optimization
Nedic, A., & Bertsekas, D. P. (2001) · SIAM Journal on Optimization · doi:10.1137/s1052623499362111 · Cited by 589
Gossip algorithms: design, analysis and applications
Boyd, S., Ghosh, A., Prabbakar, B., & Shah, D. (2005) · Proceedings IEEE 24th Annual Joint Conference of the IEEE Computer and Communications Societies. · doi:10.1109/infcom.2005.1498447 · Cited by 558 · cited 1×
“[6], Olfati-Saber and Murray [7], Cao et al.”
BackgroundOn Distributed Averaging Algorithms and Quantization Effects
Nedic, A., Olshevsky, A., Ozdaglar, A., & Tsitsiklis, J. N. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2009.2031203 · Cited by 557
Self-citationApproximate Primal Solutions and Rate Analysis for Dual Subgradient Methods
Nedić, A., & Ozdaglar, A. (2009) · SIAM Journal on Optimization · doi:10.1137/070708111 · Cited by 399
Self-citationStochastic Optimization: Algorithms and Applications
(2001) · Applied Optimization · doi:10.1007/978-1-4757-6594-6 · Cited by 198
Convergence rate for consensus with delays
Nedić, A., & Ozdaglar, A. (2010) · Journal of Global Optimization · doi:10.1007/s10898-008-9370-2 · Cited by 198
Self-citationConvergence Rate of Incremental Subgradient Algorithms
Nedić, A., & Bertsekas, D. (2001) · Applied Optimization · doi:10.1007/978-1-4757-6594-6_11 · Cited by 190
Convergence Rates in Distributed Consensus and Averaging
Olshevsky, A., & Tsitsiklis, J. N. (2006) · Proceedings of the 45th IEEE Conference on Decision and Control · doi:10.1109/cdc.2006.376899 · Cited by 153 · cited 1×
“In addition, our work is also related to the literature on reaching consensus on a particular scalar value or computing exact averages of the initial values of the agents, which has attracted much recent attention as natural models of cooperative behavior in networked-systems (see Vicsek et al. [4], Jadbabaie et al. […”
BackgroundDistributed Asynchronous Incremental Subgradient Methods
Nedić, A., Bertsekas, D. P., & Borkar, V. S. (2001) · Studies in computational mathematics · doi:10.1016/s1570-579x(01)80023-9 · Cited by 146 · cited 1×
“Similar relations have been used in various ways to analyze subgradient approaches (for example, see Shor [18], Polyak [19], Nedic ´ and Bertsekas [20], [21], and Nedic ´, Bertsekas, and Borkar [ 22 ]).”
MethodA Lower Bound on Convergence of a Distributed Network Consensus Algorithm
Cao, M., Spielman, D. A., & Morse, A. S. (2006) · Proceedings of the 44th IEEE Conference on Decision and Control · doi:10.1109/cdc.2005.1582514 · Cited by 116 · cited 1×
“[8], and Olshevsky and Tsitsiklis [9], [10]).”
Inherently Parallel Algorithms in Feasibility and Optimization and their Applications
Butnariu, D., Censor, Y., & Reich, S. (2001) · Studies in computational mathematics · doi:10.1016/s1570-579x(01)x8001-4 · Cited by 95
Spread of (Mis)Information in Social NetworksPreprint
Acemoğlu, D., Ozdaglar, A., & ParandehGheibi, A. (2009) · SSRN Electronic Journal · doi:10.2139/ssrn.1401648 · Cited by 94
Self-citationCommunication constraints in coordinated consensus problems
Carli, R., Fagnani, F., Speranzon, A., & Zampieri, S. (2006) · 2006 American Control Conference · doi:10.1109/acc.2006.1657376 · Cited by 46 · cited 1×
“[6]).”
Convergence analysis of distributed subgradient methods over random networks
Lobel, I., & Ozdaglar, A. (2008) · 2008 46th Annual Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2008.4797579 · Cited by 44
Self-citationKashyap, A., Basar, T., & Srikant, R. (2006) · 2006 IEEE International Symposium on Information Theory · doi:10.1109/isit.2006.261862 · Cited by 43
Anthony, M., & Biggs, N. (2024) · Cambridge University Press eBooks · doi:10.1017/9781108560177.010 · Cited by 9
Cited by
Boyd, S., Parikh, N., Chu, E., Peleato, B., & Eckstein, J. (2011) · Foundations and Trends® in Machine Learning · doi:10.1561/2200000016 · Cited by 17,075
Boyd, S. (2010) · now publishers, Inc. eBooks · doi:10.1561/9781601984616 · Cited by 12,677
Parikh, N., & Boyd, S. (2014) · Foundations and Trends® in Optimization · doi:10.1561/2400000003 · Cited by 4,102
“Some classic and important modern references include those by Dantzig and Wolfe [66], Benders [23], Lasdon [118], Geoffrion [93], Tsitsiklis [189], Bertsekas and Tsitsklis [27], Censor and Zenios [50], and Nedic̀ and Ozdaglar [144, 145].”
BackgroundAn Overview of Recent Progress in the Study of Distributed Multi-Agent Coordination
Cao, Y., Yu, W., Ren, W., & Chen, G. (2013) · IEEE Transactions on Industrial Informatics · doi:10.1109/tii.2012.2219061 · Cited by 2,399
“[234] was probably the first paper studying the distributed multi -agent optimization problem under a consensus-based framework.”
BackgroundConstrained Consensus and Optimization in Multi-Agent Networks
Nedic, A., Ozdaglar, A., & Parrilo, P. A. (2010) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2010.2041686 · Cited by 2,086
Self-citation
Metadata
- Authors
- Nedic, A., & Ozdaglar, A.
- Affiliations
- Massachusetts Institute of Technology (US)
- ORCID
- Ozdaglar, Asuman
- Venue
- IEEE Transactions on Automatic Control
- Published
- 2009-01
- Volume
- 54
- Issue
- 1
- Pages
- 48-61
- ISSN
- 0018-9286 (ISSN-L)
- OpenAlex
- W2044212084
- Cited by
- 3,719
- References
- 36
- Citations by year
- 2026: 185 · 2025: 299 · 2024: 290 · 2023: 299 · 2022: 295 · 2021: 305 · 2020: 370 · 2019: 328 · 2018: 266 · 2017: 236 · 2016: 209 · 2015: 166 · 2014: 127 · 2013: 107 · 2012: 99
- FWCI
- 96.63
- Type
- journal article
- Language
- en
- Open access
- closed
- Locations
- IEEE Transactions on Automatic Control (publishedVersion)
- Topics
- Physical Sciences › Engineering › Control and Systems Engineering › Distributed Control Multi-Agent Systems
- Physical Sciences › Computer Science › Computational Theory and Mathematics › Optimization and Variational Analysis
- Physical Sciences › Engineering › Control and Systems Engineering › Advanced Control Systems Optimization
- Keywords
- distributed optimization, multi-agent systems, subgradient method, convex optimization, time-varying topology, convergence rate, convergence analysis, networked agents, distributed computing
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.