Alternating Projection Method for Intersection of Convex Sets, Multi-Agent Consensus Algorithms and Averaging Inequalities

Мұқаба

Дәйексөз келтіру

Толық мәтін

Ашық рұқсат Ашық рұқсат
Рұқсат жабық Рұқсат берілді
Рұқсат жабық Тек жазылушылар үшін

Аннотация

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 first author is shown (this theorem develops convergence results for the usual method of iterative averaging as applied to the consensus problem).

Толық мәтін

Рұқсат жабық

Авторлар туралы

A. Proskurnikov

Politecnico di Torino

Хат алмасуға жауапты Автор.
Email: avp1982@gmail.com
Италия, Torino

I. Zabaryanskaya

Saint Petersburg State University

Email: akshiira@yandex.ru
Ресей, Saint Petersburg

Әдебиет тізімі

  1. Gordon R., Bender R., Herman G. T. Algebraic Reconstruction Techniques (ART) for three-dimensional electron microscopy and X-ray photography // Journal of Theoretical Biology. 1970. Т. 29. No 3. С. 471—481.
  2. Гелиг А. Х., Матвеев А. С. Введение в математическую теорию обучаемых распознающих систем и нейронных сетей. СПб.: Изд-во СПбГУ, 2014.
  3. Якубович В. А. Некоторые общие теоретические принципы построения обучаемых опознающих систем // Вычислительная техника и вопросы программирования. Ленинград: Изд-во ЛГУ. 1965. С. 3—71.
  4. Demyanov V. F. Mathematical diagnostics via nonsmooth analysis // Optimization Methods and Software. — 2005. Т. 20. No 2/3. С. 197—218.
  5. Оптимизационные методы в задачах диагностики / К. И. Ананьев [и др.] // Вестник СПбГУ. Прикл. матем. Информ. Проц. упр. 2011. Т. 10. No 3. С. 3—12.
  6. Малоземов В. Н., Плоткин А. В. Строгое полиномиальное отделение двух множеств // Вестник СПбГУ. Математика. Механика. Астрономия. 2019. Т. 6, No 2. С. 232—240.
  7. Combettes P. L. The Foundations of Set Theoretic Estimation // Proceedings of IEEE. 1993. Т. 81. No 2. С. 182—208.
  8. Петров И. П., Тимофеев А. В. Конечно-сходящиеся рекуррентные алгоритмы решения целевых неравенств при наличии ограничений // Ж. вычисл. матем. и матем. физ. 1975. Т. 15. No 6. С. 1582—1588.
  9. Фомин В. Н., Фрадков А. Л., Якубович В. А. Адаптивное управление динамическими объектами. — М.: Наука, 1981.
  10. Kaczmarz S. Angenäherte Auflösung von Systemen linearer Gleichungen // Bulletin International de l’Acad ́emie Polonaise des Sciences et des Lettres. 1937. Т. 35. С. 355—357.
  11. Cimmino G. Calcolo approssimato per le soluzioni dei sistemi di equazioni lineari // La Ricerca Scientifica. 1938. Т. 2. No 9. С. 326—333.
  12. Von Neumann J. Functional operators, Vol. II. The geometry of orthogonal spaces. — Princeton, NJ: Princeton University Press, 1950. — (Annals of Mathematical Studies). — Reprint of mimeographed lecture notes first distributed in 1933.
  13. Еремин И. И. Релаксационный метод решения систем неравенств с выпуклыми функциями в левых частях // Докл. АН СССР. 1965. Т. 160. No 5. С. 994— 996.
  14. Брэгман Л. М. Нахождение общей точки выпуклых множеств методом последовательного проектирования // Докл. АН СССР. 1965. Т. 162. No 3. С. 487— 490.
  15. Гурин Л. Г., Поляк Б. Т., Райк Э. В. Методы проекций для отыскания общей точки выпуклых множеств // Ж. вычисл. матем. и матем. физ. 1967. Т. 7. No 6. С. 1211—1228.
  16. Еремин И. И., Мазуров В. Д. Итерационный метод решения задачи выпуклого программирования // Докл. АН СССР. 1966. Т. 170. No 1. С. 57—60.
  17. Бердникова Е. А., Ерёмин И. И., Попов Л. Д. Распределенные фейеровские процессы для систем линейных неравенств и задач линейного программирования // Автомат. и телемех. 2004. No 2. С. 16—32.
  18. Ерёмин И. И., Попов Л. Д. Замкнутые фейеровские циклы для несовместных систем выпуклых неравенств // Изв. вузов. Матем. 2008. No 1. С. 11—19.
  19. Ерёмин И. И., Попов Л. Д. Фейеровские процессы в теории и практике: обзор последних результатов // Изв. вузов. Матем. 2009. No 1. — С. 44—65.
  20. Брэгман Л. М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для решения задач выпуклого программирования // Ж. вычисл. матем. и матем. физ. 1967. Т. 7, No 3. С. 620—631.
  21. Васин И. И., Еремин И. И. Операторы и итерационные процессы фейеровского типа: теория и приложения. — Ижевск: Регулярная и хаотическая динамика, 2005.
  22. Escalante R., Raydan M. Alternating Projection Methods. — Society for Industrial, Applied Mathematics Philadelphia, 2011.
  23. Bauschke H. H., Borwein J. M. On Projection Algorithms For Solving Convex Feasibility Problems // SIAM Review. 1996. Т. 38. No 3. С. 367—426.
  24. Lewis A. S., Malick J. Alternating Projections on Manifolds // Mathematics of Operations Research. 2008. Т. 33. No 1. С. 216—234.
  25. Nedic A., Ozdaglar A., Parrilo P. Constrained consensus and optimization in multi-agent networks // IEEE Trans. Autom. Control. 2010. Т. 55. No 4. С. 922—938.
  26. Shi G., Johansson K., Hong Y. Reaching an optimal consensus: dynamical systems that compute intersections of convex sets // IEEE Trans. Autom. Control. 2013. Т. 58. No 3. С. 610—622.
  27. Solving a system of linear equations: from centralized to distributed algorithms / P. Wang [и др.] // Ann. Rev. Control. 2019. Т. 47. С. 306—322.
  28. Проскурников А. В. Усредняющие алгоритмы и неравенства в задачах многоагентного управления и моделирования. Диссертация д.ф.-м.н. — Санкт-Петербург, 2021.
  29. Proskurnikov A., Cao M. Differential inequalities in multi-agent coordination and opinion dynamics modeling // Automatica. 2017. Т. 85. С. 202—210.
  30. Proskurnikov A., Calafiore G., Cao M. Recurrent averaging inequalities in multi-agent control and social dynamics modeling // Ann. Rev. Control. 2020. Т. 49. С. 95— 112.
  31. Балакришнан А. В. Прикладной функциональный анализ. — М.: Наука, 1980.
  32. Peterson B., Olinick M. Leontief models, Markov chains, substochastic matrices, and positive solutions of matrix equations // Mathematical Modelling. 1982. Т. 3. No 3. С. 221—239.
  33. Polyak B., Tremba A. Regularization-based solution of the PageRank problem for large matrices // Autom. Remote Control. 2012. Т. 73. No 11. С. 1877—1894.
  34. Гасников А. В., Дмитриев Д. Ю. Об эффективных рандомизированных алгоритмах поиска вектора PageRank // Ж. вычисл. матем. и матем. физ. 2015. Т. 55. No 3. С. 355—371.
  35. Sznajder R. Kaczmarz Algorithm Revisited // Technical Transactions Fundamental Sciences. 2015. No 2. С. 248—254.
  36. Deutsch F. The Angle Between Subspaces of a Hilbert Space // Approximation Theory, Wavelets and Applications / под ред. S. P. Singh. — Dordrecht: Springer, 1995. С. 107—130.
  37. A block projection method for sparse matrices / M. Arioli [и др.] // SIAM Journal on Scientific and Statistical Computing. 1938. Т. 13. С. 326—333.
  38. Agmon S. The Relaxation Method For Linear Inequalities // Canadian Journal of Mathematics. 1954. Т. 6. С. 382—392.
  39. Motzkin T. S., Schoenberg I. J. The Relaxation Method For Linear Inequalities // Canadian Journal of Mathematics. 1954. Т. 6. С. 393—404.
  40. Ерёмин И. И. Обобщение релаксационного метода Моцкина–Агмона // Успехи мат. наук. 1965. Т. 20, No 2. С. 183—187.
  41. Gurin L., Polyak B., Raik E. The method of projections for finding the common point of convex sets // USSR Comp. Math. Math. Phys. 1967. Т. 7. No 6. С. 1—24.
  42. Ерёмин И. И. О скорости сходимости в методе фейеровских приближений // Матем. заметки. 1968. Т. 4. No 1. С. 53—61.
  43. Ерёмин И. И. Фейеровские отображения и задача выпуклого программирования // Сиб. матем.журн. 1969. Т. 10. No 5. С. 1034—1047.
  44. Ерёмин И. И. Применение метода фейеровских приближений к решению задач выпуклого программирования с негладкими ограничениями // Ж. вычисл. матем. и матем. физ. 1969. Т. 9. No 5. С. 1153—1160.
  45. Брэгман Л. М. Релаксационный метод нахождения общей точки выпуклых множеств и его применение для задач оптимизации // Докл. АН СССР. 1966. Т. 171. No 5. С. 1019—1022.
  46. Lin P., Ren W. Constrained consensus in unbalanced networks with communication delays // IEEE Trans. Autom. Control. 2014. Т. 59. No 3. С. 775—781.
  47. Notarstefano G., Notarnicola I., Camisa A. Distributed Optimization for Smart Cyber-Physical Networks // Foundations and Trends in Systems and Control. 2019. Т. 7. No 3. С. 253—383.
  48. Гасников А. В. Современные численные методы оптимизации. Универсальный градиентный спуск. — М.: МФТИ, 2018.
  49. Fejér L. Über die Lage der Nullstellen von Polynomen, die aus Minimumforderungen gewisser Art entspringen // Math. Ann. 1922. No 85. С. 41—48.
  50. Fullmer D., Morse A. S. A distributed algorithm for computing a common fixed point of a finite family of paracontractions // IEEE Trans. Autom. Control. 2018. Т. 63. No 9. С. 2833—2843.
  51. Vasin V. V., Eremin I. I. Operators and Iterative Processes of Fejér Type: Theory and Applications. — De Gruyter, 2009.
  52. Rzevski G., Skobelev P. Managing complexity. — Southampton, UK: WIT Press, 2014.
  53. Wooldridge M. An Introduction To Multiagent Systems. — Chichester, England: John Wiley & Sons Ltd., 2002.
  54. Проскурников A. В., Фрадков А. Л. Задачи и методы сетевого управления // Автоматика и телемеханика. 2016. No 10. С. 3—39.
  55. Граничин О. Н. Как действительно устроены сложные информационно-управляющие системы? // Стохастическая оптимизация в информатике. 2016. Т. 12. No 1. С. 3—19.
  56. Proskurnikov A. V., Granichin O. N. Evolution of clusters in large-scale dynamics networks // Cybern. Phys. 2018. Т. 7. No 3. С. 102—129.
  57. Проблемы сетевого управления / А. Л. Фрадков [и др.]. — Ижевск: ИКИ, 2015.
  58. Marik V., Gorodetsky V., Skobelev P. Multi-agent technology for industrial applications: barriers and trends // Proc. of IEEE Int. Conf. Syst., Man, Cybern. 2020. С. 1980—1987.
  59. Агаев Р. П., Чеботарев П. Ю. Сходимость и устойчивость в задачах согласования характеристик // Управление большими системами. 2010. Т. 30.1. С. 470—505.
  60. Proskurnikov A., Tempo R. A tutorial on modeling and analysis of dynamic social networks. Part I // Ann. Rev. Control. 2017. Т. 43. С. 65—79.
  61. Proskurnikov A., Tempo R. A tutorial on modeling and analysis of dynamic social networks. Part II // Ann. Rev. Control. 2018. Т. 45. С. 166—190.
  62. Seneta E. Non-negative matrices and Markov chains. — New York: Springer-Verlag, 1981.
  63. Leizarowitz A. On infinite products of stochastic matrices // Linear Alg. Appl. 1992. Т. 168. С. 189—219.
  64. Bolouki S., Malhame R. P. Consensus algorithms and the decomposition-separation theorem // IEEE Trans. Autom. Control. 2016. Т. 61. No 9. С. 2357—2369.
  65. Touri B., Nedic A. On backward product of stochastic matrices // Automatica. 2012. Т. 48. No 8. С. 1477—1488.
  66. Chebotarev P., Agaev R. Forest matrices around the Laplacian matrix // Linear Alg. Appl. 2002. Т. 356. С. 253—274.
  67. Ren W., Beard R. Distributed consensus in multi-vehicle cooperative control: theory and applications. — London: Springer-Verlag, 2008.
  68. Ren W., Cao Y. Distributed coordination of multi-agent networks. — Springer, 2011.
  69. Shi G., Johansson K. Robust consensus for continuous-time multi-agent dynamics // SIAM J. Control Optim. 2013. Т. 51. No 5. С. 3673—3691.
  70. Proskurnikov A., Cao M. Modulus consensus in discrete-time signed networks and properties of special recurrent inequalities // Proc. of IEEE Conf. Decision and Control. 2017. С. 2003—2008.
  71. Proskurnikov A., Matveev A. Popov-type criterion for consensus in nonlinearly coupled networks // IEEE Trans. Cybernetics. 2015. Т. 45. No 8. С. 1537—1548.
  72. You K., Song S., Tempo R. A networked parallel algorithm for solving linear algebraic aquations // Proc. IEEE Conf. Decision and Control. 2016. С. 1727—1732.
  73. Mou S., Liu J., Morse A. A distributed algorithm for solving a linear algebraic equation // IEEE Trans. Autom. Control. 2015. Т. 60. No 11. С. 2863—2878.
  74. Olshevsky A., Tsitsiklis J. Convergence speed in distributed consensus and averaging // SIAM Rev. 2011. Т. 53. No 4. С. 747—772.
  75. Proskurnikov A. V., Calafiore G. C. Delay Robustness of Consensus Algorithms: Continuous-Time Theory // IEEE Trans. Autom. Control. 2023. Т. 68. No 9. С. 5301—5316.
  76. Shi G., Johansson K. Randomized optimal consensus of multi-agent systems // Automatica. 2012. Т. 48. Вып. 12. С. 3018—3030.
  77. Steinerberger S. Randomized Kaczmarz Converges Along Small Singular Vectors // SIAM Journal on Matrix Analysis and Applications. 2021. Т. 42. No 2. С. 608— 615.
  78. Sarlette A., Sepulchre R. Consensus Optimization on Manifolds // SIAM Journal on Control and Optimization. — 2009. Т. 48, No 1. С. 56—76.

Қосымша файлдар

Қосымша файлдар
Әрекет
1. JATS XML
Жүктеу
2. Fig. 1. Examples of intersections of convex sets: (a) - in the plane, (b) - in space

Жүктеу (99KB)
Метадеректер
3. Fig. 2. Projection of the point x onto the closed convex set Ω

Жүктеу (134KB)
Метадеректер
4. Fig. 3. Iterative Kaczmarz method

Жүктеу (99KB)
Метадеректер
5. Fig. 4. Cimmino method (illustration for the two-dimensional case)

Жүктеу (138KB)
Метадеректер
6. Fig. 5. Affine hyperplanes separating two sets of points in space

Жүктеу (139KB)
Метадеректер
7. Fig. 6. Projections in cyclic order (illustration for two sets)

Жүктеу (249KB)
Метадеректер

© Russian Academy of Sciences, 2024