We consider a multi agent optimization problem where a set of agents collectively solves a global optimization problem with the objective function given by the sum of locally known convex functions. We focus on the case when information exchange among agents takes place over a directed network and propose a distributed subgradient algorithm in which each agent performs local processing based on information obtained from his incoming neighbors. Our algorithm uses weight balancing to overcome the asymmetries caused by the directed communication network, i.e., agents scale their outgoing information with dynamically updated weights that converge to balancing weights of the graph. We show that both the objective function values and the consensus violation, at the ergodic average of the estimates generated by the algorithm, converge with rate @math , where @math is the number of iterations. A special case of our algorithm provides a new distributed method to compute average consensus over directed graphs.
Our work also contributes to the vast literature on the consensus problem, where agents have a more specific goal of aligning their estimates (see @cite_34 @cite_39 @cite_11 @cite_10 for consensus over undirected graphs and @cite_7 @cite_51 @cite_55 for consensus over directed graphs). In particular, a special case of our algorithm provides a new distributed method for computing average of initial values over a directed graph. Out contribution here is most closely related to @cite_2 and @cite_23 , which proposed distributed algorithms for average consensus over directed graphs using balancing weights. Reference @cite_2 builds on earlier work @cite_15 , which presented a distributed algorithm for computing balancing node weights based on approximating the left eigenvector associated with the zero eigenvalue of the Laplacian matrix of the underlying directed network. In @cite_2 , the authors used this algorithm for updating weights in the same time scale as the update for estimates and showed convergence to average of initial values. Reference @cite_23 provides a similar algorithm for average consensus based on an earlier work @cite_14 , which proposes an update rule for computing balancing edge weights.
@cite_14 @cite_7 @cite_55 @cite_39 @cite_23 @cite_2 @cite_51 @cite_15 @cite_34 @cite_10 @cite_11
2114791779 2064403618 2151685478 2763281404
We present distributed algorithms that can be used by multiple agents to align their estimates with a particular value over a network with time-varying connectivity. Our framework is general in that this value can represent a consensus value among multiple agents or an optimal solution of an optimization problem, where the global objective function is a combination of local agent objective functions. Our main focus is on constrained problems where the estimates of each agent are restricted to lie in different convex sets. To highlight the effects of constraints, we first consider a constrained consensus problem and present a distributed "projected consensus algorithm" in which agents combine their local averaging operation with projection on their individual constraint sets. This algorithm can be viewed as a version of an alternating projection method with weights that are varying over time and across agents. We establish convergence and convergence rate results for the projected consensus algorithm. We next study a constrained optimization problem for optimizing the sum of local objective functions of the agents subject to the intersection of their local constraint sets. We present a distributed "projected subgradient algorithm" which involves each agent performing a local averaging operation, taking a subgradient step to minimize its own objective function, and projecting on its constraint set. We show that, with an appropriately selected stepsize rule, the agent estimates generated by this algorithm converge to the same optimal solution for the cases when the weights are constant and equal, and when the weights are time-varying but all agents have the same constraint set. In this work we propose a distributed algorithm to solve the discrete-time average consensus problem on strongly connected weighted digraphs (SCWDs). The key idea is to couple the computation of the average with the estimation of the left eigenvector associated with the zero eigenvalue of the Laplacian matrix according to the protocol described in (2012). The major contribution is the removal of the requirement of the knowledge of the out-neighborhood of an agent, thus paving the way for a simple implementation based on a pure broadcast-based communication scheme. We consider a stochastic model for distributed average consensus, which arises in applications such as load balancing for parallel processors, distributed coordination of mobile autonomous agents, and network synchronization. In this model, each node updates its local variable with a weighted average of its neighbors' values, and each new value is corrupted by an additive noise with zero mean. The quality of consensus can be measured by the total mean-square deviation of the individual variables from their average, which converges to a steady-state value. We consider the problem of finding the (symmetric) edge weights that result in the least mean-square deviation in steady state. We show that this problem can be cast as a convex optimization problem, so the global solution can be found efficiently. We describe some computational methods for solving this problem, and compare the weights and the mean-square deviations obtained by this method and several other weight design methods. When solving consensus optimization problems over a graph, there is often an explicit characterization of the convergence rate of Gradient Descent (GD) using the spectrum of the graph Laplacian. The same type of problems under the Alternating Direction Method of Multipliers (ADMM) are, however, poorly understood. For instance, simple but important non-strongly-convex consensus problems have not yet being analyzed, especially concerning the dependency of the convergence rate on the graph topology. Recently, for a non-strongly-convex consensus problem, a connection between distributed ADMM and lifted Markov chains was proposed, followed by a conjecture that ADMM is faster than GD by a square root factor in its convergence time, in close analogy to the mixing speedup achieved by lifting several Markov chains. Nevertheless, a proof of such a claim is is still lacking. Here we provide a full characterization of the convergence of distributed over-relaxed ADMM for the same type of consensus problem in terms of the topology of the underlying graph. Our results provide explicit formulas for optimal parameter selection in terms of the second largest eigenvalue of the transition matrix of the graph's random walk. Another consequence of our results is a proof of the aforementioned conjecture, which interestingly, we show it is valid for any graph, even the ones whose random walks cannot be accelerated via Markov chain lifting.