Distributed Continuous-Time Convex Optimization on Weight-Balanced Digraphs

By Bahman Gharesifard, Jorge Cortés. IEEE Transactions on Automatic Control, 2012

797 citations recorded by the source corpus.

This technical note 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.

Subfields: Computer Networks and Communications, Electrical and Electronic Engineering

View Paper: https://www.semanticscholar.org/paper/1e4095da22f608499c9b4d94df506cb4f0fa1224

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

In Electrical and Electronic Engineering

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.”
A survey of distributed optimization (2019, methodology): “These algorithms are discrete-time counterparts of the continuous-time distributed PI algorithms proposed in Gharesifard and Cortés (2014) ; Kia, Cortés, and Martínez (2015a) ; Wang and Elia (2010) and Xie and Lin (2017) , which will be reviewed in Section 3.2 .”
Stochastic Gradient-Push for Strongly Convex Functions on Time-Varying Directed Graphs (2014, background): “a recent strand of the distributed optimization literature which studies effective protocols when interactions between nodes are unidirectional [6], [8], [10], [11], [36], [41].”
Initialization-free distributed algorithms for optimal resource allocation with feasibility constraints and application to economic dispatch of power systems (2015, methodology): “• In fact, proportional-integral (PI)-type consensus dynamics (Wang & Elia (2011) and Gharesifard & Cort´es (2014)) and projected gradient ﬂows (Liu & Wang (2015)), which both have been utilized for distributed optimization, are combined together to obtain the algorithm (9) for the KKT condition…”
Augmented distributed gradient methods for multi-agent optimization under uncoordinated constant stepsizes (2015, result): “where θ ∈ R is the global variable to be optimized, which is equivalent to solve the following problem [28]”
Distributed optimization for multi-task learning via nuclear-norm approximation (2015, background): “Literature review: The increasing body of literature on cooperative strategies for distributed convex optimization, see (Nedic and Ozdaglar, 2009; Boyd et al., 2011; Zhu and Mart́ınez, 2012; Gharesifard and Cortés, 2014) and references therein, renders itself naturally to large-scale problems like d”
A Distributed Approach to Maximum Power Point Tracking for Photovoltaic Submodule Differential Power Processing (2015, methodology): “Then, we tailor the distributed optimization algorithm in [20] to our setting.”
Network Topology and Communication-Computation Tradeoffs in Decentralized Optimization (2017, background): “Distributed convex optimization algorithms for weight-balanced directed graphs have been investigated in continuous-time [68].”
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.”
Distributed optimization over time-varying directed graphs (2013, positive): “The paper [5] shows the convergence of a distributed optimization protocol in continuous time, also for directed but fixed graphs; moreover, an additional assumption is made in [5] that the graph is “balanced.”
Linear Convergence Rate of a Class of Distributed Augmented Lagrangian Algorithms (2013, background): “References [18], [19], [20], [21] study distributed primal-dual methods that resemble ours when the number of inner iterations τ is set to one (but their methods are not the same.)”
Distributed Online Convex Optimization on Time-Varying Directed Graphs (2017, background): “In [18] and [19], motivated by the saddle-point dynamics in [21], a discrete-time distributed online convex optimization algorithm on weight-balanced network topologies is introduced; in particular, the suggested protocol in [19] works on jointly connected weight-balanced digraphs.”
Primal-Dual Algorithm for Distributed Reinforcement Learning: Distributed GTD (2018, methodology): “The proposed algorithm was also motivated by the continuous-time consensus optimization algorithm from [14]–[16], where the consensus equality constraint was introduced.”
A Second-Order Multi-Agent Network for Bound-Constrained Distributed Optimization (2015, methodology): “The Lyapunov method has been used for consensus analysis for first-order multi-agent network in [12].”