Distributed Banach-Picard Iteration for Locally Contractive Maps

• 成果类型: Article
• 署名作者: Andrade, Francisco; Figueiredo, Mario A. T.; Xavier, Joao
• 署名单位: Universidade de Lisboa; Instituto de Telecomunicacoes; Universidade de Lisboa; Universidade de Coimbra
• 刊物名称: IEEE TRANSACTIONS ON AUTOMATIC CONTROL
• ISSN/ISSBN: 0018-9286
• DOI: 10.1109/TAC.2022.3152722
• 发表日期: 2023
• 页码: 1275-1280
• 关键词: convergence; Distributed algorithms; optimization; Jacobian matrices; Perturbation methods; Distributed databases; Symmetric matrices; Banach-Picard iteration; consensus; Distributed computation; Fixed points; perturbation theory (PT) of linear operators

摘要

The Banach-Picard iteration is widely used to find fixed points of locally contractive (LC) maps. This article extends the Banach-Picard iteration to distributed settings; specifically, we assume the map of which the fixed point is sought to be the average of individual (not necessarily LC) maps held by a set of agents linked by a communication network. An additional difficulty is that the LC map is not assumed to come from an underlying optimization problem, which prevents exploiting strong global properties, such as convexity or Lipschitzianity. Yet, we propose a distributed algorithm and prove its convergence, in fact showing that it maintains the linear rate of the standard Banach-Picard iteration for the average LC map. As another contribution, our proof imports tools from perturbation theory of linear operators, which, to the best of our knowledge, are scarcely exploited in the theory of distributed computation.