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
Distributed optimization in sensor networks
Rabbat, M., & Nowak, R. (2004) · Proceedings of the 3rd international symposium on Information processing in sensor networks · doi:10.1145/984622.984626 · Cited by 901 · cited 1×
“I. INTRODUCTION Distributed optimization of a sum of convex functions has applications in a variety of scenarios, including sensor networks, source localization, and robust estimation, and has been intensively studied in recent years, see e.g. [1], [2], [3], [4], [5], [6].”
BackgroundOn Distributed Convex Optimization Under Inequality and Equality Constraints
Zhu, M., & Martinez, S. (2012) · IEEE Transactions on Automatic Control · doi:10.1109/tac.2011.2167817 · Cited by 759
Distributed Control of Robotic Networks
Bullo, F. (2009) · Cited by 649
A control perspective for centralized and distributed convex optimization
Wang, J., & Elia, N. (2011) · IEEE Conference on Decision and Control and European Control Conference · doi:10.1109/cdc.2011.6161503 · Cited by 398
Discontinuous Dynamical Systems: A tutorial on solutions, nonsmooth analysis, and stability
Cortés, J. (2009) · arXiv (Cornell University) · doi:10.48550/arxiv.0901.3583 · Cited by 397
Control approach to distributed optimization
Wang, J., & Elia, N. (2010) · 2010 48th Annual Allerton Conference on Communication, Control, and Computing (Allerton) · doi:10.1109/allerton.2010.5706956 · Cited by 358
A Randomized Incremental Subgradient Method for Distributed Optimization in Networked Systems
Johansson, B., Rabi, M., & Johansson, M. (2010) · SIAM Journal on Optimization · doi:10.1137/08073038x · Cited by 336
Modified Lagrangians and Monotone Maps in Optimization
Golʹshteĭn, E. G., & Tret’yakov, N. V. (1996) · Medical Entomology and Zoology · Cited by 127
Event-triggered distributed optimization in sensor networks
Wan, P., & Lemmon, M. D. (2009) · Information Processing in Sensor Networks · doi:10.5555/1602165.1602172 · Cited by 101
Modified Lagrangians and monotone maps in optimization
(1996) · Computers & Mathematics with Applications · doi:10.1016/s0898-1221(96)90271-0 · Cited by 76
Distributed convergence to Nash equilibria by adversarial networks with undirected topologies
Gharesifard, B., & Cortés, J. (2012) · Proceedings of the ... American Control Conference/Proceedings of the American Control Conference · doi:10.1109/acc.2012.6315270 · Cited by 16
Self-citation
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
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.