Метод поочередных проекций для пересечения выпуклых множеств, многоагентные алгоритмы консенсуса и усредняющие неравенства

Обложка

Цитировать

Полный текст

Открытый доступ Открытый доступ
Доступ закрыт Доступ предоставлен
Доступ закрыт Только для подписчиков

Аннотация

История метода поочередных проекций для нахождения общей точки нескольких выпуклых множеств в евклидовом пространстве восходит к известному алгоритму Качмаржа для решения систем линейных уравнений, который появился в 1930-х годах и впоследствии нашел широкое применения в обработке изображений и компьютерной томографии. Важную роль в исследовании данного метода сыграли работы И.И. Ерёмина, Л.М. Брэгмана и Б.Т. Поляка, появившиеся практически одновременно и содержащие весьма общие результаты о сходимости последовательных проекций к точке на пересечении множеств, если это пересечение непусто. В настоящей статье мы рассматриваем модификацию задачи о пересечении выпуклых множеств, относящуюся к теории многоагентных систем и называемую задачей о консенсусе с ограничениями. Каждое выпуклое множество в этой задаче связано со своим агентом и, вообще говоря, недоступно другим агентам. При этом группа агентов заинтересована в нахождении общей точки этих множеств: точки, удовлетворяющей ограничениям. Распределенные аналоги метода поочередных проекций, предложенные для решения этой задачи, приводят к достаточно сложной нелинейной системе уравнений, сходимость которой, обычно, доказывается с помощью специальных функций Ляпунова. В работе дается краткий обзор данных методов и показывается их связь с теоремой о консенсусе в системе усредняющих неравенств, недавно установленной в работах первого автора и развивающей результаты о сходимости обычного метода последовательных усреднений в задаче о консенсусе.

Полный текст

Доступ закрыт

Об авторах

А. В. Проскурников

Политехнический университет Турина

Автор, ответственный за переписку.
Email: avp1982@gmail.com
Италия, Турин

И. С. Забарянская

СПбГУ

Email: akshiira@yandex.ru
Россия, Санкт-Петербург

Список литературы

  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. Фиг. 1. Примеры пересечений выпуклых множеств: (а) — на плоскости, (б) — в пространстве

Скачать (99KB)
Метаданные
3. Фиг. 2. Проекция точки x на замкнутое выпуклое множество Ω

Скачать (134KB)
Метаданные
4. Фиг. 3. Итеративный метод Качмаржа

Скачать (99KB)
Метаданные
5. Фиг. 4. Метод Чиммино (иллюстрация для двумерного случая)

Скачать (138KB)
Метаданные
6. Фиг. 5. Аффинные гиперплоскости, разделяющие два множества точек в пространстве

Скачать (139KB)
Метаданные
7. Фиг. 6. Проекции в циклическом порядке (иллюстрация для двух множеств)

Скачать (249KB)
Метаданные

© Российская академия наук, 2024