Continuous-time distributed convex optimization on weight-balanced digraphs
The DOI matches its Crossref record; 21 of the 21 references it cites were found in a registry or an index.
Abstract
This paper studies the continuous-time distributed optimization of a sum of convex functions over directed graphs. Contrary to what is known in the consensus literature, where the same dynamics works for both undirected and directed scenarios, we show that the consensus-based dynamics that solves the continuous-time distributed optimization problem for undirected graphs fails to converge when transcribed to the directed setting. This study sets the basis for the design of an alternative distributed dynamics which we show is guaranteed to converge, on any strongly connected weight-balanced digraph, to the set of minimizers of a sum of convex differentiable functions with globally Lipschitz gradients. Our technical approach combines notions of invariance and cocoercivity with the positive definiteness properties of graph matrices to establish the results.
Overview
Integrity signals
Registry
Cites
Statistics
Verification
Claims the paper makes
Citations
Cites
Boyd, S., & Vandenberghe, L. (2004) · doi:10.1017/cbo9780511804441 · Cited by 56,601
Horn, R. A., & Johnson, C. R. (1985) · Cited by 22,203
Consensus and Cooperation in Networked Multi-Agent Systems
Olfati-Saber, R., Fax, J. A., & Murray, R. M. (2007) · Proceedings of the IEEE · doi:10.1109/jproc.2006.887293 · Cited by 10,522 · cited 2×
“Nevertheless, it is natural to study whether the dynamics (6) enjoys the same convergence properties as in the undirected situation (as, for instance, is the case in the agreement problem [7], [8], [9], [10]).”
BackgroundHorn, R. A., & Johnson, C. R. (1985) · Cambridge University Press eBooks · doi:10.1017/cbo9780511810817 · Cited by 10,280
Distributed 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
Graph Theoretic Methods in Multiagent Networks
Mesbahi, M., & Egerstedt, M. (2010) · Princeton University Press eBooks · doi:10.1515/9781400835355 · Cited by 2,897 · cited 2×
“Nevertheless, it is natural to study whether the dynamics (6) enjoys the same convergence properties as in the undirected situation (as, for instance, is the case in the agreement problem [7], [8], [9], [10]).”
BackgroundDistributed Consensus in Multi-vehicle Cooperative Control
Ren, W., & Beard, R. W. (2008) · Communications and Control Engineering · doi:10.1007/978-1-84800-015-5 · Cited by 2,826 · cited 2×
“Nevertheless, it is natural to study whether the dynamics (6) enjoys the same convergence properties as in the undirected situation (as, for instance, is the case in the agreement problem [7], [8], [9], [10]).”
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
Distributed Control of Robotic Networks: A Mathematical Approach to Motion Coordination Algorithms
Bullo, F., Cortés, J., & Martínez, S. (2009) · Princeton University Press eBooks · doi:10.1515/9781400831470 · Cited by 1,509
Discontinuous dynamical systems
(2008) · IEEE Control Systems · doi:10.1109/mcs.2008.919306 · Cited by 1,068
Research works printed but not linked: 2
- khalil, 2002, Nonlinear Systems
- rockafellar, 1997, Convex Analysis
Cited by
Distributed 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
Network 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
A Distributed Algorithm for Solving a Linear Algebraic Equation
Mou, S., Liu, J., & Morse, A. S. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2015.2414771 · Cited by 284
Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms
Jakovetic, D., Moura, J. M. F., & Xavier, J. (2015) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2014.2363299 · Cited by 123
Continuous-time proportional-integral distributed optimisation for networked systems
Droge, G. N., Kawashima, H., & Egerstedt, M. (2014) · Journal of Control and Decision · doi:10.1080/23307706.2014.926622 · Cited by 78
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
A distributed hierarchical algorithm for multi-cluster constrained optimization
Guo, F., Wen, C., Mao, J., Li, G., & Song, Y. (2017) · Automatica · doi:10.1016/j.automatica.2016.11.029 · Cited by 56
Distributed optimization with the consideration of adaptivity and finite-time convergence
Lin, P., Ren, W., Song, Y., & Farrell, J. A. (2014) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2014.6858932 · Cited by 41
A distributed algorithm for solving a linear algebraic equation
Mou, S., Liu, J., & Morse, A. S. (2013) · Allerton Conference on Communication, Control, and Computing · doi:10.1109/allerton.2013.6736534 · Cited by 27
Shi, X., Wang, Y., Song, S., & Yan, G. (2018) · International Journal of Systems Science · doi:10.1080/00207721.2018.1439124 · Cited by 26
Mou, S., Lin, Z., Wang, L., Fullmer, D., & Morse, A. S. (2016) · Systems & Control Letters · doi:10.1016/j.sysconle.2016.05.011 · Cited by 25
Path Planning with Time Windows for Multiple UAVs Based on Gray Wolf Algorithm
Zhang, C., Liu, Y., & Hu, C. (2022) · Biomimetics · doi:10.3390/biomimetics7040225 · Cited by 24
Continuous-time distributed algorithms for solving linear algebraic equation
Cao, K., Zeng, X., & Hong, Y. (2017) · Chinese Control Conference (CCC) · doi:10.23919/chicc.2017.8028633 · Cited by 22
Parallel alternating direction method of multipliers
Yan, J., Guo, F., Wen, C., & Li, G. (2019) · Information Sciences · doi:10.1016/j.ins.2019.08.039 · Cited by 22
Nedić, A. (2015) · Springer eBooks · doi:10.1007/978-1-4471-5058-9_219 · Cited by 10
Noise-to-state exponentially stable distributed convex optimization on weight-balanced digraphs
Mateos‐Núñez, D., & Cortés, J. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760304 · Cited by 9
Proportional integral distributed optimization for dynamic network topologies
Droge, G. N., & Egerstedt, M. (2014) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2014.6858826 · Cited by 8
Cascading Network Failure in Power Grid Blackouts
Dobson, I. (2015) · Springer eBooks · doi:10.1007/978-1-4471-5058-9_264 · Cited by 7
Decentralized Coordination Control for Dynamic Multiagent Systems
Kvaternik, K. (2015) · TSpace (University of Toronto) · Cited by 5
Domínguez-García, A. D., & Hadjicostis, C. N. (2015) · Springer eBooks · doi:10.1007/978-1-4471-5058-9_268 · Cited by 5
Nedić, A. (2021) · Springer eBooks · doi:10.1007/978-3-030-44184-5_219 · Cited by 3
Domínguez-García, A. D. (2014) · Springer eBooks · doi:10.1007/978-1-4471-5102-9_268-1 · Cited by 3
Multiagent Approach of the Demand Side Management Within the Microgrids
Zhavoronkov, A. A., Aksyonov, K. A., & Sitnikov, I. (2021) · Ural Symposium on Biomedical Engineering, Radioelectronics and Information Technology (USBEREIT) · doi:10.1109/usbereit51232.2021.9455026 · Cited by 2
Distributed optimization by myopic strategic interactions and the price of heterogeneity
Gharesifard, B., Touri, B., Başar, T., & Langbort, C. (2013) · IEEE Conference on Decision and Control (CDC) · doi:10.1109/cdc.2013.6760041 · Cited by 2
Self-citationPush-Pull Finite-Time Convergence Distributed Optimization Algorithm
Chen, X., Yan, K., Gao, Y. K., Xu, X., Yan, K., & Wang, J. (2020) · American Journal of Computational Mathematics · doi:10.4236/ajcm.2020.101008 · Cited by 1
Distributed Network Flow to Solve Constrained Linear Matrix Equation
Chai, Y., Feng, J., Xu, C. G., & Qin, S. (2021) · International Conference on Advanced Computational Intelligence (ICACI) · doi:10.1109/icaci52617.2021.9435868 · Cited by 1
Game Theory and Multi-Agent Optimization
Tatarenko, T. (2017) · Springer eBooks · doi:10.1007/978-3-319-65479-9_2
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
Distributed control of energy systems
Guo, F. (2016) · DR-NTU (Nanyang Technological University) · doi:10.32657/10356/69061
Domínguez-García, A. D., & Hadjicostis, C. N. (2021) · Springer eBooks · doi:10.1007/978-3-030-44184-5_268
Wang, C., Zhu, R., Wang, F., & Liu, Z. (2023) · Lecture notes in electrical engineering · doi:10.1007/978-981-99-6847-3_62
Distributed Jacobi-Proximal ADMM for Consensus Convex OptimizationPreprint
Xiao, X.-H., Deng, H., & Xu, Y. D. (2024) · Preprints.org · doi:10.20944/preprints202401.2201.v1
Metadata
- Authors
- Gharesifard, B., & Cortes, J.
- Affiliations
- University of California San Diego (US)
- ORCID
- Gharesifard, Bahman
- Venue
- 2012 IEEE 51st IEEE Conference on Decision and Control (CDC)
- Publisher
- IEEE
- Published
- 2012-12
- Pages
- 7451-7456
- ISSN
- 0191-2216 (ISSN-L)
- OpenAlex
- W1979062758
- Cited by
- 32
- References
- 21
- Citations by year
- 2024: 1 · 2023: 1 · 2022: 1 · 2021: 4 · 2020: 1 · 2019: 1 · 2018: 3 · 2017: 3 · 2016: 2 · 2015: 5 · 2014: 6 · 2013: 4
- FWCI
- 4.03
- Type
- conference paper
- Language
- en
- Open access
- closed
- Locations
- IEEE Conference on Decision and Control (CDC) (publishedVersion)
- Funders
- National Science Foundation
- Division of Civil, Mechanical and Manufacturing Innovation
- 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 › Extremum Seeking Control Systems
- Keywords
- distributed convex optimization, continuous-time dynamics, directed graphs, convergence analysis, invariance, graph matrices, strongly connected graphs, Lipschitz gradient
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.