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

Research output: Journal Publications and Reviews (RGC: 21, 22, 62)21_Publication in refereed journalpeer-review

2 Scopus Citations
View graph of relations

Author(s)

Related Research Unit(s)

Detail(s)

Original languageEnglish
Article number9126183
Pages (from-to)2130-2145
Journal / PublicationIEEE Transactions on Automatic Control
Volume66
Issue number5
Online published25 Jun 2020
Publication statusPublished - May 2021

Abstract

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.

Research Area(s)

  • Distributed algorithms, fixed point, Krasnoselski˘ı–Mann iteration, multi-agent networks, nonexpansive operators, optimization