Distributed Subgradient Methods for Convex Optimization Over Random Networks
The DOI matches its Crossref record; 28 of the 28 references it cites were found in a registry or an index.
Abstract
We consider the problem of cooperatively minimizing the sum of convex functions, where the functions represent local objective functions of the agents. We assume that each agent has information about his local function, and communicate with the other agents over a time-varying network topology. For this problem, we propose a distributed subgradient method that uses averaging algorithms for locally sharing information among the agents. In contrast to previous works on multi-agent optimization that make worst-case assumptions about the connectivity of the agents (such as bounded communication intervals between nodes), we assume that links fail according to a given stochastic process. Under the assumption that the link failures are independent and identically distributed over time (possibly correlated across links), we provide almost sure convergence results for our subgradient algorithm.
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 1×
“[10], OlfatiSaber and Murray [16], Cao 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
Parallel 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 [20], and Chiang et al.”
BackgroundDistributed Subgradient Methods for Multi-Agent Optimization
Nedic, A., & Ozdaglar, A. (2009) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2008.2009515 · Cited by 3,719 · cited 6×
“[23], Bertsekas and Tsitsiklis [2]), which developed a general framework for parallel and distributed computation among different processors, and on the recent work by Nedić and Ozdaglar [14], which studied a distributed method for cooperative optimization in multi-agent environments.”
BackgroundMethodResultInfluentialSelf-citationRate 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 · cited 1×
“The following lemma on the infinite sum of products of the components of two sequences will also be used in establishing our convergence results (see Lemma 7 in [15] for the proof).”
BackgroundSelf-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 1×
“[11], Low and Lapsley [12], Srikant [20], and Chiang et al.”
Background
Research works printed but not linked: 1
- bertsimas, 1985, Linear Optimization
Cited by
Items 301–342 of 342
On the connectivity of unions of random graphs
Hale, M. (2017) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2017.8264311
“For example, distributed agreement problems over random graphs are studied in [34] and [18], while optimization over random graphs was explored in [24].”
BackgroundA Distributed Gossip Optimization Algorithm for Wireless Multi-hop Networks
Liu, J., & Chang, W.-L. (2017) · Lecture notes in electrical engineering · doi:10.1007/978-981-10-5281-1_5
Distributed Convex Optimization Consensus in Multi-Agent Network Subject to Equality Constraints
Zhao, D., Dong, T., Xiao-li, L., & Li, Y. (2018) · IEEE Data Driven Control and Learning Systems Conference (DDCLS) · doi:10.1109/ddcls.2018.8515989
“It is generally recognized as a distribute optimization problem and has been studied widely in [19, 24, 25].”
BackgroundDistributed Constrained Optimization Using a Projected Differential Inclusion
Zeng, X., Yi, P., & Chen, J. (2018) · IEEE International Conference on Real-time Computing and Robotics (RCAR) · doi:10.1109/rcar.2018.8621846
“To solve distributed optimization problems, both discrete-time algorithms [1], [2] and continuous-time algorithms [3]–[8] based on multi-agent networks are implemented to search for optimal solutions.”
BackgroundMethodDistributed Optimization Control of Discrete-Time Multi-Agent Systems
Zhang, H., Li, Z. Z., Wang, Y., & Li, K. (2018) · Chinese Automation Congress · doi:10.1109/cac.2018.8623050
Energy Efficiency Optimization Based SWIPT in Multiuser OFDM Systems
Fang, S., Lu, W., Zhang, Y., Li, B., Liu, X., & Na, Z. (2019) · Lecture notes of the Institute for Computer Sciences, Social Informatics and Telecommunications Engineering · doi:10.1007/978-3-030-19153-5_51
Gradient-Free Multi-Agent Nonconvex Nonsmooth OptimizationPreprint
Hajinezhad, D., & Zavlanos, M. M. (2019) · arXiv (Cornell University) · doi:10.48550/arxiv.1904.04650
“, [8–11].”
Schnelle, verteilte Optimierungsmethoden und spieltheoretische Ansätze in vernetzten Systemen
Tatarenko, T. (2020) · at - Automatisierungstechnik · doi:10.1515/auto-2019-0080
“Zufällige Kommunikationstopologien wurden in [10] betrachtet.”
Optimization and control issues with network connected dynamic systems
Li, Z. (2019) · Research Explorer (The University of Manchester)
МОДЕЛЮВАННЯ ОПТИМАЛЬНОГО РОЗВИТКУ ВИРОБНИЧИХ СИСТЕМ
Usov, A., & Sikirash, Y. (2020) · Applied Questions of Mathematical Modeling · doi:10.32782/2618-0340/2020.1-3.22
Nonasymptotic Connectivity of Random Graphs and Their Unions
Bjorkman, B., Hale, M., Lamkin, T. D., Robinson, B. D., & Thompson, C. A. (2020) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2020.3013715
“For example, distributed agreement problems over random graphs are studied in [37] and [19], whereas optimization over random graphs was explored in [25].”
BackgroundHashimoto, W., Hayashi, N., Hara, N., & Takai, S. (2020) · Transactions of the Society of Instrument and Control Engineers · doi:10.9746/sicetr.56.395
An, L., & Yang, G. (2020) · arXiv (Cornell University) · doi:10.48550/arxiv.2009.12739
“Differing from the previous works [12,13,14,15,16,17] where the integrated closed-loop control laws are designed, this paper presents a new two-layer control structure based on the traditional DO algorithms [4,5,6,7,8] and adaptive backstepping controls [36,37,38,39].”
BackgroundMethodInfluentialDistributed Optimization Over Markovian Switching Random Network
Yi, P., & Li, L. (2020) · International Conference on Control and Automation · doi:10.1109/icca51439.2020.9264492
“[7] provided the almost sure convergence results for distributed subgradient algorithm when the communication link failures are independent and identically distributed over time.”
BackgroundMethodA distributed methodology for approximate uniform global minimum sharing
Bin, M., & Parisini, T. (2021) · Automatica · doi:10.1016/j.automatica.2021.109777
“Moreover, the first-order methods in [11, 13, 16] lead to an approximate convergence result in which the convergence speed and the approximation error need to be traded off.”
MethodLinear Convergence for Constrained Optimization Over Time-Varying Digraphs
Wang, H., Li, H., & Zhou, B. (2021) · Springer eBooks · doi:10.1007/978-981-33-4528-7_5
Gradient-free distributed optimization and nash equilibrium seeking
Pang, Y. (2020) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/143354
A Flexible Distributed Stochastic Optimization Framework for Concurrent Tasks in Processing Networks
Shi, Z., & Eryılmaz, A. (2021) · IEEE/ACM Transactions on Networking · doi:10.1109/tnet.2021.3078054
“Since the traditional DSSA corresponds to our algorithm with p = 1 , then its expected network computation cost is bounded by which can be also obtained following the proof line in [5].”
BackgroundMethodInfluentialDistributed Reactive Power Control
Xu, Y., Zhang, W., Liu, W., & Yu, W. (2020) · Wiley eBooks · doi:10.1002/9781119534938.ch4
Distributed Active Power Control
Xu, Y., Zhang, W., Liu, W., & Yu, W. (2020) · Wiley eBooks · doi:10.1002/9781119534938.ch3
A Primal-Dual Algorithm for Distributed Stochastic Optimization with Equality Constraints
Du, K., & Chen, X. (2021) · Chinese Control Conference (CCC) · doi:10.23919/ccc52363.2021.9549801
“A multi-agent unconstrained convex optimization problem over deterministic time-varying network is investigated by [4] with a novel approach combining average consensus algorithm with subgradient method being introduced, while the case of random switching network is considered in [5].”
MethodDistributed Event-Triggered Random Gradient-Free Optimization Algorithm For Multiagent Systems
Hu, X., Zhang, H., & Zhuo, Q. (2021) · Chinese Control Conference (CCC) · doi:10.23919/ccc52363.2021.9550074
“The method in [3] involved estimating the solution of the agents to maintain the global optimization problem and updating them by averaging the neighbors in the network and taking a subgradient step with their local objective function.”
MethodMultiagent Distributed Optimization and Reinforcement Learning Control
Wang, J. (2021) · Studies in systems, decision and control · doi:10.1007/978-3-030-86893-2_6
Distributed multi-agent consensus under constraints
Qiu, Z. (2017) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/72344
Optimal control applications and methods literature survey (Nos. 25–26)
(2011) · Optimal Control Applications and Methods · doi:10.1002/oca.1017
Adaptive control and signal processing literature survey (No. 26)
(2011) · International Journal of Adaptive Control and Signal Processing · doi:10.1002/acs.1278
Coluccia, G., Ravazzi, C., & Magli, E. (2015) · Springer briefs in electrical and computer engineering · doi:10.1007/978-981-287-390-3_5
Markovian Decentralized Ensemble Control for Demand Response
Peng, G., Mieth, R., Deka, D., & Dvorkin, Y. (2022) · IEEE Control Systems Letters · doi:10.1109/lcsys.2022.3179476
“Convergence of (17) to the optimal solution of (10) is guaranteed by: Proposition 1 ([14]): Let {P(n)(k)} be generated by (17)”
BackgroundMethodArroyo, J. E. M., & Mogollón, H. J. P. (2021) · Publicaciones e Investigación · doi:10.22490/25394088.5590
Moreau Envelope ADMM for Decentralized Weakly Convex Optimization
Mirzaeifard, R., Venkategowda, N. K. D., Jung, A., & Werner, S. (2023) · Asia-Pacific Signal and Information Processing Association Annual Summit and Conference (APSIPA ASC) · doi:10.1109/apsipaasc58517.2023.10317303
“For convex objective functions, subgradient methods and ADMM are guaranteed to converge to a global optimum under suitable parameter choices [6], [10], [11].”
MethodLiu, J. (2024) · International Journal of Control · doi:10.1080/00207179.2024.2387300
“In discrete-time case, the step-sizes are used to adjust convergence which can be traced back to the seminal works (Duchi et al., 2012; Lee & Nedić, 2013; Lobel & Ozdaglar, 2011; Nedić & Olshevsky, 2015; Nedić & Ozdaglar,2009 ; Zhu & Mar-tinez, 2012).”
Distributed Least-Squares Optimization Solvers with Differential Privacy
Liu, W., Wang, L., Guo, F., Wu, Z., & Su, H. (2024) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.23919/acc60939.2024.10644636
“For such a problem, since the seminal work of the distributed gradient-descend algorithm [4], numerical algorithms have been developed, that differ from linear or sub-linear convergence rate [5], [6], [7], [8], deterministic or stochastic communication graph [9], [10], and equality or inequality…”
BackgroundDecentralized stochastic subgradient projection optimization algorithms over random networks
Fu, K., & Fu, X. (2024) · Optimization · doi:10.1080/02331934.2024.2407019
Fixed-Time Zero-Gradient-Sum Algorithm for Disturbed Linear Heterogeneous Multi-Agent Systems
Zhang, P., Luan, L., Zhang, Y., Zhang, J., & Wu, Y. (2024) · International Conference on New Trends in Computational Intelligence (NTCI) · doi:10.1109/ntci64025.2024.10776227
Wang, Q., Xin, B., & Chen, J. (2025) · Springer eBooks · doi:10.1007/978-981-96-0950-5_1
Xu, Q., & Luo, S. (2023) · International Conference on Networking Systems of AI (INSAI) · doi:10.1109/insai60116.2023.00045
“…optimization algorithms are proposed for balanced undirected graph communication topology, such as distributed gradient descent algorithm[2], mirror descent algorithm[3] and accurate first-order algorithm[4], but there is little research on directed graph communication topology,…”
Zeng, L., Chen, Z., & Guo, Z. (2025) · Chinese Control Conference (CCC) · doi:10.23919/ccc64809.2025.11179661
Fast, distributed optimization strategies for resource allocation in networks
Zargham, M. (2014) · Scholarly Commons (University of Pennsylvania)
Tang, R., Li, H., Xia, D., Ran, L., & Li, J. Q. (2026) · Nonlinear Dynamics · doi:10.1007/s11071-026-12377-z
Lan, J., & Ma, J. (2026) · Chinese Control and Decision Conference (CCDC) · doi:10.1109/ccdc69976.2026.11560791
“Classical distributed optimization methods including subgradient algorithms [4], [5], dual averaging [6], [7] and alternating direction methods of multipliers [8], [9], provide decentralized solutions, while projection-based constrained methods [10], [11] and an exponentially convergent constrained…”
Боровська, Т. М., & Borovska, T. M. (2018) · Repository of Vinnytsia National Technical University (Vinnytsia National Technical University)
Metadata
- Authors
- Lobel, I., & Ozdaglar, A.
- Affiliations
- New York University (US)
- Massachusetts Institute of Technology (US)
- Venue
- IEEE Transactions on Automatic Control
- Published
- 2011-06
- Volume
- 56
- Issue
- 6
- Pages
- 1291-1306
- ISSN
- 0018-9286 (ISSN-L)
- 1558-2523
- OpenAlex
- W2106901427
- Cited by
- 351
- References
- 28
- Citations by year
- 2026: 6 · 2025: 8 · 2024: 14 · 2023: 13 · 2022: 15 · 2021: 27 · 2020: 26 · 2019: 36 · 2018: 38 · 2017: 37 · 2016: 37 · 2015: 30 · 2014: 25 · 2013: 14 · 2012: 11
- FWCI
- 17.33
- 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 › Computer Science › Signal Processing › Sparse and Compressive Sensing Techniques
- Keywords
- convex optimization, multi-agent optimization, time-varying topology, random networks, link failure, averaging algorithms, almost sure convergence, 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
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.