Distributed Deterministic Asynchronous Algorithms in Time-Varying Graphs Through Dykstra Splitting
C. H. Jeffrey Pang · SIAM Journal on Optimization · 2019
Consider a setting where each vertex of a graph has a function, and communications can only occur between vertices connected by an edge. We wish to minimize the sum of these functions. For the case when each function is the sum of a strongly convex quadratic and a convex function, we propose a distributed version of Dykstra's algorithm. The computations to optimize the dual objective function can run asynchronously without a global clock, and in a distributed manner without a central controller. Convergence to the primal minimizer is deterministic instead of being probabilistic, and is guaranteed as long as, in each cycle, the edges where two-way communications occur connect all vertices. We also look at an accelerated algorithm, and an algorithm for the case when the functions on the nodes are not strongly convex.