This paper explores the fundamental properties of distributed minimization of a sum of functions with each function only known to one node, and a pre-specified level of node knowledge and computational capacity. We define the optimization information each node receives from its objective function, the neighboring information each node receives from its neighbors, and the computational capacity each node can take advantage of in controlling its state. It is proven that there exist a neighboring information way and a control law that guarantee global optimal consensus if and only if the solution sets of the local objective functions admit a nonempty intersection set for fixed strongly connected graphs. Then we show that for any tolerated error, we can find a control law that guarantees global optimal consensus within this error for fixed, bidirectional, and connected graphs under mild conditions. For time-varying graphs, we show that optimal consensus can always be achieved as long as the graph is uniformly jointly strongly connected and the nonempty intersection condition holds. The results illustrate that nonempty intersection for the local optimal solution sets is a critical condition for successful distributed optimization for a large class of algorithms.
Consensus algorithms have been proven to be useful in the design of distributed optimization methods @cite_18 @cite_28 @cite_6 @cite_31 @cite_23 @cite_2 . Consensus methods have also been extensively studied for both discrete-time and continuous-time models in the past decade, some references related to the current paper include @cite_26 @cite_40 @cite_35 @cite_19 @cite_8 @cite_24 @cite_13 @cite_7 @cite_22 @cite_11 @cite_36 @cite_12 .
@cite_35 @cite_18 @cite_26 @cite_22 @cite_7 @cite_8 @cite_28 @cite_36 @cite_6 @cite_24 @cite_19 @cite_40 @cite_23 @cite_2 @cite_31 @cite_13 @cite_12 @cite_11
2950504271 2152755966 2034226907 2342494393
This paper introduces several new algorithms for consensus over the special orthogonal group. By relying on a convex relaxation of the space of rotation matrices, consensus over rotation elements is reduced to solving a convex problem with a unique global solution. The consensus protocol is then implemented as a distributed optimization using (i) dual decomposition, and (ii) both semi and fully distributed variants of the alternating direction method of multipliers technique -- all with strong convergence guarantees. The convex relaxation is shown to be exact at all iterations of the dual decomposition based method, and exact once consensus is reached in the case of the alternating direction method of multipliers. Further, analytic and or efficient solutions are provided for each iteration of these distributed computation schemes, allowing consensus to be reached without any online optimization. Examples in satellite attitude alignment with up to 100 agents, an estimation problem from computer vision, and a rotation averaging problem on @math validate the approach. We investigate the approximate consensus problem in highly dynamic networks in which topology may change continually and unpredictably. We prove that in both synchronous and partially synchronous networks, approximate consensus is solvable if and only if the communication graph in each round has a rooted spanning tree. Interestingly, the class of averaging algorithms, which have the benefit of being memoryless and requiring no process identifiers, entirely captures the solvability issue of approximate consensus in that the problem is solvable if and only if it can be solved using any averaging algorithm. We develop a proof strategy which for each positive result consists in a reduction to the nonsplit networks. It dramatically improves the best known upper bound on the decision times of averaging algorithms and yields a quadratic time non-averaging algorithm for approximate consensus in non-anonymous networks. We also prove that a general upper bound on the decision times of averaging algorithms have to be exponential, shedding light on the price of anonymity. Finally we apply our results to networked systems with a fixed topology and benign fault models to show that with n processes, up to @math of link faults per round can be tolerated for approximate consensus, increasing by a factor 2 the bound of Santoro and Widmayer for exact consensus. This paper presents analysis and design results for distributed consensus algorithms in multi-agent networks. We consider arbitrary consensus functions of the initial state of the network agents. Under mild smoothness assumptions, we obtain necessary and sufficient conditions characterizing any algorithm that asymptotically achieves consensus. This characterization is the building block to obtain various design results. We first identify a class of smooth functions for which one can synthesize in a systematic way distributed algorithms that achieve consensus. We apply this result to the family of weighted power mean functions, and characterize the exponential convergence properties of the resulting algorithms. We conclude with two distributed algorithms that achieve, respectively, max and min consensus in finite time. Consensus is a fundamental feature of distributed systems, and it is the prerequisite for several complex tasks, such as flocking of mobile robots, localization in wireless-sensor networks, or decentralized control of smart grids. Average consensus, in particular, is quite challenging, because it is typically obtained asymptotically, while few finite-time algorithms are available. In this paper, we provide a methodology to achieve distributed average consensus in finite time, while maintaining low computational and memory requirements, and small completion times. The provided solution, namely, finite-time average-consensus by iterated max-consensus (FAIM) is based on several runs of the max-consensus algorithm, and has low memory requirements for each node. Compared to existing Flooding approaches, the proposed algorithm requires less memory, at the cost of a slight increase in the number of steps required for termination. The FAIM algorithm assumes that the nodes are aware of an upper bound on the network diameter. To relax this assumption, we complement this paper with a novel distributed algorithm that, in the case of undirected graphs, provides an upper bound on the network diameter which, in the worst case, is twice the actual diameter. A comparison of the proposed finite-time algorithm against the state of the art concludes this paper.