Decentralized conjugate gradients with finite-step convergence.
Alexander Engelmann, Timm Faulwasser · arXiv (Cornell University) · 2021
The decentralized solution of linear systems of equations arises as a subproblem in optimization over networks. Typical examples include the KKT system corresponding to equality constrained quadratic programs in distributed optimization algorithms or in active set methods. This note presents a tailored structure-exploiting decentralized variant of the conjugate gradient method. We show that the decentralized conjugate gradient method exhibits super-linear convergence in a finite number of steps. Finally, we illustrate the algorithm's performance in comparison to the Alternating Direction Method of Multipliers drawing upon examples from sensor fusion.