This paper considers the problem of distributed optimization over
time-varying graphs. For the case of undirected graphs, we introduce a
distributed algorithm, referred to as DIGing, based on a combination of a
distributed inexact gradient method and a gradient tracking technique. The
DIGing algorithm uses doubly stochastic mixing matrices and employs fixed
step-sizes and, yet, drives all the agents' iterates to a global and consensual
minimizer. When the graphs are directed, in which case the implementation of
doubly stochastic mixing matrices is unrealistic, we construct an algorithm
that incorporates the push-sum protocol into the DIGing structure, thus
obtaining Push-DIGing algorithm. The Push-DIGing uses column stochastic
matrices and fixed step-sizes, but it still converges to a global and
consensual minimizer. Under the strong convexity assumption, we prove that the
algorithms converge at R-linear (geometric) rates as long as the step-sizes do
not exceed some upper bounds. We establish explicit estimates for the
convergence rates. When the graph is undirected it shows that DIGing scales
polynomially in the number of agents. We also provide some numerical
experiments to demonstrate the efficacy of the proposed algorithms and to
validate our theoretical findings.

本文考虑基于动态图的分布式优化问题，提出了 DIGing 和 Push-DIGing 算法来解决无向和有向图的问题，同时证明了在强凸性假设下，这些算法以几何级数的速率收敛。