Zeroth-order Gradient Tracking for Distributed Constrained Optimization

Abstract

Distributed optimization is an important and practical problem that arose from machine learning, smart grid, and multi-robot systems. In this paper, we propose a zeroth-order gradient tracking method to solve a class of constrained distributed optimization problems with nonidentical feasible sets. We design a more general pseudo-gradient estimation scheme, which includes the existing coordinate descent, discretized gradient descent, and spherical smoothing methods as its special cases. Moreover, we propose pseudo-gradient tracking with projection dynamics to deal with nonidentical feasible set constraints and achieve the optimal solution. We show the proposed algorithm achieves the optimal solution with an O(lnT/√T) convergence rate. Finally, we present an example to demonstrate the effectiveness of the proposed algorithm.