Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki
RUS  ENG    JOURNALS   PEOPLE   ORGANISATIONS   CONFERENCES   SEMINARS   VIDEO LIBRARY   PACKAGE AMSBIB  
General information
Latest issue
Archive
Impact factor

Search papers
Search references

RSS
Latest issue
Current issues
Archive issues
What is RSS



Zh. Vychisl. Mat. Mat. Fiz.:
Year:
Volume:
Issue:
Page:
Find






Personal entry:
Login:
Password:
Save password
Enter
Forgotten password?
Register


Zhurnal Vychislitel'noi Matematiki i Matematicheskoi Fiziki, 2024, Volume 64, Number 4, Pages 671–696
DOI: https://doi.org/10.31857/S0044466924040078
(Mi zvmmf11734)
 

Computer science

Alternating projection method for intersection of convex sets, multi-agent consensus algorithms, and averaging inequalities

A. V. Proskurnikova, I. S. Zabarianskab

a Politecnico di Torino, 10129, Turin, Italy
b St. Petersburg State University, 199178, St. Petersburg, Russia
Abstract: The history of the alternating projection method for finding a common point of several convex sets in Euclidean space goes back to the well-known Kaczmarz algorithm for solving systems of linear equations, which was devised in the 1930s and later found wide applications in image processing and computed tomography. An important role in the study of this method was played by I.I. Eremin’s, L.M. Bregman’s, and B.T. Polyak’s works, which appeared nearly simultaneously and contained general results concerning the convergence of alternating projections to a point in the intersection of sets, assuming that this intersection is nonempty. In this paper, we consider a modification of the convex set intersection problem that is related to the theory of multi-agent systems and is called the constrained consensus problem. Each convex set in this problem is associated with a certain agent and, generally speaking, is inaccessible to the other agents. A group of agents is interested in finding a common point of these sets, that is, a point satisfying all the constraints. Distributed analogues of the alternating projection method proposed for solving this problem lead to a rather complicated nonlinear system of equations, the convergence of which is usually proved using special Lyapunov functions. A brief survey of these methods is given, and their relation to the theorem ensuring consensus in a system of averaging inequalities recently proved by the second author is shown (this theorem develops convergence results for the usual method of iterative averaging as applied to the consensus problem).
Key words: alternating projection method, convex programming, Fejér mappings, distributed algorithms, consensus, multi-agent systems.
Funding agency Grant number
Russian Science Foundation 23-11-00229
This work was supported by the Russian Science Foundation, project no. 23-11-00229.
Received: 03.11.2023
Revised: 11.11.2023
Accepted: 20.11.2023
English version:
Computational Mathematics and Mathematical Physics, 2024, Volume 64, Issue 4, Pages 848–871
DOI: https://doi.org/10.1134/S0965542524700155
Bibliographic databases:
Document Type: Article
UDC: 519.85+517.97
Language: Russian
Citation: A. V. Proskurnikov, I. S. Zabarianska, “Alternating projection method for intersection of convex sets, multi-agent consensus algorithms, and averaging inequalities”, Zh. Vychisl. Mat. Mat. Fiz., 64:4 (2024), 671–696; Comput. Math. Math. Phys., 64:4 (2024), 848–871
Citation in format AMSBIB
\Bibitem{ProZab24}
\by A.~V.~Proskurnikov, I.~S.~Zabarianska
\paper Alternating projection method for intersection of convex sets, multi-agent consensus algorithms, and averaging inequalities
\jour Zh. Vychisl. Mat. Mat. Fiz.
\yr 2024
\vol 64
\issue 4
\pages 671--696
\mathnet{http://mi.mathnet.ru/zvmmf11734}
\crossref{https://doi.org/10.31857/S0044466924040078}
\elib{https://elibrary.ru/item.asp?id=74490708}
\transl
\jour Comput. Math. Math. Phys.
\yr 2024
\vol 64
\issue 4
\pages 848--871
\crossref{https://doi.org/10.1134/S0965542524700155}
Linking options:
  • https://www.mathnet.ru/eng/zvmmf11734
  • https://www.mathnet.ru/eng/zvmmf/v64/i4/p671
  • Citing articles in Google Scholar: Russian citations, English citations
    Related articles in Google Scholar: Russian articles, English articles
    Журнал вычислительной математики и математической физики Computational Mathematics and Mathematical Physics
     
      Contact us:
     Terms of Use  Registration to the website  Logotypes © Steklov Mathematical Institute RAS, 2024