Distributed convex optimization via continuous-time coordination algorithms with discrete-time communication

By Solmaz S. Kia, Jorge Cortés, Sonia Martínez. at - Automatisierungstechnik, 2014

675 citations recorded by the source corpus.

This paper proposes a novel class of distributed continuous-time coordination algorithms to solve network optimization problems whose cost function is a sum of local cost functions associated to the individual agents. We establish the exponential convergence of the proposed algorithm under (i) strongly connected and weight-balanced digraph topologies when the local costs are strongly convex with globally Lipschitz gradients, and (ii) connected graph topologies when the local costs are strongly convex with locally Lipschitz gradients. When the local cost functions are convex and the global cost function is strictly convex, we establish asymptotic convergence under connected graph topologies. We also characterize the algorithm's correctness under time-varying interaction topologies and study its privacy preservation properties. Motivated by practical considerations, we analyze the algorithm implementation with discrete-time communication. We provide an upper bound on the stepsize that guarantees exponential convergence over connected graphs for implementations with periodic communication. Building on this result, we design a provably-correct centralized event-triggered communication scheme that is free of Zeno behavior. Finally, we develop a distributed, asynchronous event-triggered communication scheme that is also free of Zeno with asymptotic convergence guarantees. Several simulations illustrate our results.

Subfields: Computer Networks and Communications

View Paper: https://www.semanticscholar.org/paper/5e4f8d22fd2d7142846a1c4400b0e8a841931eeb

How researchers see this paper

The researchers whose trusted networks rank it highest, strongest advocate first. Every researcher gets a different order.

In Computer Networks and Communications

1. Wei Ren
2. Ziyang Meng
3. Guanrong Chen
4. Yiguang Hong
5. Peng Lin
6. Jorge Cortés
7. Long Wang
8. Yongcan Cao

Citations in the corpus

• Distributed Continuous-Time Convex Optimization With Time-Varying Cost Functions (2015, background): “A proportional-integral al-gorithm is introduced in [10]–[12], where [11] considers strongly connected weight balanced directed graphs and [12] extends these results using discrete-time communication updates.”
• Distributed Continuous-Time Optimization: Nonuniform Gradient Gains, Finite-Time Convergence, and Convex Constraint Set (2017, background): “Founded on the work of [12], articles [13], [14] studied the distributed continuous-time optimization problem for general strongly connected balanced directed graphs and gave the estimate of the convergence rate of the algorithm.”
• A survey of distributed optimization (2019, methodology): “Most studies focused on the first-order multi-agent systems with single integrator agent dynamics. in Kia et al. (2015a) , the authors developed a distributed PI algorithm with an event-triggered communication strategy and established its exponential convergence to a neighborhood of an optimal point.”
• SPARQ-SGD: Event-Triggered and Compressed Communication in Decentralized Stochastic Optimization (2019, neutral): “The idea of event-triggered communication has been explored previously in the control community [HJT12, DFJ12, SDJ13, Gir15], [LNTL17] and in optimization literature [KCM15, CR16, DYG + 18].”
• Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems (2015, methodology): “…analysis techniques are inspired by the projected dynamical systems for variational inequalities (referring to Xia & Wang (2000) and Gao (2003)) and distributed optimization (referring to Shi, Johanssan, & Hong (2013 ), Kia, Cort´es, & Martinez (2015), Qiu, Liu, & Xie (2014) and Liu & Wang (2015)).”
• Event-triggered communication and control of networked systems for multi-agent consensus (2017, background): “More specifically, agents employ event-triggered communication to trade computation for reduced overall information exchange in finding a solution of the optimization problem (Chen & Ren, 2016; Kia, Cortés, & Martínez, 2015a; Liu & Chen, 2016; Richert & Cortés, 2016; Zhong & Cassandras, 2010).”
• Distributed Nash equilibrium seeking for aggregative games with coupled constraints (2016, background): “In recent years, continuoustime algorithms for distributed optimization become more and more popular (Shi et al. 2013, Kia et al. 2015, Yi, Hong & Liu 2016), partially because they may be easily implemented in continuous-time or hybrid physical systems.”