Gradient-free method for distributed multi-agent optimization via push-sum algorithms

摘要

This paper studies the problem of minimizing the sum of convex functions that all share a common global variable, each function is known by one specific agent in the network. The underlying network topology is modeled as a time-varying sequence of directed graphs, each of which is endowed with a non-doubly stochastic matrix. We present a distributed method that employs gradient-free oracles and push-sum algorithms for solving this optimization problem. We establish the convergence by showing that the method converges to an approximate solution at the expected rate of O(lnT/root T), where T is the iteration counter. A numerical example is also given to illustrate the proposed method. Copyright (c) 2014 John Wiley & Sons, Ltd.