Special Session 34: 

Decentralized Consensus Algorithms for distributed optimization

Yunmei Chen
University of Florida
USA
Co-Author(s):    Chenxi Chen and Xiaojing Ye
Abstract:
We propose two decentralized consensus algorithms for solving a class of distributed optimization problems. The first one is based on deterministic primal-dual method that can achieve the rate of convergence O(1/N) for both objective and consensus, where $N$ is the number of iterations, The total cost of communication is O(Nmd), where m is the number of nodes in the network, and d is the degree of the network. To reduce the communication cost, we propose the second algorithm based on randomized primal-dual algorithm. This algorithm maintains the same rate of convergence for both objective and consensus at O(1/N), but with O(d) cost of communication for each iteration. Compared to the cost of communication of deterministic primal-dual based method, randomized primal-dual based method is capable to reduce the total communication cost by O(m). The numerical results indicate the effectiveness of the proposed methods.