Distributed Algorithms for Computing a Common Fixed Point of a Group of Nonexpansive Operators

This article addresses the problem of seeking a common fixed point for a finite collection of nonexpansive operators over time-varying multi-agent networks in real Hilbert spaces. Each operator is assumed to be only privately and approximately known to each individual agent, and all agents need to cooperate to solve this problem by local communications over time-varying networks. To handle this problem, inspired by the centralized inexact Krasnoselski˘ı–Mann iteration, we propose a distributed algorithm, called distributed inexact averaged operator algorithm (DIO). It is shown that the DIO can converge weakly to a common fixed point of the family of nonexpansive operators. Moreover, under the assumption that all operators and their own fixed point sets are (boundedly) linearly regular, it is proved that the distributed averaged operator algorithm converges with a rate O(γ^log16(4k)) for some constant γ ∈ (0, 1), where k is the iteration number. To reduce computational complexity, a scenario, where only a random part of coordinates of each operator is computed at each iteration, is further considered. In this case, a corresponding algorithm, named distributed block-coordinate inexact averaged operator algorithm, is developed. The algorithm is proved to be weakly convergent to a common fixed point of the group of considered operators almost surely, and, with the extra assumption of (bounded) linear regularity, the distributed block-coordinate averaged operator algorithm is convergent in the mean square sense with a rate O(η^log4(4k)) for some constant η ∈ (0, 1). Furthermore, it is shown that the same convergence rates can still be guaranteed under a more relaxed (bounded) power regularity condition. A couple of examples are finally presented to illustrate the effectiveness of the proposed algorithms.