| 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. |
|