Randomized Gradient-Free Distributed Optimization Methods for a Multiagent System With Unknown Cost Function

This paper proposes a randomized gradient-free distributed optimization algorithm to solve a multiagent optimization problem with set constraints. Random gradient-free oracle instead of the true gradient information is built locally such that the estimated gradient information is utilized in guiding the update of decision variables. Thus, the algorithm requires no explicit expressions but only local measurements of the cost functions. The row-stochastic and column-stochastic matrices are used as the weighting matrices during the communication with neighbors, making the algorithm convenient to implement in directed graphs as compared with the doubly stochastic weighting matrix. Without the true gradient information, we establish asymptotic convergence to the approximated optimal solution, where the optimality gap can be set arbitrarily small. Moreover, it is shown that the proposed algorithm achieves the same rate of convergence $O(\ln t/\sqrt{t})$ as the state-of-the-art gradient-based methods with similar settings, but having the advantages of less required information and more practical communication topologies.