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
An 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
“Further results on this topic can be found in [111]–[113], where a similar distributed multi-agent optimization problem was studied within various scenarios, under constraints [111], over random networks [112], and with broadcast-based communications in an asynchronous setting [113].”
BackgroundDistributed Optimization Over Time-Varying Directed Graphs
Nedic, A., & Olshevsky, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2364096 · Cited by 1,187
“2364096 Distributed optimization of a sum of convex functions has received a surge of interest in recent years [3], [5], [8], [11]– [13], [15], [23], [27].”
A survey of distributed optimization
Yang, T., Yi, X., Wu, J., Yuan, Y., Wu, D., Meng, Z., Hong, Y., Wang, H., Lin, Z., & Johansson, K. H. (2019) · Annual Reviews in Control · doi:10.1016/j.arcontrol.2019.05.006 · Cited by 913
“In summary, the existing distributed algorithms for random graphs either use the gradient information (see, e.g., Jakoveti ´c et al., 2014a; Lobel & Ozdaglar, 2011; Wu, Yang, Wu et al., 2017 ) and diminishing step-sizes or fixed step-sizes and the Hessian information (see, e.g., Carli et al., 2015;…”
BackgroundMethodOpinion Dynamics and Learning in Social Networks
Acemoglu, D., & Ozdaglar, A. (2011) · Dynamic Games and Applications · doi:10.1007/s13235-010-0004-1 · Cited by 705
“12 10 The DeGroot model and variations have also been studied extensively in the cooperative control literature as natural algorithms for achieving cooperative behavior with local information in networked-systems (see [18, 33, 62, 67, 71, 72, 87–89]).”
BackgroundSelf-citationNetwork Topology and Communication-Computation Tradeoffs in Decentralized Optimization
Nedic, A., Olshevsky, A., & Rabbat, M. G. (2018) · Proceedings of the IEEE · doi:10.1109/jproc.2018.2817461 · Cited by 534
Distributed Constrained Optimization by Consensus-Based Primal-Dual Perturbation Method
Chang, T.-H., Nedic, A., & Scaglione, A. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2308612 · Cited by 401
A Second-Order Multi-Agent Network for Bound-Constrained Distributed Optimization
Liu, Q., & Wang, J. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2416927 · Cited by 397
“For distributed optimization, most of the works build on consensus algorithms which are described by discrete-time dynamics to search for optimal solutions [21], [25].”
BackgroundDistributed Asynchronous Constrained Stochastic Optimization
Srivastava, K., & Nedic, A. (2011) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2011.2118740 · Cited by 350
“In [9], the authors consider a random network model for communication among agents, but the optimization problem is unconstrained and the proposed approach is synchronous in nature in the sense that the step sizes of the different agents are coordinated.”
BackgroundDistributed Algorithms for Aggregative Games on Graphs
Koshal, J., Nedić, A., & Shanbhag, U. V. (2016) · Operations Research · doi:10.1287/opre.2016.1501 · Cited by 341
“This idea has attracted a lot of attention recently in an effort to extend the algorithm of [57] to more general and broader range of problems [35, 46, 45, 19, 18, 36, 54, 33, 26, 58, 48, 59, 5].”
BackgroundXu, Y., Wang, J., Wu, Q., Anpalagan, A., & Yao, Y.-D. (2012) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2011.2176916 · Cited by 330
“However, as was pointed in [14], it is a challenging task to achieve global optimization for distributed systems where only local information is available.”
BackgroundDistributed Optimization for Control
Nedić, A., & Liu, J. (2018) · Annual Review of Control, Robotics, and Autonomous Systems · doi:10.1146/annurev-control-060117-105131 · Cited by 302
1Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed GraphsPreprint
Nedić, A., & Olshevsky, A. (2016) · Cited by 312
Distributed Optimization Based on a Multiagent System in the Presence of Communication Delays
Yang, S., Liu, Q., & Wang, J. (2017) · IEEE Transactions on Systems, Man, and Cybernetics: Systems · doi:10.1109/tsmc.2016.2531649 · Cited by 289
Designing Games for Distributed Optimization
Li, N., & Marden, J. R. (2013) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2013.2246511 · Cited by 290
“ular, the algorithms presented in [27] and [32] introduce a com-”
MethodResultA Linear Algorithm for Optimization Over Directed Graphs With Geometric Convergence
Xin, R., & Khan, U. A. (2018) · IEEE Control Systems Letters · doi:10.1109/lcsys.2018.2834316 · Cited by 243
A Collective Neurodynamic Approach to Distributed Constrained Optimization
Liu, Q., Yang, S., & Wang, J. (2017) · IEEE Transactions on Neural Networks and Learning Systems · doi:10.1109/tnnls.2016.2549566 · Cited by 262
Distributed constrained optimal consensus of multi-agent systems
Qiu, Z., Liu, S., & Xie, L. (2016) · Automatica · doi:10.1016/j.automatica.2016.01.055 · Cited by 261
“Here we only require α( t ) to be non-integrable, in contrast to the case of being non-summable but square summable in many existing works (Lobel & Ozdaglar, 2011; Nedic et al., 2010).”
MethodOnline Optimal Generation Control Based on Constrained Distributed Gradient Algorithm
Zhang, W., Liu, W., Wang, X., Liu, L., & Ferrese, F. (2015) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2014.2319315 · Cited by 235
“Some of them consider only equality constraints (1b) [22] while others only concern inequality constraints (1c) [23]–[26].”
BackgroundEvent-triggered zero-gradient-sum distributed consensus optimization over directed networks
Chen, W., & Ren, W. (2016) · Automatica · doi:10.1016/j.automatica.2015.11.015 · Cited by 234
Zeng, X., Yi, P., & Hong, Y. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2628807 · Cited by 234
“, [1], [2]), continuous-time multi-agent solvers have recently been applied to distributed optimization problems as a promising and usefu l technique [3]–[8], thanks to the well-developed continuous-time stability theory.”
MethodDP-ADMM: ADMM-Based Distributed Learning With Differential Privacy
Huang, Z., Hu, R., Guo, Y., Chan-Tin, E., & Gong, Y. (2020) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2019.2931068 · Cited by 190
“ess and the scalability of data processing. As pointed out in recent studies [1], [2], existing approaches to decentralizing an optimization problem mainly consist of subgradient-based algorithms [3]–[5], Alternating Direction Method of Multipliers (ADMM) based algorithms [6]–[10], and composite of sub-gradient descen…”
BackgroundLinear Convergence in Optimization Over Directed Graphs With Row-Stochastic Matrices
Xi, C., Mai, V. S., Xin, R., Abed, E. H., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2797164 · Cited by 215
ADD-OPT: Accelerated Distributed Directed Optimization
Xi, C., Xin, R., & Khan, U. A. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2737582 · Cited by 181
Convergence of Asynchronous Distributed Gradient Methods Over Stochastic Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2730481 · Cited by 214
“In line with these works, Nedic and Ozdaglar [12] applied consensus theory to optimization problems, where each agent only knows the cost of itself and aims to minimize the sum of the costs of all agents through cooperation with others.”
MethodInfluentialDistributed Adaptive Convex Optimization on Directed Graphs via Continuous-Time Algorithms
Li, Z., Ding, Z., Sun, J., & Li, Z. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2750103 · Cited by 211
Communication-efficient algorithms for decentralized and stochastic optimization
Lan, G., Lee, S., & Zhou, Y. (2020) · Mathematical Programming · doi:10.1007/s10107-018-1355-4 · Cited by 187
“ng agents to propagate the distributed information to every location in the network. One of the most well-studied techniques in decentralized optimization are the subgradient based methods (see e.g., [39,35,57,37,14,27,52]), where at each step a local subgradient is taken at each node, followed by the communication wi…”
Distributed secure state estimation for cyber–physical systems under sensor attacks
An, L., & Yang, G.-H. (2019) · Automatica · doi:10.1016/j.automatica.2019.06.019 · Cited by 191
Liu, Q., Yang, S., & Hong, Y. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2681200 · Cited by 184
“In the literature, several consensus algorithms have been proposed for distributed optimization [2], [3].”
BackgroundDistributed Random Projection Algorithm for Convex Optimization
Lee, S., & Nedic, A. (2013) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2013.2247023 · Cited by 184
Online Distributed Convex Optimization on Dynamic Networks
Hosseini, S., Chapman, A., & Mesbahi, M. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2525928 · Cited by 179
“In this direction, a class of distributed sub-gradient algorithms for convex optimizat ion has been developed [7], [8], [9], [10], [11].”
BackgroundNon-Convex Distributed Optimization
Tatarenko, T., & Touri, B. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2648041 · Cited by 171
“We refer the reader to the following papers that consider various settings on network topology, asynchronous updating rules, and noisy communication [5], [8], [15], [16], [23], [32], [35].”
BackgroundInfluentialA Saddle Point Algorithm for Networked Online Convex Optimization
Koppel, A., Jakubiec, F. Y., & Ribeiro, A. (2015) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2015.2449255 · Cited by 164
“A simple local gradient descent policy can achieve small regret with respect to the optimal local action x̃i = argminx ∑T t=1 fi,t(x) [12] .”
BackgroundDistributed multi-agent optimization with state-dependent communication
Lobel, I., Ozdaglar, A., & Feijer, D. (2011) · Mathematical Programming · doi:10.1007/s10107-011-0467-x · Cited by 162
“This is in contrast to the analysis of multi-agent algorithms over exogenously varying network topologies where it is possible to provide error bounds on the difference between the limiting objective function values of agent estimates and the optimal value as a function of the constant stepsize α (see [15]).”
BackgroundMethodResultInfluentialSelf-citationDistributed Time-Varying Quadratic Optimization for Multiple Agents Under Undirected Graphs
Sun, C., Ye, M., & Hu, G. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2673240 · Cited by 160
Li, H., Liu, S., Soh, Y. C., & Xie, L. (2017) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2017.2694323 · Cited by 157
“Early consensusbased distributed optimization algorithms, however, usually assume that the agent could perfectly obtain the information from its neighboring ones [5], [6], [11], [12], which implies that the communication channel has infinite communication bandwidth.”
BackgroundMethodA fast distributed proximal-gradient method
Chen, A. I., & Ozdaglar, A. (2012) · 2012 50th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2012.6483273 · Cited by 154
Self-citationDecentralized Optimization Over Time-Varying Directed Graphs With Row and Column-Stochastic Matrices
Saadatniaki, F., Xin, R., & Khan, U. A. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.2969721 · Cited by 170
“Early work on time-varying communication among the agents can be found in [11] and [38], where the exchange is undirected and in [18], where the exchange is directed.”
BackgroundAybat, N. S., Wang, Z., Lin, T., & Ma, S. (2017) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2017.2713046 · Cited by 170
“, see [27] and [28] for distributed optimization on directed graphs, and [29] for computation over random networks.”
BackgroundWang, Z., Wu, W., & Zhang, B. (2015) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2015.2493638 · Cited by 138
“efficiently in a distributed manner by using the subgradient algorithm [33]–[35].”
MethodPrimal–dual algorithm for distributed constrained optimization
Lei, J., Chen, H.-F., & Fang, H. (2016) · Systems & Control Letters · doi:10.1016/j.sysconle.2016.07.009 · Cited by 148
Distributed Convex Optimization with Inequality Constraints over Time-Varying Unbalanced Digraphs
Xie, P., You, K., Tempo, R., Song, S., & Wu, C. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2816104 · Cited by 133
Fault-Tolerant Multi-Agent Optimization: Optimal Iterative Distributed Algorithms
Su, L., & Vaidya, N. H. (2016) · Proceedings of the 2016 ACM Symposium on Principles of Distributed Computing · doi:10.1145/2933057.2933105 · Cited by 125
“Although the basic evolution relation has been obtained for failure-free distributed algorithms [9, 19, 31, 15], since our effective objective function is time-dependent ( p ( · ) in (11)), their analysis does not apply directly to our problem.”
BackgroundInfluentialOnline distributed optimization via dual averaging
Hosseini, S., Chapman, A., & Mesbahi, M. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760092 · Cited by 163
“Recently, there has grown an extensive literature on distributed convex optimization.”
BackgroundPassivity-Based Distributed Optimization With Communication Delays Using PI Consensus Algorithm
Hatanaka, T., Chopra, N., Ishizaki, T., & Li, N. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2823264 · Cited by 130
Distributed optimization over directed graphs with row stochasticity and constraint regularity
Mai, V. S., & Abed, E. H. (2019) · Automatica · doi:10.1016/j.automatica.2018.07.020 · Cited by 137
Hong, M., Hajinezhad, D., & Zhao, M. (2017) · doi:10.13140/rg.2.2.25204.14729 · Cited by 120
“Subsequently, many variants of DSG have been proposed, either with special assumptions on the underlying graph, or having additional structures of the problem; see, e.g., (Lobel & Ozdaglar, 2011; Lobel et al., 2011; Nedic & Olshevsky, 2015).”
BackgroundZONE: Zeroth-Order Nonconvex Multiagent Optimization Over Networks
Hajinezhad, D., Hong, M., & Garcia, A. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2896025 · Cited by 135
“Other related algorithms can be found in [9]–[11].”
BackgroundEnabling Privacy-Preservation in Decentralized Optimization
Zhang, C., & Wang, Y. (2019) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2018.2873152 · Cited by 124
Distributed Subgradient-Based Coordination of Multiple Renewable Generators in a Microgrid
Xu, Y., Zhang, W., Liu, W., Wang, X., Ferrese, F. T., Zang, C., & Yu, H. (2013) · IEEE Transactions on Power Systems · doi:10.1109/tpwrs.2013.2281038 · Cited by 124
“In this paper, the coordination of multiple RGs in a microgrid is formulated as a convex optimization problem that can be solved using the distributed subgradient algorithm introduced in [21]–[23].”
MethodAccelerated Dual Descent for Network Flow Optimization
Zargham, M., Ribeiro, A., Ozdaglar, A., & Jadbabaie, A. (2014) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2013.2293221 · Cited by 111
“Analysis of subgradient methods for distributed convex optimization can be found in [14] and [15] with the latter taking into account uncertainty in the network structure.”
Self-citationAchieving Pareto Optimality Through Distributed Learning
Marden, J. R., Young, H. P., & Pao, L. Y. (2014) · SIAM Journal on Control and Optimization · doi:10.1137/110850694 · Cited by 108
Distributed Optimization for Smart Cyber-Physical Networks
Notarstefano, G., Notarnicola, I., & Camisa, A. (2019) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000020 · Cited by 122
Distributed Optimal Coordination for Heterogeneous Linear Multiagent Systems
An, L., & Yang, G. (2021) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2021.3133269 · Cited by 105
Bastianello, N., Carli, R., Schenato, L., & Todescato, M. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3011358 · Cited by 119
“ms is that of (sub)gradient- and Newton-based methods. Distributed gradient descent algorithms in general combine local gradient descent steps with consensus averaging, see for example [3], [4], [5], [6], [7], [8], [9], [10], [11], [12], [13], [14]. These algorithms can handle many different scenarios, with smooth and…”
BackgroundRecycled ADMM: Improving the Privacy and Accuracy of Distributed Algorithms
Zhang, X., Khalili, M. M., & Liu, M. (2019) · IEEE Transactions on Information Forensics and Security · doi:10.1109/tifs.2019.2947867 · Cited by 105
Differentially Private Distributed Online Algorithms Over Time-Varying Directed Networks
Zhu, J., Xu, C., Guan, J., & Wu, D. O. (2018) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2018.2797806 · Cited by 111
Multiobjective Distributed Optimization via a Predefined-Time Multiagent Approach
Liu, Y., Xia, Z., & Gui, W. (2023) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2023.3244122 · Cited by 100
“Some existing approaches deal with distributed optimization with constraints [7], [8], [9], [10], [11], [12], [13], some focus on the types of communication graphs [1], [2], [14], [15], [16], [17], and some consider general value-domain [4], [18].”
BackgroundAn Asynchronous Mini-Batch Algorithm for Regularized Stochastic Optimization
Feyzmahdavian, H. R., Aytekin, A., & Johansson, M. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2525015 · Cited by 136
Special Issue on “Distributed and Networked Control Systems”
Pang, C. K. (2015) · Asian Journal of Control · doi:10.1002/asjc.1056 · Cited by 99
Distributed Multiple Agent System Based Online Optimal Reactive Power Control for Smart Grids
Zhang, W., Liu, W., Wang, X., Liu, L., & Ferrese, F. T. (2014) · IEEE Transactions on Smart Grid · doi:10.1109/tsg.2014.2327478 · Cited by 94
“Compared with the interior-point method, the subgradient algorithm requires less memory and computation, and can be easily applied to large-scale problems with decomposition techniques [26].”
MethodAsynchronous Gossip-Based Random Projection Algorithms Over Networks
Lee, S., & Nedić, A. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2460051 · Cited by 97
“Literature Overview: Distributed projection-based algorithms for problem (1) have been studied in [10]–[19] for convex unconstrained problems, convex constrained problems with common (X = Xi) or distributed local constraint sets.”
BackgroundPrivacy Preservation in Distributed Subgradient Optimization Algorithms
Lou, Y., Yu, L., Wang, S., & Yi, P. (2017) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2017.2728644 · Cited by 101
A Distributed Control Method With Minimum Generation Cost for DC Microgrids
Wang, Z., Wu, W., & Zhang, B. (2016) · IEEE Transactions on Energy Conversion · doi:10.1109/tec.2016.2584649 · Cited by 87
“This algorithm has been proposed in [31] and [32], and applied to an AC microgrid in [33] and [34].”
BackgroundMethodA review of distributed optimization: Problems, models and algorithms
Zheng, Y., & Liu, Q. (2021) · Neurocomputing · doi:10.1016/j.neucom.2021.06.097 · Cited by 98
Ma, Q., Meng, Q., & Xu, S. (2023) · IEEE Transactions on Systems Man and Cybernetics Systems · doi:10.1109/tsmc.2023.3247456 · Cited by 86
“Some pioneering works include [3], [10], [16], [25], and [31] for discrete-time algorithms.”
BackgroundDistributed Linear Parameter Estimation: Asymptotically Efficient Adaptive Strategies
Kar, S., Moura, J. M. F., & Poor, H. V. (2013) · SIAM Journal on Control and Optimization · doi:10.1137/110848396 · Cited by 95
“The performance of existing distributed information processing and optimization schemes (see, for example, [5, 7, 15, 16, 17, 18, 21, 28, 29, 33, 35, 36, 37, 41, 42]) based on accurate knowledge of the sensed data statistics may suffer substantially in the face of such parametric uncertainties.”
Pang, Y., & Hu, G. (2019) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2019.2914025 · Cited by 90
Liu, Q., Le, X., & Li, K. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2948424 · Cited by 89
Distributed optimization over weighted directed graphs using row stochastic matrix
Mai, V. S., & Abed, E. H. (2016) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2016.7526803 · Cited by 100
Convergence Rate of Distributed Averaging Dynamics and Optimization in Networks
Nedić, A. (2015) · Foundations and Trends® in Systems and Control · doi:10.1561/2600000004 · Cited by 107
Distributed optimization over time-varying directed graphs
Nedic, A., & Olshevsky, A. (2013) · 52nd IEEE Conference on Decision and Control · doi:10.1109/cdc.2013.6760975 · Cited by 72
“Distributed optimization of a sum of convex functions has received a surge of interest in recent years [13], [15], [6], [11], [9], [10], [19], [12], [2], [16], [4].”
BackgroundSun, H., & Hong, M. (2019) · IEEE Transactions on Signal Processing · doi:10.1109/tsp.2019.2943230 · Cited by 82
Doan, T. T., Maguluri, S. T., & Romberg, J. (2020) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2020.3031018 · Cited by 81
Convergence Rates for Distributed Stochastic Optimization Over Random Networks
Jakovetić, D., Bajović, D., Sahu, A. K., & Kar, S. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8619228 · Cited by 82
“Distributed optimization over random networks has been studied in [4]–[6], [18].”
BackgroundA Distributed Stochastic Gradient Tracking Method
Pu, S., & Nedić, A. (2018) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2018.8618708 · Cited by 78
Asynchronous Optimization Over Heterogeneous Networks Via Consensus ADMM
Kumar, S., Jain, R., & Rajawat, K. (2016) · IEEE Transactions on Signal and Information Processing over Networks · doi:10.1109/tsipn.2016.2593896 · Cited by 77
“In general, distributed optimization algorithms are desig ned either in the primal [9], [11], [12], [13, Chap.”
MethodDistributed mirror descent method for multi-agent optimization with delay
Li, J., Chen, G., Dong, Z. Y., & Wu, Z. (2015) · Neurocomputing · doi:10.1016/j.neucom.2015.12.017 · Cited by 73
Cloud-Enabled Differentially Private Multiagent Optimization With Constraints
Hale, M., & Egerstedt, M. (2017) · IEEE Transactions on Control of Network Systems · doi:10.1109/tcns.2017.2751458 · Cited by 67
“For example, [10] allows for distributed optimization of nondifferentiable objectives with time-varying communication links, [11] considers a similar problem formulation in which communication links fail over time, and [12] uses a distributed Newton method to solve dynamic network utility maximization problems.”
MethodDistributed Optimization Methods for Multi-Robot Systems: Part 1—A Tutorial [Tutorial]
Shorinwa, O., Halsted, T., Yu, J., & Schwager, M. (2024) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2024.3358718 · Cited by 91
Perturbed proximal primal–dual algorithm for nonconvex nonsmooth optimization
Hajinezhad, D., & Hong, M. (2019) · Mathematical Programming · doi:10.1007/s10107-019-01365-4 · Cited by 62
Designing games for distributed optimization
Li, N., & Marden, J. R. (2011) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2011.6161053 · Cited by 60
“There are similarities between our contributions and the algorithmic structure of existing distributed algorithms [25], [28] where an underlying state space is introduced to estimate parameters relevant to the gradients.”
BackgroundYuan, D., Ho, D. W. C., & Hong, Y. (2016) · SIAM Journal on Control and Optimization · doi:10.1137/15m1048896 · Cited by 59
“As uncertainties always exist in communication and environment, stochastic or randomize algorithms also have been discussed for distributed optimization [13, 10].”
BackgroundStochastic Subgradient Algorithms for Strongly Convex Optimization Over Distributed Networks
Sayin, M. O., Vanli, N. D., Kozat, S. S., & Başar, T. (2017) · IEEE Transactions on Network Science and Engineering · doi:10.1109/tnse.2017.2713396 · Cited by 58
“…− λ 2 ||w∗ −wt,i||2 − λ 2 ||wt,i −wt||2 ] , (12) where (10) follows from the λ-strong convexity, i.e., Efi(w ∗) ≥ E [ fi(wt,i) + g T t,i(w ∗ −wt,i) + λ2 ||w∗ −wt,i|| 2 ] , (11) also follows from the λ-strong convexity, i.e., Efi(wt,i) ≥ E [ fi(wt) + ḡ T t,i(wt,i −wt) + λ2 ||wt,i −wt|| 2 ]…”
MethodAchieving pareto optimality through distributed learning
Marden, J. R., Young, H. P., & Pao, L. Y. (2012) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2012.6426834 · Cited by 56
Graph balancing for distributed subgradient methods over directed graphs
Makhdoumi, A., & Ozdaglar, A. (2015) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2015.7402401 · Cited by 63
“distributed sensor networks [6], coordination [13], and flow control [21]) have motivated a flurry of research on distributed approaches for solving optimization problems where the objective function is the sum of local objective functions of agents (nodes) that are connected through a network (see [7], [45], [44], [2…”
BackgroundSelf-citationA Survey of Distributed Optimization Methods for Multi-Robot SystemsPreprint
Halsted, T., Shorinwa, O., Yu, J., & Schwager, M. (2021) · arXiv (Cornell University) · doi:10.48550/arxiv.2103.12840 · Cited by 71
“As proven in [28], scheduling the step-size according to the rules ∑∞ k=1 αi(k) = ∞ and ∑∞ k=1 αi(k) 2 < ∞ with all robots’ step-sizes equal guarantees the asymptotic convergence of the robots’ optimization variables to the optimal joint solution, given the standard assumptions of a connected network, properly chosen…”
BackgroundA Bregman Splitting Scheme for Distributed Optimization Over Networks
Xu, J., Zhu, S., Soh, Y. C., & Xie, L. (2018) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2018.2805260 · Cited by 62
“In line with this work, Nedic and Ozdaglar applied consensus theory into the above DOP problem, where the communication network can be varying, leading to a well-known algorithm termed distributed subgradient method (DSM) [12].”
MethodInfluentialCavalcante, R. L. G., & Stańczak, S. (2013) · IEEE Journal of Selected Topics in Signal Processing · doi:10.1109/jstsp.2013.2246766 · Cited by 58
A Simple Distributed Power Control Algorithm for Cognitive Radio Networks
Xiao, Y., Bi, G., & Niyato, D. T. (2011) · IEEE Transactions on Wireless Communications · doi:10.1109/twc.2011.090611.102049 · Cited by 53
“Note that our algorithm is different from that proposed in [10] in which each SU needs to communicate with its nearby SUs to make decisions based on the “consensus" among them.”
MethodSurveying Game Theoretic Approaches for Wind Farm Optimization
Marden, J. R., Ruben, S. D., & Pao, L. Y. (2012) · AIAA Aerospace Sciences Meeting · doi:10.2514/6.2012-1154 · Cited by 53
Distributed sampled-data control of nonholonomic multi-robot systems with proximity networks
Liu, Z., Wang, L., Wang, J., Dong, D., & Xiaoming Hu, A. (2017) · Automatica · doi:10.1016/j.automatica.2016.11.027 · Cited by 53
Distributed iterative thresholding for ℓ0/ℓ1-regularized linear inverse problems
Ravazzi, C., Fosson, S. M., & Magli, E. (2015) · IEEE Transactions on Information Theory · doi:10.1109/tit.2015.2403263 · Cited by 54
“We distinguish two classes: 1) algorithms based on the decentralization of subgradient methods for convex optimization (DSM, [29], [33], [34]); 2) consensus and distributed ADMM ([30], [43], [44]); Algorithm 2 DISTA Given a row-stochastic matrix P adapted to the graph, 1) DSM: As has been said, our…”
BackgroundMethodLi, H., Jin, B., & Yan, W. (2020) · Automatica · doi:10.1016/j.automatica.2020.109422 · Cited by 51
Fast Distributed First-Order Methods
Chen, A. I.-A. (2012) · DSpace@MIT (Massachusetts Institute of Technology) · Cited by 69
Distributed Optimization Methods for Multi-Robot Systems: Part 2—A Survey
Shorinwa, O., Halsted, T., Yu, J., & Schwager, M. (2024) · IEEE Robotics & Automation Magazine · doi:10.1109/mra.2024.3352852 · Cited by 68
“As proven in [36] while stopping criterion is not satisfied square-summable but not summable, then the optimization variables of all robots converge to the optimal joint solution, given the standard assumptions of a connected network, properly chosen weights, and bounded (sub)-gradients.”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs
Nedić, A., & Olshevsky, A. (2016) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2016.2529285 · Cited by 183
“Our work here contributes to the growing literature on distributed methods for optimization over networks [5], [9], [12], [14]–[16], [19]–[23], [28], [32], [34], [40], [43].”
MethodLei, J., Chen, H.-F., & Fang, H. (2018) · SIAM Journal on Control and Optimization · doi:10.1137/16m1086133 · Cited by 51
“A unconstrained cooperative optimization problem is investigated in [7] and [8] over the deterministic and the random switching networks, respectively.”
BackgroundA Novel Multiagent Neurodynamic Approach to Constrained Distributed Convex Optimization
Ma, L., & Bian, W. (2019) · IEEE Transactions on Cybernetics · doi:10.1109/tcyb.2019.2895885 · Cited by 47
Le, X., Yan, Z., & Xi, J. (2017) · IEEE Transactions on Emerging Topics in Computational Intelligence · doi:10.1109/tetci.2017.2716377 · Cited by 46
“Lobel and Ozdaglar discussed multiagent optimization with stochastic link failures [14].”
BackgroundSpiridonoff, A., Olshevsky, A., & Paschalidis, I. C. (2018) · PubMed · doi:10.48550/arxiv.1811.03982 · Cited by 65
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.