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

全文:

1. ВВЕДЕНИЕ

Ряд задач численного анализа и оптимизации сводятся к нахождению точки в пересечении семейства замкнутых выпуклых множеств в конечномерном либо гильбертовом векторном пространстве (или установлению того, что данное пересечение пусто). Одним из специальных случаев является проверка совместности системы линейных уравнений с нахождением одного из возможных решений, а также проверка совместности ограничений в линейном программировании; взрывной рост интереса к быстрым алгоритмам для решения таких задач был связан, в частности, с изобретением компьютерной томографии и связанных с ней алгоритмов быстрого восстановления изображений (см. [1]). К нахождению точки в пересечении полупространств аффинного пространства сводится вопрос о разделении двух множеств точек в пространстве, важный для задач обучения (см. [2], [3]) и математической диагностики (см. [4]–[6]). К задачам более общего вида приводит выпуклая оптимизация: на начальной стадии прямого (primal) метода оптимизации требуется найти некоторую (произвольную) точку, удовлетворяющую системе выпуклых ограничений. Наконец, в теории управления пересечения выпуклых множеств возникают в связи с оцениванием параметров и траекторий систем при неизвестных помехах (см. [7]); примером являются системы рекуррентных целевых неравенств (см. [8], [9]).

Большинство имеющихся в литературе алгоритмов для вычисления общей точки выпуклых множеств являются модификациями и обобщениями метода поочередных (alternating) проекций. В англоязычной литературе для данного метода также используется аббревиатура POCS (projection onto convex sets, т. е. проекции на выпуклые множества). История данного метода восходит к работам Качмаржа [10] и Чиммино [11] по релаксационным методам решения систем линейных уравнений, а впервые (в специальном случае двух линейных подпространств) он, по-видимому, упомянут в лекциях фон Неймана по геометрии гильбертова пространства, изданных в виде монографии [12]. Разработанная впоследствии теория метода поочередных проекций, во многом базируется на работах трех крупнейших специалистов в области оптимизации и численных методов: И. И. Ерёмина, Б. Т. Поляка и Л. М. Брэгмана, чьи пионерские работы [13]–[15] появились практически одновременно. Исследование последовательных итеративных проекций привело, с одной стороны, к развитию теории фейеровских процессов (см. [16]–[19]), а с другой стороны, послужило мотивацией для изучения D-расстояния (дивергенции) Брэгмана (см. [20]), в настоящее время играющего исключительно важную роль в задачах машинного обучения, оптимизации и вычислительной геометрии.

В настоящее время существуют достаточно подробные обзоры по задаче о пересечении выпуклых множеств и ее обобщениям (в частности, сходимости фейеровских приближений), среди которых особо следует отметить монографии [21], [22] и более раннюю работу [23], а также более специальный обзор по теории оценивания [7]. С некоторыми обобщениями задачи на невыпуклый случай (проектирование на многообразиях) можно ознакомиться в работе [24], содержащей также достаточно полный обзор литературы по данной теме. Эти обзоры, однако, не покрывают многоагентные версии задачи о пересечении выпуклых множеств, исследуемые в последние годы под различными названиями, — например задача о консенсусе с ограничениями (см. [25]) или “оптимальном консенсусе” (см. [26]). В этих задачах каждое выпуклое множество является собственностью одного из агентов и недоступно другим агентам (это может быть вызвано как требованиями приватности, так и сложностью описания самих множеств, информацию о которых по каким-то причинам может быть затруднительно передавать через сеть). Целью группы агентов, как и в исходной задаче, является нахождение точки в пересечении всех множеств, при этом обмениваться информацией каждый из агентов может лишь с некоторым набором “соседей”. Отношения соседства описываются коммуникационным графом, который может меняться и быть неполностью известен. Распределенные децентрализованные алгоритмы для решения многоагентной задачи о пересечении множеств изучались, главным образом, в журналах по теории управления и малоизвестны специалистам из других областей, а имеющиеся обзоры по теме в основном ограничиваются специальными случаями, такими как алгоритмы решения линейных уравнений (см. [27]).

Настоящая статья восполняет указанный пробел и дает краткий обзор распределенных алгоритмов, которые были предложены для решения многоагентной задачи о пересечении выпуклых множеств. Мы покажем, что

1) в данных алгоритмах (как и в централизованном случае) операторы проектирования могут быть заменены произвольными фейеровскими (парасжимающими) отображениями,

2) сходимость к консенсусу в предложенных алгоритмах может быть доказана единым способом в рамках теории усредняющих неравенств на графах. Данная теория была развита в диссертации первого автора (см. [28]), а также работах [29], [30]. Для удобства читателя, мы приводим также доказательства основных результатов, прежде не публиковавшихся на русском языке.

Оставшаяся часть статьи организована следующим образом. В разд. 2 приводятся постановка задачи о пересечении выпуклых множеств, алгоритмы поочередных проекций и их обобщения (фейеровские процессы), а также краткий обзор основных результатов о сходимости этих алгоритмов, в частности, фундаментальные результаты Ерёмина, Брэгмана и Гурина–Поляка–Райка. Основной материал статьи, относящийся к многоагентной постановке задачи, приводится в разд. 3, где мы также приводим некоторые факты о сходимости классических усредняющих алгоритмов консенсуса на переменных графах, а также ассоциированных с ними систем усредняющих неравенств. Раздел 4 завершает статью. Доказательство основных результатов о сходимости многоагентных алгоритмов приводится в приложении.

2. ЗАДАЧА О ПЕРЕСЕЧЕНИИ МНОЖЕСТВ И ЕЕ ОБОБЩЕНИЯ

В настоящей статье мы будем рассматривать задачу о пересечении выпуклых множеств в конечномерном евклидовом пространстве, однако ряд упоминаемых ниже результатов может быть распространен также на гильбертовы пространства (с некоторыми уточнениями, связанными с типом сходимости последовательных приближений). Проекционные методы изучались также на многообразиях, допускающих эффективное вычисление проекционного оператора (см. [24]); данное обобщение выходит за рамки настоящей статьи.

2.1. Постановка задачи. Оператор проектирования

Классическая задача о пересечении выпуклых множеств (или о совместности выпуклых ограничений), как правило формулируется следующим образом.

Задача А. Пусть есть набор выпуклых множеств ${\left\{{\Xi }_i\right\}}_{i\in \mathcal{V}}$ в ${ℝ}^d$, где $\mathcal{V}$ – некоторое конечное множество индексов, пересечение которых непусто:

${\Xi }_{*}\stackrel{\Delta }{=}\underset{i\in \mathcal{V}}{\cap }{\Xi }_i\ne \cancel{0}$. (1)

Требуется найти хотя бы одну точку ξ_∗ ∈ Ξ_∗.

Более сложная задача — дополнительно распознать ситуацию, когда ${\Xi }_{*}=\cancel{0}$.

Задача B. Для заданного набора выпуклых множеств ${\left\{{\Xi }_i\right\}}_{i\in \mathcal{V}}$ требуется проверить выполнение условия (1) и, если оно выполнено, найти хотя бы одну точку ξ_∗ ∈ Ξ_∗.

Отметим, что в случае одномерного пространства d = 1 задачи A и B решаются просто, поскольку единственно возможное выпуклое множество в $ℝ$-промежуток (открытый, полуоткрытый или замкнутый). Пересечение конечного семейства промежутков тривиально находится путем сортировки их левых и правых концов (фиг. 1). В этом случае мы можем определить множество Ξ_∗. В случае d = 2 множество Ξ_∗ обычно легко визуализировать с помощью компьютера, однако описать его структуру полностью или хотя бы найти одну из его точек  аналитически — достаточно трудная задача. Уже в случае трехмерного пространства d = 3 даже визуализация множества Ξ_∗ весьма затруднительна.

Фиг. 1. Примеры пересечений выпуклых множеств: (а) — на плоскости, (б) — в пространстве

Алгоритмы решения задач A и B, исходно предложенные в литературе, основывались на последовательных проекциях. Напомним фундаментальный результат о проектировании на выпуклое множество и определение проекционного оператора. Для любого замкнутого выпуклого множества $\Omega \subset {ℝ}^d$ и $x\in {ℝ}^d$ оператор проектирования $P_{\Omega }:{ℝ}^d\to \Omega$ сопоставляет точке ближайший элемент из Ω, т.е¹. $\left|x-P_{\Omega }\left(x\right)\right|={\min }_{y\in \Omega }\left|x-y\right|$. Минимум расстояния всегда достигается, а ближайшая точка единственна. Это утверждение справедливо в произвольном гильбертовом пространстве (см. [31], теорема 1.4.1).

Можно показать, что² $\measuredangle \left(y-P_{\Omega }\left(x\right),x-P_{\Omega }\left(x\right)\right)\ge \pi /2\forall y\in \Omega$ (фиг. 2)

Фиг. 2. Проекция точки x на замкнутое выпуклое множество Ω

и

$\left|x-y{|}^2\ge \right|x-P_{\Omega }\left(x\right){|}^2+|y-P_{\Omega }\left(x\right){|}^2\forall y\in \Omega$. (2)

В силу свойства (2), если y ∈ Ω (иными словами, y – неподвижная точка P_Ω), то

$\left|P_{\Omega }\left(x\right)-y\left|\le \right|x-y\right|$,

причем неравенство строгое тогда и только тогда, когда |x – P_Ω(x)| > 0, т. е. $x\cancel{\in }\Omega$. Непрерывное отображение с таким свойством называется фейеровским или (в англоязычной литературе) парасжимающим; ниже будет дано формальное определение.

2.2. Первые работы: системы линейных уравнений и неравенств

Простейшим (и первым в историческом плане) примером задачи о пересечении выпуклых множеств является решение системы линейных уравнений³

$a_i^{{\rm T}}\xi =b_i\forall i\in \mathcal{V}$,

где $\xi \in {ℝ}^d$ – неизвестный вектор, а $a_i\in {ℝ}^d, b_i\in ℝ$, определяют коэффициенты i-го уравнения. В данном случае ${\Xi }_i=\left\{\xi :a_i^{{\rm T}}\xi =b_i\right\}$ – аффинная гиперплоскость размерности d – 1, а поиск решения системы уравнений (более точно, одного из решений) может быть рассмотрен как пересечение этих выпуклых множеств. Подчеркнем, что система уравнений может быть как переопределенной ($d<\left|\mathcal{V}\right|$), так и недоопределенной ($d>\left|\mathcal{V}\right|$), уравнения могут быть линейно зависимы, а количество уравнений и переменных может быть очень велико. Такие системы уравнений, например, возникают в компьютерной томографии при восстановлении изображений по проекциям (см. [1]), леонтьевских моделях отраслевого баланса (см. [32]), вычислении вектора PageRank (см. [33], [34]) и аналогичных характеристик в задачах ранжирования и поиска, нахождении собственных векторов. Два простых проекционных алгоритма для решения линейных уравнений были практически одновременно предложены в 1930-е годы в работах Качмаржа и Чиммино.

2.2.1. Алгоритм Качмаржа. Алгоритм Качмаржа⁴ (см. [10], [35]) заключается в последовательном проектировании точки на гиперплоскости в циклическом порядке (для случая двух уравнений $\left|\mathcal{V}\right|=2$ и двух переменных d + 2 процедура проиллюстрирована на фиг. 3).

Фиг. 3. Итеративный метод Качмаржа

Нетрудно видеть, что оператор проектирования на множество $\Xi =\left\{\xi :a^{{\rm T}}\xi =b\right\}$ (где |a| ≠ 0) является аффинным отображением:

$P_{\Xi }:x\mapsto x+\frac{b-a^{{\rm T}}x}{|a{|}^2}a$. (3)

Предположим, что уравнения некоторым образом пронумерованы от 1 до n, так что $\mathcal{V}=\left\{\mathrm{1,}\dots ,n\right\}$, и выбрано некоторое произвольное приближение к решению ξ(0). На итерации с номером t = 0, 1, ... приближение ξ(t) заменяется на

$\xi \left(t+1\right)=P_{{\Xi }_i}\left(\xi \left(t\right)\right)=\xi \left(t\right)+\frac{b_i-a_i^{{\rm T}}\xi \left(t\right)}{|a_i{|}^2}{a}_i, где t+1\equiv i\mathrm{mod}n$.

В случае двух множеств данный алгоритм впервые появляется в лекциях фон Неймана (1933), изданных впоследствии в виде монографии [12], при этом рассматривались линейные замкнутые подпространства гильбертова пространства Ξ₁, Ξ₂. Фон Нейманом было доказано (см. [12], теорема 10.7), что последовательность ξ(t) сходится к проекции начальной точки ξ(0) на пространство Ξ_∗ = Ξ₁ ∩ Ξ₂ по норме. Данная сходимость экспоненциальна, а ее скорость определяется квадратом косинуса угла между подпространствами Ξ₁ и Ξ₂ (см. [36]). Указанный результат — экспоненциальная сходимость ξ(t) к проекции $P_{{\Xi }_{*}}\left(\xi \left(0\right)\right)$ – остается справедливым n > 2 и для подпространств, однако в этом случае известны лишь верхние оценки для скорости сходимости (см. [22], [23], [36]), которая, вообще говоря, не определяется только углами между всевозможными парами подпространств (Ξ_i, Ξ_j). Более подробно с историей алгоритма Качмаржа и его обобщениями, полученными в последние годы, можно ознакомиться в обзоре [35].

2.2.2. Алгоритм Чиммино. Итеративный алгоритм Чиммино, предложенный в [11], в определенном смысле является прообразом распределенных многоагентных алгоритмов, рассматриваемых в разд. 3. Его отличием от алгоритма Качмаржа является то, что на итерации ξ(t) проектируется одновременно на все гиперплоскости. Затем вычисляется центр масс полученных проекций ξ_b(t), который может быть выбран в качестве следующего приближения ξ(t + 1). Более общо, следующее приближение может быть получено как

$\xi \left(t+1\right)=\xi \left(t\right)+\alpha \left({\xi }_b\left(t\right)-\xi \left(t\right)\right)$,

где α ∈ (0, 2) – некоторый фиксированный шаг (фиг. 4).

Фиг. 4. Метод Чиммино (иллюстрация для двумерного случая)

Большим преимуществом алгоритма Чиммино является возможность параллелизации операций проектирования, которые могут выполняться несколькими процессорами. Вместе с тем, число итераций данного алгоритма, требуемое для нахождения решения с заданной точностью, может быть достаточно велико. Существуют ускоренные версии алгоритма, в частности, блочный алгоритм Чиммино (см. [37]) для разреженных систем уравнений; их рассмотрение выходит за рамки настоящей статьи.

2.2.3. Алгоритм Агмона–Мотцкина для пересечения полупространств. Важным этапом в исследовании задачи о пересечении выпуклых множеств стали вышедшие одновременно работы Агмона [38] и Мотцкина и Шёнберга [39]; идея изучаемого в них алгоритма, как упомянуто в [38], принадлежит Мотцкину. В отличие от работ Качмаржа и Чиммино, рассматривается задача о решении системы линейных неравенств, т. е. нахождении точки в пересечении полупространств

${\Xi }_i=\left\{\xi \in {ℝ}^d:a_i^{{\rm T}}\xi \le b_i\right\}$.

Проектор на полупространство $\Xi =\left\{\xi :a^{{\rm T}}\xi \le b\right\}$ нетрудно вычислить. Отметим, что он уже не является аффинным отображением:

$P_{\Xi }:x\mapsto x\text{'}\stackrel{\Delta }{=}\left(\begin{array}{ll}x+\frac{b-a^{{\rm T}}x}{|a{|}^2}a,& a^{{\rm T}}x>b,\\ x,& a^{{\rm T}}x\le b.\end{array}\right.$ (4)

Равенство $a_i^{{\rm T}}\xi =b_i$, очевидно, может быть записано как пара неравенств, таким образом, метод из [38], [39] позволяет находить решения произвольной системы линейных уравнений и неравенств (в предположении, что такое решение существует). Отметим, что к решению неравенств сводятся многие “линейные” задачи обучения (например, алгоритмы настройки весов перцептрона), классификации и математической диагностики (см. [2], [4]–[6]). В этих задачах требуется найти гиперплоскость, разделяющую две группы точек в многомерном пространстве (фиг. 5). Задавая гиперплоскость линейным уравнением, условие разделения является системой неравенств на коэффициенты этого уравнения.

Фиг. 5. Аффинные гиперплоскости, разделяющие два множества точек в пространстве

Метод из работ [38], [39] по реализации напоминает алгоритм Качмаржа (где проектор вместо (3) приобретает вид (4)), однако имеется одно существенное отличие: на каждой итерации t = 0, 1, ... проектирование осуществляется на самое дальнее множество. Формально, находится индекс⁵

$m\left(t\right)=\arg \underset{i\in \mathcal{V}}{\max }d\left(\xi \left(t\right),{\Xi }_i\right)$, (5)

где $d\left(\xi ,\Xi \right)\stackrel{\Delta }{=}\min \left\{\left|\xi -x\right|:x\in \Xi \right\}$. Проектирование осуществляется на полупространство с индексом m(t), таким образом, следующее приближение имеет вид

$\xi \left(t+1\right)=P_{{\Xi }_{m\left(t\right)}}\left(\xi \left(t\right)\right)$.

В работах [38], [39] была доказана (в предположении непустоты пересечения множеств) экспоненциальная сходимость этого алгоритма, а также его “релаксированного” варианта:

$\xi \left(t+1\right)=\left(1-\alpha \right)\xi \left(t\right)+\alpha P_{{\Xi }_{m\left(t\right)}}\left(\xi \left(t\right)\right), \alpha \in \left(\mathrm{0,2}\right)$. (6)

Отметим, что скорость сходимости может быть определена явно (см. [38]) и зависит от матрицы A, хотя ее вычисление нетрививально. По сложности итерация алгоритма Агмона–Мотцкина эквивалентна итерации алгоритма Чиммино, поскольку требуется вычислить расстояния до всех полупространств, прежде чем выполнить проектирование.

2.3. Метод попеременных проекций для произвольных множеств

Методы попеременных проекций для отыскания общей точки произвольных замкнутых выпуклых множеств чаще всего используют идею алгоритмов Качмаржа (поочередные проекции на множества в циклическом порядке, см. фиг. 6) и Агмона–Мотцкина (в этом случае на каждом шаге выбирается самое дальнее множество).

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

Поскольку исследованию данного класса методов посвящена обширная литература, в частности, обзоры [22], [23], перечислим лишь основные работы, положившие начало целому ряду исследований по выпуклой оптимизации с ограничениями.

Исторически первой была статья И. И. Ерёмина [40] (написанная и представленная в редакцию в 1962 г.), в которой рассматривался метод Агмона–Мотцкина (5), (6) для произвольных замкнутых выпуклых множеств Ξ_i. Было показано, что если пересечение множеств непусто, то метод сходится, и наоборот, если последовательность ξ(t) имеет предел, то ее предел автоматически принадлежит пересечению всех множеств Ξ_∗.

В работе Л. М. Брэгмана [14] исследовался вопрос сходимости алгоритмов при последовательном проектировании в циклическом порядке (как в алгоритме Качмаржа) и при проекции на самое дальнее выпуклое множество, как в алгоритме Агмона–Мотцкина. Сходимость исследовалась в гильбертовом пространстве, однако понималась лишь в слабом смысле (в случае конечномерного пространства она эквивалентна сходимости по норме) и была доказана в предположении, что множества имеют непустое пересечение. Более того, была исследована сходимость модифицированного алгоритма Агмона–Мотцкина в случае полупространств ${\Xi }_i=\left\{\xi :a_i^{{\rm T}}\xi \le b_i\right\}$. В этом модифицированном методе проекция осуществляется не на самое дальнее полупространство Ξ_i, а на множество, для которого ограничение $a_i^{{\rm T}}\xi \le b_i$ на шаге t “наиболее нарушено”, иными словами, (5) нужно заменить условием

$m\left(t\right)=\arg \underset{i\in \mathcal{V}}{\max }\left[a_i^{{\rm T}}\xi \left(t\right)-b_i\right]$,

в то время как правило проектирования (6) остается без изменения.

Дальнейшее обобщение результатов Ерёмина и Брэгмана было получено в работе Л. Г. Гурина⁶, Б. Т. Поляка и Э. В. Райка [15]. Как и в работе [14], исследовались два типа алгоритма попеременных проекций (в циклическом порядке и на самое дальнее множество) для замкнутых выпуклых множеств в произвольном гильбертовом пространстве. Были получены условия экспоненциальной (в норме гильбертова пространства) сходимости обоих алгоритмов в случае, если каждое из множеств Ξ_i имеет непустое пересечение с внутренностями остальных множеств:

${\Xi }_i\cap \underset{j\ne i}{}{\dot{\Xi }}_j\ne \cancel{0}\forall i\in \mathcal{V}$.

Последнее условие можно снять, если Ξ_i являются полупространствами (таким образом, результат [38] был обобщен на бесконечномерный случай). Приведено также некоторое условие сходимости по норме (“равномерная выпуклость” множеств Ξ_i). Во всех указанных результатах точный оператор проектирования можно заменить его “релаксированной” версией, как в алгоритме (6) (более того, шаг может на каждой итерации алгоритма быть разным). Показано, что алгоритм циклических проекций при пустом пересечении множеств Ξ_i экспоненциально быстро сходится к периодической траектории. Был предложен также ускоренный вариант метода Агмона–Мотцкина (проекция на самое дальнее множество). В статье [15] приводится ряд интересных приложений метода последовательных проекций, в частности, к задаче аппроксимации функции полиномами на отрезке и специальной задаче оптимального управления.

2.3.1. Дальнейшее развитие: фейеровские операторы и оптимизация. Отметим, что алгоритмы для вычисления общей точки выпуклых множеств, рассматривавшиеся до сих пор, основаны на неявном предположении, что оператор проектирования на каждое из множеств может быть эффективно вычислен. Если в случае линейных гиперплоскостей и полупространств он допускает просто аналитическое представление, то в случае более сложных множеств (например, заданных некоторым нелинейным выпуклым неравенством f(ξ) ≤ 0) вычисление проекции возможно только численно и, вообще говоря, сводится к решению задачи выпуклой оптимизации. Вместе с тем, уже в первых работах (см. [10], [13], [38], [39]) было замечено, что оператор проекции может быть заменен “релаксированной” проекцией (6), и, более того, основное свойство, используемое в доказательстве — то, что он обладает некоторым слабым свойством сжатия и приближает любую точку за пределами выбранного множества Ξ к этому множеству. Данное наблюдение привело к развитию теории фейеровских процессов, основы которой были заложены Ерёминым в пионерских работах [13], [16], [42]–[44]. Наиболее полное изложение данной теории доступно в монографии [21]. Как будет показано в разд. 3, есть возможность обобщить результаты о сходимости итеративных процедур с фейеровскими операторами на многоагентный случай (см. теорему 1). В следующем пункте мы подробнее рассмотрим фейеровские отображения и приведем некоторые примеры.

Помимо того, часто интерес представляет нахождение не произвольной точки в пересечении выпуклых множеств, а точки, доставляющей оптимум некоторому функционалу (возможно, негладкому). Возможность решения задач линейного программирования с помощью метода последовательных проектирований была замечена Брэгманом (см. [14]), в последующих работах которого (см. [20], [45]) были рассмотрены итерационные методы “проектирования” в смысле некоторой “псевдометрики” на линейном пространстве, которая была названа D-расстоянием. Наиболее часто используемый тип D-расстояний называется дивергенцией Брэгмана и задается формулой

$D_{\phi }\left(x,y\right)=\phi \left(x\right)-\phi \left(y\right)-\nabla \phi \left(y\right)\left(x-y\right)$

для некоторой выпуклой дифференцируемой функции φ. Брэгманом было показано (см. [20]), что методы проекции в смысле подходящим образом построенного D-расстояния позволяют решать задачи выпуклого программирования с ограничениями в виде равенств и неравенств. Альтернативный подход, предложенный Ерёминым (см. [43]), приводит к изучению фейеровских отображений со сдвигом. Отметим, что в многоагентном случае алгоритмы оптимизации такого рода малоизучены, как правило, используются альтернативные алгоритмы, полученные децентрализацией методов проекции градиента (см. [25], [46], [47]); зачастую ограничения также заменяются барьерными функциями. Изучение алгоритмов оптимизации с ограничениями выходит за рамки настоящей статьи, достаточно полное изложение современных методов доступно, например, в монографии [48].

2.4. Фейеровские (парасжимающие) отображения

Всюду в данном пункте мы предполагаем заданными некоторый оператор $P:{ℝ}^d\to {ℝ}^d$ (вообще говоря, нелинейный) и некоторую норму ||·|| на ${ℝ}^d$ (не обязательно евклидову). Напомним, что на конечномерном пространстве все нормы эквивалентны и порождают одну и ту же топологию, соответственно понятия открытости, замкнутости и непрерывности в различных нормах также эквивалентны.

Определение 1. Оператор P называется фейеровским⁷ относительно множества $M\subset {ℝ}^d$, или M-фейеровским, если выполнены три условия: [(a)]

1. P – непрерывное отображение на всем пространстве;
2. множество M неподвижно относительно P;
3. оператор удовлетворяет условию сжатия относительно M, т. е.

$\parallel P\left(\xi \right)-{\xi }_0\parallel =\parallel P\left(\xi \right)-P\left({\xi }_0\right)\parallel <\parallel \xi -{\xi }_0\parallel \forall \xi \cancel{\in }M, {\xi }_0\in M$. (7)

Очевидно, что из (7) следует, что P обладает свойством

$\parallel P\left(\xi \right)-P\left({\xi }_0\right)\parallel \le \parallel \xi -{\xi }_0\parallel \forall \xi \in {ℝ}^d, {\xi }_0\in M$. (8)

В англоязычной литературе фейеровские операторы называются часто парасжимающими (paracontracting) (см. [50]), встречаются также и иные термины, например, “притягивающий” (attracting) к множеству M оператор (см. [23]). Очевидно, что если $\parallel x-y\parallel <\parallel P\left(x\right)-y\parallel$, то x ≠ P(x); таким образом, M в определении 1 совпадает со множеством всех неподвижных точек M-фейеровского оператора $\mathcal{F}\left(P\right)\stackrel{∆}{=}\left\{\zeta :P\left(\zeta \right)=\zeta \right\}$; поэтому, если не требуется явное уточнение данного множества, мы для краткости будем просто называть оператор фейеровским. Легко видеть также, что множество M автоматически является замкнутым и выпуклым. Первое свойство вытекает из непрерывности оператора P: если последовательность {x_n} элементов M сходится к некоторому пределу $x\in {ℝ}^d$, то, очевидно, для произвольного элемента a ∈ M имеем $\parallel x-a\parallel ={\lim }_{n\to \infty }\parallel x_n-a\parallel ={\lim }_{n\to \infty }\parallel P\left(x_n\right)-a\parallel =\parallel P\left(x\right)-a\parallel$, что возможно лишь в случае, когда x ∈ M. Второе свойство также легко доказать: если z-произвольный элемент отрезка, соединяющего точки x, y ∈ M, то $\parallel x-y\parallel =\parallel x-z\parallel +\parallel z-y\parallel \ge \parallel x-P\left(z\right)\parallel +\parallel P\left(z\right)-y\parallel \ge \parallel x-y\parallel$. Данное неравенство может быть выполнено только в случае, когда z ∈ M (в противном случае, $\parallel x-P\left(z\right)\parallel <\parallel x-z\parallel$ и $\parallel y-P\left(z\right)\parallel <\parallel y-z\parallel$). Следовательно, вместе с двумя точками M содержит и отрезок, их соединяющий.

Фейеровское отображение является естественными обобщением сжимающего (по Банаху) отображения P, для которого $\left|P\left(x\right)-P\left(y\right)\right|\le q\left|x-y\right|\forall x,y\in {ℝ}^d$ при некоторой постоянной q ∈ (0, 1). Принципиальным отличием сжимающих и фейеровских отображений является то, что у сжимающих отображений, в силу известной теоремы Банаха, существует ровно одна неподвижная точка, а множество неподвижных точек фейеровского отображения может быть любым замкнутым выпуклым множеством. В следующем пункте приводятся примеры фейеровских операторов.

2.4.1. Примеры фейеровских операторов

Пример 1. Как мы видели, проектор P_Ω на замкнутое выпуклое множество является фейеровским (в стандартной евклидовой норме). Более общо, можно показать, что при любом коэффициенте a ∈ (0, 2) оператор (1 − a)Id + aP_Ω, где Id – тождественное отображение, также является фейеровским в евклидовой норме (см., например, лемму 2 в [40] и следствие 2.5 в [23]).

Пример 2. Выпуклая комбинация нескольких фейеровских отображений является фейеровским отображением. Пусть P₁, ..., P_n – фейеровские операторы с множествами неподвижных точек M₁, ..., M_n, и a₁, ..., a_n > 0 – коэффициенты такие, что ${\sum }_{i=1}^n{a}_i=1$. Тогда легко проверить, что оператор $P={\sum }_i{a}_i{P}_i$ является фейеровским относительно $M=M_1\cap \cdots \cap M_n$ (в предположении, что оно непусто). Объединяя данный пример с примером 1, можно показать, что в алгоритме Чиммино, описанном в п. 2.1, приближение ξ(t + 1) получается из путем ξ(t) применения фейеровского оператора.

Пример 3. Аналогично, легко проверить, что композиция фейеровских операторов $P_n\circ \cdots \circ P_1$ также является фейеровским относительно пересечения множеств неподвижных точек $M=M_1\cap \cdots \cap M_n$ (в предположении, что оно непусто). Таким образом, последовательные n операций (где n – число множеств) в алгоритме Качмаржа эквивалентны применению фейеровского оператора.

Пример 4. Пусть P в некоторой строго выпуклой норме⁸ ||·|| является нерасширяющим ($\parallel P\left(x\right)-P\left(y\right)\parallel \le 1$ при всех $x,y\in {ℝ}^d$) с непустым множеством неподвижных точек $M=\mathcal{F}\left(P\right)$. Тогда при a ∈ (0, 1) оператор (1 − a)Id + aP также является нерасширяющим, а также M-фейеровским. Первое свойство проверяется непосредственно, кроме того, если y ∈ M и $x\cancel{\in }M$, то $P\left(x\right)-y\ne x-y$, следовательно, либо $\parallel P\left(x\right)-y\parallel <\parallel x-y\parallel$, либо векторы P(x) – y и x – y неколлинеарны, либо $P\left(x\right)-y=y-x$. Во всех случаях

$\parallel \left(1-a\right)x+aP\left(x\right)-y\parallel =\parallel \left(1-a\right)\left(x-y\right)+a\left(P\left(x\right)-y\right)\parallel <\parallel x-y\parallel$.

В силу сделанного выше замечания получаем, в частности, известный факт: множество неподвижных точек нерасширяющего (относительно строго выпуклой нормы) отображения всегда является выпуклым (см. [23]).

Примеры 2—4 интересны тем, что явное вычисление проекции на множество может быть затруднительно, тем не менее, может быть известен фейеровский оператор, приближающий точку не из к этому множеству. На самом деле, таких примеров достаточно много. Следующий пример относится к распространенному случаю, когда выпуклое множество задается некоторым скалярным выпуклым неравенством.

Пример 5. Рассмотрим непрерывно дифференцируемую выпуклую функцию $f:{ℝ}^d\to ℝ$ и предположим, что множество $M_f\stackrel{∆}{=}\left\{x:f\left(x\right)\le 0\right\}$ непусто (очевидно, это множество выпукло и замкнуто). Выбрав постоянную a ∈ (0, 2), рассмотрим отображение

$P_{\alpha ,f}:x\mapsto x^{\text{'}}\stackrel{\Delta }{=}\left(\begin{array}{ll}x-\alpha f\left(x\right)\frac{\nabla f\left(x\right)}{|\nabla f\left(x\right){|}^2},& f\left(x\right)>\mathrm{0,}\\ x,& f\left(x\right)\le 0.\end{array}\right.$

Отметим, что градиент ∇f, в силу выпуклости, может обращаться в нуль лишь в точках (глобального) минимума f, а все точки минимума (если они существуют) должны принадлежать M_f. В силу этого, выражение P_α,f(x) корректно определено при f(x) > 0. Нетрудно также показать, что P_α,f – непрерывное (но, вообще говоря, недифференцируемое) отображение с множеством неподвижных точек M_f. Важное наблюдение, сделанное в [13], cостоит в том, что оператор P_α,f является фейеровским относительно евклидовой нормы. Конструкция тривиально распространяется на недифференцируемые выпуклые отображения, для которых можно выбрать непрерывную ветвь субдифференциала. Более точно, если существует непрерывное отображение $g:{ℝ}^d\to {ℝ}^d$ такое, что $g\left(x\right)\in \partial f\left(x\right)$ при всех x, то в определении P_α,f градиент ∇f(x) можно заменить на g(x) (см. [13]).

Другими примерами фейеровских отображений являются проксимальные операторы и операторы градиентного спуска, соответствующие строго выпуклым функциям (см. [50]).

2.4.2. Итерации фейеровских операторов. Следующая простая лемма показывает, что итерации фейеровского оператора так же, как и сжимающего (в смысле Банаха) отображения, сходятся к неподвижной точке.

Лемма 1. Пусть оператор $P:{ℝ}^d\to {ℝ}^d$ является фейеровским с непустым множеством неподвижных точек $M=\mathcal{F}\left(P\right)$. Тогда последовательность ${\left(\xi \left(t\right)\right)}_{t=0}^{\infty }$, задаваемая рекуррентным соотношением

$\xi \left(t+1\right)=P\left(\xi \left(t\right)\right), t=\mathrm{0,} \mathrm{1,} \dots$,

при любой начальной точке ξ(0) сходится к некоторому элементу множества M.

Доказательство леммы 1 будет дано в приложении. В силу примеров 2 и 3, из леммы 1 нетрудно вывести сходимость алгоритма Качмаржа и алгоритма Чиммино (для проекторов на произвольные множества не обязательно линейной структуры). Понятие фейеровского оператора и лемму 1 можно обобщить и на многозначные отображения (возникающие, например, в алгоритме Агмона–Мотцкина, если разрешить индексу в (5) принимать несколько значений). Наиболее общие результаты о сходимости и расходимости фейеровских процессов могут быть найдены в [17], [21], [23], [51].

3. МНОГОАГЕНТНЫЕ АЛГОРИТМЫ ДЛЯ ПЕРЕСЕЧЕНИЯ МНОЖЕСТВ

Обратимся теперь к многоагентной⁹ постановке задачи о пересечении выпуклых множеств. В этой задаче каждое замкнутое выпуклое множество ${\Xi }_i\subseteq {ℝ}^d$ связано со своим агентом (это может быть программный модуль, робот или живое существо, обладающее некоторой автономностью в принятии решений). Часто это множество трактуется как ограничение, выдвигаемое агентом i. Мы считаем, что агент i располагает достаточной информацией о своем множестве ${\Xi }_i\subseteq {ℝ}^d$, в частности, может вычислять проекцию $P_{{\Xi }_i}\left(\xi \right)$ произвольной точки на множество Ξ_i либо, более общо, значение какого-либо иного фейеровского оператора P_i(ξ) с множеством неподвижных точек Ξ_i. При этом агенту недоступна информация о множествах других агентов Ξ_j, j ≠ i. Это может быть связано как со сложной структурой множеств, информацию о которых затруднительно передать через сеть, так и с требованиями приватности (множества могут зависеть от некоторой конфиденциальной информации). Целью агентов является найти некоторую точку ${\xi }_{*}\in {\Xi }_{*}\stackrel{∆}{=}{\cap }_{i\in \mathcal{V}}{\Xi }_i$, которая удовлетворяет всем ограничениям.

В предположении неограниченной коммуникации между агентами общая точка может, теоретически, быть найдена с помощью обычного метода попеременных проекций (обобщенного алгоритма Качмаржа). Для этого требуется некоторым образом занумеровать агентов и обеспечить после каждой операции проектирования передачу полученного приближения к точке ξ(t) следующему (в циклическом порядке) агенту. Агент 1 выполняет проектирование начальной точки ξ(0) на множество Ξ₁ либо, более общо, вычисление некоторого фейеровского оператора P₁(ξ(0)) и передает результат агенту 2, применяющему оператор P₂ и так далее, агент n применяет оператор P_n и передает результат агенту 1. Такая процедура, однако, неудовлетворительна по ряду причин. Во-первых, будучи формально независимыми, агенты лишены возможности выполнять операции параллельно: каждый из них простаивает n – 1 из последовательных n итераций. Во-вторых, с точки зрения парадигмы многоагентных систем, агенты в общем случае должны быть равнозначны и не иметь каких-либо отличительных признаков в виде уникального индекса, соответственно, для получения некоторого упорядочения от 1 до n агентам требуется осуществить специальную процедуру. Наконец, как уже было сказано, на шаге с номером t должна быть возможность коммуникации между агентами с номерами 1 + (t mod n) и 1 + (t + 1mod n). На практике это гарантировано не всегда: коммуникационный граф может быть неполным, меняться с течением времени и быть заранее неизвестным (например, ряд коммуникационных линий может отключаться вследствие отказов или необходимости передать более важную информацию).

Более удобны с точки зрения многоагентной реализации обобщенные методы Чиммино (проектирование на все множества и вычисление барицентра) и Агмона–Мотцкина (нахождение самого дальнего множества), однако они предполагают, что агенты могут обмениваться информацией с некоторым центральным узлом, который собирает у них значения P₁(ξ(t)), а затем вычисляет их барицентр (либо самую дальнюю проекцию) для нахождения ξ(t + 1). Наличие такого центрального узла в сети также не всегда возможно, кроме того, сложность такой централизованной системы растет с ростом числа агентов.

В силу сказанного, для решения задачи о пересечении множеств, принадлежащих агентам, были предложены альтернативные алгоритмы, которые близки по идее алгоритму Чиммино, однако основываются на идее консенсуса, достигаемого путем последовательных усреднений (короткое введение в консенсусные алгоритмы дано в следующем пункте). В отличие от обычных проекционных алгоритмов, каждый агент i имеет свое собственное состояние ${\xi }^i\left(t\right)\in {ℝ}^d$, которое на каждом шаге становится доступным соседним (в смысле коммуникационного графа) агентам, обновляется в зависимости от состояний соседей и в конечном итоге сходится к точке из пересечения множеств, при этом данное установившееся состояние одинаково для всех агентов.

Оставшаяся часть данного раздела организована следующим образом. В п. 3.1 приведено краткое изложение консенсусных алгоритмов и условие достижения консенсуса в сети агентов с переменным направленным графом. Нам данный результат понадобится в несколько более сильном виде (робастность консенсуса к исчезающе малым возмущениям). Другой важный результат — лемма о консенсусе, гарантируемом усредняющими неравенствами, которому посвящен п. 3.2. В п. 3.3 мы приводим несколько классов алгоритмов, предложенных в литературе для решения многоагентной задачи о пересечении множеств и формулируем основной результат статьи, который будет доказан в приложении.

3.1. Классические алгоритмы консенсуса. Сведения из теории графов

Алгоритмы усреднения имеют длинную историю, восходящую, с одной стороны, к динамике марковских процессов (см. [59]), а с другой стороны, к агентным (микроскопическим) моделям динамики мнений (см. [60], [61]). В данном пункте мы ограничимся лишь кратким описанием линейных алгоритмов усреднения и приведем основное (на сегодняшний день) условие достижения консенсуса.

3.1.1. Динамика последовательного усреднения. Консенсус. Рассмотрим множество агентов $\mathcal{V}$, каждый из которых описывается скалярной переменной x_i(t), $i\in \mathcal{V}$, называемой состоянием и меняющейся в дискретном времени t = 0, 1, .... На каждом шаге каждый из агентов вычисляет взвешенное среднее своего собственного состояния и состояний других агентов. Агенту, однако, доступна информация не обо всех состояниях, а лишь об агентах из некоторого множества ${\mathcal{V}}_i\left(t\right)\subseteq \mathcal{V}$, которое мы будем называть множеством соседей агента i в момент t. Мы всегда считаем, что $i\in {\mathcal{V}}_i\left(t\right)$. В каждый момент времени $t\in \mathbb{N}$, агент  i присваивает веса усреднения a_ij(t) всем соседям. Веса каждого агента удовлетворяют ограничениям

$a_{ij}\left(t\right)\ge 0 \forall j\in {\mathcal{V}}_i\left(t\right), \sum _{j\in {\mathcal{V}}_i\left(t\right)}{a}_{ij}\left(t\right)=1$. (9)

Затем, агент обновляет свое значение следующим образом:

$x_i\left(t+1\right)=\sum _{j\in {\mathcal{V}}_i\left(t\right)}{a}_{ij}\left(t\right)x_j\left(t\right), t=\mathrm{0,} \mathrm{1,} \dots$, (10)

Доопределяя $a_{ij}\left(t\right)\stackrel{∆}{=}0$ при $j\cancel{\in }{\mathcal{V}}_i\left(t\right)$, мы получаем стохастическую матрицу усредняющих весов $A\left(t\right)={\left(a_{ij}\right)}_{i,j\in \mathcal{V}}$. Удобно переписать (10) в компактной матричной форме:

$x\left(t+1\right)=A\left(t\right)x\left(t\right), t=\mathrm{0,1,}\dots$, (11)

где x(t) обозначает вектор-столбец, составленный из состояний агентов x_i(t).

В случае постоянной матрицы A поведение системы (11), очевидно, определяется структурой матрицы A^t, хорошо изученной в теории марковских цепей. В приложениях, однако, принципиально важно иметь возможность работать с переменной матрицей, поскольку каналы коммуникации между агентами могут открываться и закрываться, что приводит к изменению отношений соседства (множеств ${\mathcal{V}}_i$) и, как следствие, необходимости перераспределять веса. Поведение систем с переменной матрицей, или бесконечными матричными произведениями, в общем случае остается мало изученным. Основные результаты можно найти в монографии [62] и обзоре [59], а также недавних работах [63]–[65]. Мы приведем ниже лишь один результат, который будет использован в дальнейшем.

Поскольку на каждом шаге агент приближает свое состояние к состояниям соседей, то можно ожидать, что в итоге все состояния окажутся одинаковы, иными словами, будет достигнут консенсус:

${\overline{x}}_1=...={\overline{x}}_n, где {\overline{x}}_i\stackrel{∆}{=} \underset{t\to \infty }{\lim }{x}_i\left(t\right) \forall i\in \mathcal{V}$. (12)

Иногда консенсус определяется в формально более слабом смысле, например, как асимптотическая синхронизация значений агентов:

$\underset{t\to \infty }{\lim }\underset{i,j\in \mathcal{V}}{\max }\left|x_j\left(t\right)-x_i\left(t\right)\right|=0$. (13)

Отметим, что в нашем случае для алгоритма (11) последнее требование эквивалентно “сильному” консенсусу. Этот факт известен из литературы по теории цепей Маркова (см. [62], теорема 4.17) (синхронизацией в этом случае является слабая эргодичность обратного матричного произведения, что эквивалентно сильной эргодичности, влекущей за собой консенсус). Связано это с тем, что максимальный (соответственно, минимальный) элемент вектора x(t) в силу уравнений (10) не возрастает (соответственно, не убывает) с ростом t, сходясь к конечному пределу. Поэтому нетрудно видеть, что

$\underset{t\to \infty }{\lim }\underset{i,j\in \mathcal{V}}{\max }\left|x_j\left(t\right)-x_i\left(t\right)\right|=\underset{t\to \infty }{\lim }\underset{i}{\max }{x}_i\left(t\right)-\underset{t\to \infty }{\lim }\underset{i}{\min }{x}_i\left(t\right)$,

а следовательно, (13) эквивалентно тому, что ${\lim }_{t\to \infty }{\max }_i{x}_i\left(t\right)={\lim }_{t\to \infty }{\min }_i{x}_i\left(t\right)$, т. е. все элементы x(t) сходятся к одному и тому же конечному значению.

Всюду далее мы называем (10) (или (11)) алгоритмом итеративного усреднения, заданного последовательностью стохастических матриц A(t). Подчеркнем, что хотя матрицы A(t) “скрывают” в себе структуру исходных множеств ${\mathcal{V}}_i\left(t\right)$ (отношений “соседства”), в действительности именно эти множества являются первичными, поскольку они определяют информационную структуру многоагентного алгоритма (кто и кому пересылает свое состояние), в то время как веса усреднения играют существенно меньшую роль в рассматриваемой ниже задаче консенсуса, хотя и не могут быть выбраны полностью произвольно. Вместо матрицы часто говорят о (нагруженном) графе влияний между агентами. В следующем пункте мы приводим определения из теории графов.

3.1.2. Графы влияния и связанные понятия

Определение 2. Граф (формально, направленный или ориентированный граф) $\mathcal{G}=\left(\mathcal{V},\mathcal{E}\right)$ – это пара двух конечных множеств $\mathcal{V}$ (могут быть произвольными) и $\mathcal{E}\subseteq \mathcal{V}\times \mathcal{V}$. Элементы $\mathcal{V}$ называются вершинами графа, а элементы $\mathcal{E}$ – ребрами. Обычно предполагается, что вершины индексируются от 1 до n, так что $\mathcal{V}=\left[1:n\right]$. Ребро (i, j) соединяет вершину i с вершиной j (и также обозначается как i → j). Во всех графах, рассматриваемых ниже, в каждой вершине имеется петля, т. е. ребро (i, i).

Следующие два понятия относятся к типам связности (направленных) графов.

Определение 3. Последовательность ребер $v_0\to v_1\to v_2\to \cdots \to v_s$ называется маршрутом, соединяющим вершину v₀ с вершиной v_s, а число ребер s в маршруте называется его длиной. Граф называется сильно связным, если каждые две разных вершины соединены маршрутом. Граф называется квазисильно связным, если существуют маршруты из некоторой вершины (называемой корнем) во все остальные вершины.

Отметим, что квазисильно связный граф имеет исходящее остовное дерево (spanning tree) (см. [66]), и наоборот, наличие такового в графе влечет квазисильную связность. Поэтому часто в критериях консенсуса квазисильная связность формулируется как существование остовного дерева в графе (см. [67], [68]).

Следуя традиции теории многоагентных систем, мы будем рассматривать графы, вершины которых ассоциируются с агентами, а ребро j → i ассоциируется с влиянием агента j на агента i в заданный момент времени. Применительно к алгоритму (10), влияние означает, что состояние агента участвует в формировании следующего состояния агента i, т. е. a_ij(t) ≠ 0. Соответственно, вес a_ij(t) можно трактовать как силу влияния или вес соответствующего ребра в графе. Это мотивирует следующее определение.

Определение 4. Для заданной квадратной матрицы $A={\left(a_{ij}\right)}_{i,j\in \mathcal{V}}$ определим ассоциированный граф $\left(\mathcal{V},\mathcal{E}\left[A\right]\right)$, вершины которого находятся в взаимно однозначном соответствии с индексным множеством $\mathcal{V}$ и $\mathcal{E}\left[A\right]=\left(j,i\right):a_{ij}\ne 0$. Тройка $\mathcal{G}\left[A\right]\triangleq \left(\mathcal{V},\mathcal{E}\left[A\right],A\right)$ в дальнейшем называется нагруженным графом, определяемым матрицей A.

3.1.3. Предположения о весах влияния. Несмотря на то, что выбор матрицы весов, на самом деле, имеет существенно меньшую роль, чем структура графа влияния, консенсус не может быть достигнут при произвольном выборе весов. Например, циклический алгоритм

$x_1\left(t+1\right)=x_2\left(t\right), x_2\left(t+1\right)=x_3\left(t\right), \dots , x_n\left(t+1\right)=x_1\left(t\right)$

не только не приводит к консенсусу, но и вообще не сходится в случае попарно различных начальных состояний x_i(0), поскольку вектор x(t + 1) просто получается из x(t) циклической перестановкой. Для исключения подобного поведения требуются некоторые условия, аналогичные апериодичности марковских цепей. Наиболее распространенное условие, накладываемое на матрицы в большинстве работ — это свойство равномерной положительности диагональных элементов стохастической матрицы:

$a_{ii}\left(t\right)\ge \eta >0\forall i\in \mathcal{V} \forall t$. (14)

Помимо этого ясно, что для достижения консенсуса связь между агентами не должна полностью прерываться, более того, веса влияния не могут становиться слишком малыми с течением времени. Это легко проиллюстрировать на примере двух агентов и матрицы $a_{11}\left(t\right)=a_{22}\left(t\right)=1-a\left(t\right)$, $a_{12}\left(t\right)=a_{21}\left(t\right)=a\left(t\right)$. Нетрудно проверить, что

$x_1\left(t+1\right)-x_2\left(t+1\right)=\left(1-2a\left(t\right)\right)\left(x_1\left(t\right)-x_2\left(t\right)\right)=\cdots =\left(x_1\left(0\right)-x_2\left(0\right)\right)\prod _{s=0}^t\left(1-2a\left(s\right)\right)$.

Если |a(t)| = 1/2 при всех t и ${\sum }_{t\ge 0}a\left(t\right)<\infty$, то произведение в правой части сходится к ненулевому значению, соответственно, консенсус не достигается.

В связи с этим обычно вводятся некоторые требования “усиленной” связности графа влияний, которая должна сохраняться при отбрасывании слишком слабых связей между агентами. Мы будем рассматривать лишь наиболее распространенное свойство равномерной (или повторяющейся) связности.

Определение 5. Если дана неотрицательная матрица $A\in {ℝ}^{\mathcal{V}\times \mathcal{V}}$, то ее ε-скелет — это матрица A^ε, полученная обнулением всех элементов, которые меньше ε, т. е.

$a_{ij}^{\epsilon }\triangleq \left(\begin{array}{l}{a}_{ij}, a_{ij}\ge \epsilon ,\\ 0 в противном случае.\end{array}\right.$

Нагруженный граф $\mathcal{G}\left[A^{\epsilon }\right]$ называется ε-скелетом нагруженного графа $\mathcal{G}\left[A\right]$. Мы говорим, что нагруженный граф (квази)сильно ε-связен, если его ε-скелет является (квази)сильно связным¹⁰.

Определение 6. Имея последовательность матриц $A\left(t\right)\in {ℝ}^{\mathcal{V}\times \mathcal{V}}$, где t ∈ [t₀ : t₁], мы определяем объединение соответствующих графов над [t₀ : t₁] как граф

$\underset{t=t_0}{\overset{t_1}{\cup }}\mathcal{G}\left[A\left(t\right)\right]\triangleq \mathcal{G}\left[\underset{t=t_0}{\overset{t_1}{}}A\left(t\right)\right]$.

Графы $\mathcal{G}\left[A\left(t\right)\right], t\in \mathcal{T}$, где $\mathcal{T}=\left[t_0:t_1\right]$, называются совместно (квази)сильно ε-связными на интервале $\mathcal{T}$, если их объединение на $\mathcal{T}$ является (квази)сильно ε-связным.

Определение 7. Меняющийся во времени граф G[A(·)] является равномерно (квази)сильно связным, если существуют такие константы ε > 0 и T > 0, что графы $\mathcal{G}\left[A\left(t\right)\right]$ совместно (квази)сильно ε-связны в каждый момент времени [t₀ : t₀ + T], t₀ ≥ 0.

Отметим, что часто предполагается дополнительное ограничение на веса усреднения, которое на практике обычно выполняется. Именно, считается, что ненулевые элементы матрицы весов не могут быть слишком малы:

$a_{ij}\left(t\right)\in \left\{0\right\}\cup \left[\epsilon ,1\right]\forall t=\mathrm{0,} \mathrm{1,} \dots$. (15)

При этом понятие равномерной связности просто означает, что объединение графов за достаточно длинный период T является связным (в сильном или квазисильном смысле).

3.1.4. Достаточное условие робастного консенсуса. При изучении многоагентных алгоритмов пересечения множеств мы будем использовать следующее условие консенсуса, которое на самом деле гарантирует робастность консенсуса к исчезающим на бесконечности возмущениям. Наряду с (11), рассмотрим возмущенную систему

$x\left(t+1\right)=A\left(t\right)x\left(t\right)+f\left(t\right), t=\mathrm{0,} \mathrm{1,} \dots$. (16)

Справедлива следующая

Лемма 2. Пусть A(t) – стохастические матрицы с равномерно положительными диагональными элементами (14). Тогда алгоритм (11) устанавливает консенсус (12), если переменный граф $\mathcal{G}\left[A\left(\cdot \right)\right]$ обладает равномерной квазисильной связностью. Более того, если возмущение f(·) исчезает на бесконечности $f\left(t\right)\underset{t\to \infty }{\to }0$, то

$\max x\left(t\right)-\min x\left(t\right)\underset{t\to \infty }{\to }0$ (17)

для любого решения (16).

Лемма 2 обычно доказывается при дополнительном предположении (15), в таком виде она доступна в [46]. Как показано в диссертации [28], это условие можно снять, однако доказательство становится существенно более сложным. Можно также распространить рассуждения из работы [69], доказывающей непрерывный аналог леммы 2 (наряду с более общими критериями робастного консенсуса), на случай систем с дискретным временем. Все доказательства из указанных источников, однако, достаточно сложны технически, и мы их здесь не приводим.

3.2. Консенсус в усредняющих неравенствах

В этом пункте мы введем важный инструмент для доказательства главного результата настоящей статьи. Именно, наряду с уравнениями (11), мы будем рассматривать рекуррентные усредняющие неравенства следующего вида:

$x\left(t+1\right)\le A\left(t\right)x\left(t\right), t\in \mathbb{N}$. (18)

Неравенство между векторами здесь понимается покомпонентно.

Следует отметить, что рекуррентное неравенство не может рассматриваться как алгоритм управления для группы агентов, поскольку его решение не является однозначно определенным. Однако такие неравенства представляются удобным инструментом в анализе многоагентных алгоритмов (см. [30], [61], [70]). Может показаться удивительным, что столь слабое ограничение на вектор состояния системы агентов в принципе позволяет установить какие-то свойства, однако, как будет показано, в предположении равномерной сильной связности графа может, как и в случае уравнений, быть доказан консенсус (12). В отличие от уравнений (11), решения которых ограничены, решения неравенств только полуограничены сверху. В частности, некоторые компоненты могут сходиться к –∞ при t → ∞. Так консенсус в случае неограниченных решений означает, что ${\overline{x}}_i=-\infty \forall i$. В практических приложениях, однако, мы часто знаем априорную нижнюю границу для решения, таким образом, ситуация консенсуса в бесконечности не реализуется.

Как мы увидим, при изучении решений неравенств часто важно знать поведение вектора невязок между правой и левой частью:

${∆}_i\left(t\right)\triangleq \sum _j{a}_{ij}\left(t\right)x_j\left(t\right)-x_i\left(t+1\right)\ge 0$, (19)

в частности, сходимость этих невязок к нулю:

${\Delta }_i\left(t\right)\underset{t\to \infty }{\to }0$. (20)

Следующая ключевая лемма гарантирует как достижение консенсуса, так и сходимость к нулю невязок для любого ограниченного решения (18).

Лемма 3. Пусть последовательность стохастических матриц A(t) имеет равномерно положительные диагональные элементы $a_{ii}\left(t\right)\ge \eta >0$, а переменный граф $\mathcal{G}\left[A\left(\cdot \right)\right]$ равномерно сильно связен. Тогда для любого решения неравенства (18) имеет место консенсус (12), а если решение ограничено снизу, то выполнено (20) при любом $i\in \mathcal{V}$.

Доказательство леммы 3 дано в приложении; специальные случаи этой леммы (предполагающие равномерную положительность всех ненулевых элементов матрицы, а не только диагональных) были доказаны в работах первого автора [30], [70]. Отметим, что требование равномерной сильной связности может быть существенно ослаблено, наиболее общий результат приведен в диссертации [28].

3.3. Консенсусные алгоритмы для пересечения выпуклых множеств

Рассмотрим несколько классов алгоритмов, предложенных в литературе для решения многоагентной задачи о пересечении выпуклых множеств. Как будет показано, техника усредняющих неравенств позволяет достаточно просто доказать сходимость состояния всех агентов в каждом из указанных алгоритмов к некоторой консенсусной точке, лежащей в пересечении множеств.

Именно, предположим, что выпуклое замкнутое множество ${\Xi }_i\subset {ℝ}^d$, связанное с агентом $i\in \mathcal{V}$, является множеством неподвижных точек фейеровского относительно некоторой нормы ||·|| отображения P_i (в наиболее распространенном случае, P_i – проектор на множество Ξ_i, а норма евклидова). Предположим, что агент i способен вычислять знач. P_i(ξ) в произвольной заданной точке ξ.

3.3.1. Классы консенсусных алгоритмов. Мы покажем, что при выполнении некоторых ограничений на граф, точка, принадлежащая Ξ_∗, может быть вычислена одним из следующих алгоритмов, основанных на последовательном усреднении с одновременным применением фейеровских операторов:

${\xi }^i\left(t+1\right)=P_i\left[{\sum }_{j\in \mathcal{V}}{a}_{ij}\left(t\right){\xi }^j\left(t\right)\right], i\in \mathcal{V}$, (21)

${\xi }^i\left(t+1\right)=P_i\left[{\sum }_{j\in \mathcal{V}}{a}_{ij}\left(t\right)P_j\left({\xi }^j\left(t\right)\right)\right], i\in \mathcal{V}$, (22)

${\xi }^i\left(t+1\right)={\sum }_{j\in \mathcal{V}}{a}_{ij}\left(t\right)P_j\left({\xi }^j\left(t\right)\right), i\in \mathcal{V}$, (23)

${\xi }^i\left(t+1\right)=a_{ii}\left(t\right)P_i\left({\xi }^i\left(t\right)\right)+\sum _{j\ne i}{a}_{ij}\left(t\right){\xi }^j\left(t\right), i\in \mathcal{V}$. (24)

Во всех указанных алгоритмах, как и прежде, $A\left(t\right)=\left(a_{ij}\left(t\right)\right)$ – стохастические матрицы. Отметим, что в вырожденном случае, когда у агентов нет ограничений (${\Xi }_i={ℝ}^d$ и P_i = Id) алгоритмы (21)–(24) превращаются в стандартную процедуру последовательного усреднения, применяемую для достижения консенсуса (см. [54], [59], [71]) (с единственной разницей, что состояние агента является многомерным вектором, а не скаляром — это, очевидно, никоим образом не меняет условий сходимости алгоритма). Вместе с тем, в общем случае условие сходимости существенно более ограничительно: требуется равномерная сильная связность, а не квазисильная, как в лемме 2. Это ограничение на граф накладывается во всех известных авторам работах. Метод доказательства сходимости, изложенный в настоящей статье, сводит каждый из алгоритмов к системе усредняющих неравенств, сильная связность требуется для применения леммы 3.

Происхождение и особенности алгоритмов (21)–(24). Алгоритм (21) был предложен в основополагающей статье [25] для случая проекционных операторов P_i, посвященной проблемам распределенной оптимизации, а затем развит в [46], где были ослаблены некоторые предположения (в частности, требование симметричности матрицы a_ij) и исследована робастность алгоритма [25] к запаздываниям¹¹ . В более поздней работе [50] алгоритм (21) был предложен для поиска общей точки фейеровских¹² отображений P_i. Существенной особенностью данного алгоритма является то, что агент сначала получает состояния соседей, а затем, вычисляет P_i от усредненного значения. Отметим, что если P_i – проектирование на Ξ_i , то состояние агента i не покидает множества Ξ_i при t ≥ 0. В этом случае агент стремится сблизить свое состояние с состояниями соседей, не нарушая собственное ограничение.

Алгоритм (24) был изначально предложен [72] для решения систем линейных уравнений, однако работает и для более общего случая. В этом случае Ξ_i – линейные гиперплоскости, а операторы проектирования P_i можно вычислить аналитически. Как и в алгоритме (21), агенты обмениваются своими состояниями. Однако имеются два принципиальных отличия: во-первых, агент может вычислять значение P_i, не дожидаясь получения соседних измерений (на практике, это может привести к ускорению вычислений), а во-вторых, состояние агента i, как правило, не принадлежит Ξ_i ни на одном шаге.

Алгоритм (23) аналогичен по структуре алгоритму Чиммино, с той разницей, что каждый агент, во-первых, имеет свое приближение к точке из пересечения множеств ξⁱ, а во-вторых, вместо барицентра всех проекций вычисляется некоторая выпуклая комбинация проекций соседних агентов. Близкие по структуре распределенные алгоритмы изучались в [17], однако в этой работе не вводились явно агенты, и не рассматривался случай переменного графа. Отметим, что в случае этого алгоритма агенты не только не раскрывают соседям информацию о своем множестве, но даже не обмениваются состояниями (это может быть существенно для защиты информации).

Наконец, алгоритм (22) был предложен в работе [73], также посвященной алгоритмам решения алгебраических уравнений. Как и в алгоритме (23), агенты обмениваются значениями P_i, однако затем агент повторно вычисляет значение P_i. В случае проекций, как уже обсуждалось, это гарантирует, что состояние агента не покидает желаемого множества. Как будет показано ниже, это также позволяет избежать некоторых патологических точек равновесия, возникающих в системе (23) (при пустом пересечении множеств ${\Xi }_{*}\ne \cancel{0}$).

3.3.2. Теорема о консенсусе с ограничениями. Предположим, что ${\Xi }_{*}=\cap {\Xi }_i=\cap \mathcal{F}\left(P_i\right)$ непусто. Будем говорить, что установлен консенсус с ограничениями (см. [25]), если при произвольных начальных состояниях агентов существуют и равны между собой следующие пределы:

$\underset{t\to \infty }{\lim }{\xi }^1\left(t\right)=\cdots =\underset{t\to \infty }{\lim }{\xi }^n\left(t\right)\in {\Xi }_{*}$. (25)

Анализ алгоритмов (21)–(24) опирается на свойства сходимости усредняющих неравенств (18) и лемму 2 о робастности консенсуса. Сформулируем основной результат, который будет доказан в приложении.

Теорема 1. Предположим, что отображения $P_i:{ℝ}^d\to {ℝ}^d$ являются фейеровскими относительно некоторой общей нормы ||·|| и имеют по крайней мере одну общую неподвижную точку, т. е. ${\Xi }_{*}={\cap }_{i\in \mathcal{V}}\mathcal{F}\left(P_i\right)\ne \cancel{0}$. Пусть последовательность стохастических матриц A(t) имеет равномерно положительные диагональные элементы $a_{ii}\left(t\right)\ge \eta >0$, и переменный граф G[A(·)], соответствующий A(t), равномерно сильно связен. Тогда каждый из алгоритмов (21)–(24) находит общую неподвижную точку {P_i}, т. е. состояния агентов ξⁱ сходятся к консенсусу (25).

Отметим что теорема 1 в ее полной общности публикуется впервые. Сходимость алгоритмов (21), (22) и (24) с помощью рекуррентных усредняющих неравенств впервые была доказана в [30] при дополнительном предположении (15), которое впоследствии было снято в [28]. Исследование алгоритма (23), однако, проведено не было.

3.3.3. Замечания к теореме 1. Отметим, что в условиях отсутствия общих точек у множеств Ξ_i сходимость векторов ξⁱ(t) к общему значению ξ_* при t → ∞ для алгоритмов (21), (22) и (24), очевидно, невозможна. Для алгоритмов (21) и (22) это так, поскольку ξⁱ(t) ∈ Ξ_i при любом $i\in \mathcal{V}$, таким образом, общий предел автоматически является общей точкой всех Ξ_i. Для (24) это следует из непрерывности P_i: предполагая, что ${\xi }^i\left(t\right)\underset{t\to \infty }{\to }{\xi }_{*}$, мы имели бы

$a_{ii}\left(t\right)\left[P_i\left({\xi }^i\left(t\right)\right)-{\xi }^i\left(t\right)\right]={\xi }^i\left(t+1\right)-\sum _{j\in \mathcal{V}}{a}_{ij}\left(t\right){\xi }^j\left(t\right)\underset{t\to \infty }{\to }0$,

что в силу равномерной положительности a_ii вновь означает, что ξ_* = P_i(ξ_*) при всех i, т. е. ξ_* – общая неподвижная точка семейства операторов. Алгоритм (23), однако, является исключением: консенсус при этом алгоритме возможен, теоретически, и при пустом пересечении множеств Ξ_i. Рассмотрим, к примеру, систему из двух агентов с множествами ограничений Ξ₁ = {–1}, Ξ₂ = {–2} и весовыми коэффициентами $a_{11}=a_{12}=a_{21}=a_{22}=1/2$. Очевидно, что ${\xi }^1\left(t\right)\equiv {\xi }^2\left(t\right)\equiv 0$ – точка равновесия системы (23), не принадлежащая ни одному из множеств Ξ_i.

Вместе с тем, в случае, когда консенсус не достигается, вопрос о поведении траекторий системы является, насколько известно авторам, открытым. Неизвестно в частности, даже при постоянной матрице весов, всегда ли в этом случае имеет место сходимость к периодической или квазипериодической траектории. Более того, даже ограниченность решений, как видно из доказательства в приложении, опирается на непустоту ${\Xi }_{*}={\cap }_i{\Xi }_i$ и, за исключением специальных случаев (например, P_i – проектор на ограниченное множество Ξ_i), вообще говоря, не является очевидным свойством.

Следует отметить также, что скорость сходимости алгоритмов (21)–(24) достаточно трудно оценить явно даже в случае постоянного графа. В случае же переменного графа, даже точная скорость сходимости обычных консенсусных алгоритмов (P_i = Id) до конца не исследована; ряд оценок на скорость сходимости может быть найден в обзоре [74]. Как показано в недавней работе [75], оценка скорости сходимости алгоритмов консенсуса сводится к вычислению наибольшего коэффициента эргодичности для некоторого компактного множества стохастических матриц. Существуют “ускоренные” модификации алгоритма (21) для решения систем линейных уравнений (см. [27], [73]), для которых доказана экспоненциальная сходимость к консенсусу. Данные алгоритмы не были исследованы в случае произвольных фейеровских операторов, а их анализ требует техники, выходящей за рамки данного обзора.

В настоящей статье мы не рассматриваем стохастические варианты алгоритма пересечения выпуклых множеств, в частности, рандомизированную версию алгоритма (24) из работы [76], а также рандомизированные модификации алгоритма Качмаржа (см., например, обзор литературы в [77]). Следует отметить, что для некоторых из рассмотренных выше алгоритмов существуют аналоги с непрерывным временем, например, в работе [26] приведен следующий аналог алгоритма (24):

${\dot{\xi }}^i\left(t\right)=\sum _{j\in \mathcal{V}}{a}_{ij}\left(t\right)\left({\xi }^j\left(t\right)-{\xi }^i\left(t\right)\right)+P_i\left({\xi }^i\left(t\right)\right)-{\xi }^i\left(t\right)$. (26)

Исследование данного алгоритма возможено с помощью теории усредняющих неравенств в непрерывном времени (см. [28], [29]); мы не приводим соответствующие результаты, поскольку они полностью аналогичны критериям сходимости в дискретном времени.

4. ЗАКЛЮЧЕНИЕ

Авторы благодарны редакторам специального выпуска, посвященного Б. Т. Поляку, за возможность представить данный обзор, который представляет расширенный материал лекции, прочитанной первым автором на Традиционной летней школе по управлению и оптимизации им. Б. Т. Поляка летом 2023 г. В обзоре представлена история задачи о пересечении выпуклых множеств в пространстве, а также недавние результаты первого автора, относящиеся к многоагентной постановке этой задачи и децентрализованным алгоритмам для ее решения. Борис Теодорович Поляк считал статью [15], в которой был получен ряд важных результатов об экспоненциальной сходимости проекционных алгоритмов, одной из важнейших своих работ. Об этой статье он, в частности, рассказывал на семинаре ИПУ РАН, организованном в честь присуждения ему премии им. Хачияна¹³. Cогласно базе данных Google Scholar, английская версия данной статьи к настоящему моменту процитирована более 1000 раз.

Следует отметить, что хотя с доказательства первой теоремы фон Неймана, устанавливающей сходимость метода последовательных проекций для двух линейных подпространств, прошло уже 90 лет, теория проекционных алгоритмов далека от своего завершения. Это относится как к классической (централизованной) версии задачи, так и многоагентной (децентрализованной) постановке. Как уже было сказано, достаточно много вопросов связано со скоростью сходимости алгоритмов, в частности, точная оценка скорости неизвестна даже для алгоритма Качмаржа. При замене проекционных операторов фейеровскими отображениями, ассоциированными с множествами, оценки скорости сходимости удается получить лишь в специальных случаях (см. [44]). В случае децентрализованного алгоритма, даже для консенсуса без ограничений (когда все множества совпадают с пространством) оценка скорости сходимости состояний агента к консенсусному значению является нетривиальной задачей (см. [74]).

Другим открытым вопросом является нахождения минимальных (необходимых и достаточных) условий связности графа. Как показано в диссертации [28], равномерная связность в леммах 2 и 3 может быть существенно ослаблена, однако приведенное условие все равно является только достаточным, а не необходимым, кроме того, его проверка для произвольного переменного графа затруднительна.

Перспективным направлением исследований представляется также развитие проекционных методов для многообразий (см. [24]) на многоагентный случай. Данная задача связана с вопросом о сходимости консенсусных алгоритмов на многообразиях (см. [78]).

ПРИЛОЖЕНИЕ

1. Доказательство леммы 3. Предположим, что все условия леммы 3 выполнены, в частности, a_ii(t) ≥ η. Рассмотрим сначала ситуацию, когда условие равномерной связности выполнено с T = 1, т. е. все графы $\mathcal{G}\left[A\left(t\right)\right]$ являются сильно ε-связными. Обозначим число агентов $n=\left|\mathcal{V}\right|$ и, при каждом t = 0, 1, ... занумеруем элементы в порядке возрастания компонент x(t):

$\begin{array}{l}\mathcal{V}=\left\{{\sigma }_1\left(t\right),\dots ,{\sigma }_N\left(t\right)\right\},\\ y_1\left(t\right)\triangleq x_{{\sigma }_1\left(t\right)}\left(t\right)\le y_2\left(t\right)\triangleq x_{{\sigma }_2\left(t\right)}\left(t\right)\le \cdots \le y_n\left(t\right)\triangleq x_{{\sigma }_n\left(t\right)}\left(t\right).\end{array}$

Мы докажем следующее вспомогательное неравенство:

$y_{k+1}\left(t+1\right)\le \left(1-{\epsilon }_0\right)y_n\left(t\right)+{\epsilon }_0{y}_k\left(t\right) \forall k=\mathrm{0,} 1, \dots , n-1$, (27)

где ${\epsilon }_0=\min \left(\epsilon ,\eta \right)$. Действительно, обозначим $I\triangleq \left\{{\sigma }_{k+1}\left(t\right),\dots ,{\sigma }_n\left(t\right)\right\}$. Так как $\mathcal{G}\left[A\left(t\right)\right]$ – сильно ε-связный граф, то существуют i ∈ I и $m\in J\triangleq \mathcal{V}\backslash I$ такие, что $a_{im}\left(t\right)\ge \epsilon \ge {\epsilon }_0$. Следовательно,

$x_i\left(t+1\right)\le a_{im}\left(t\right)\underset{\le y_k\left(t\right)}{\underbrace{x_m\left(t\right)}}+\sum _{j\in \mathcal{V}\backslash \left\{m\right\}}{a}_{ij}\left(t\right)\underset{\le y_n\left(t\right)}{\underbrace{x_j\left(t\right)}}\le \left(1-{\epsilon }_0\right)y_n\left(t\right)+{\epsilon }_0{y}_k\left(t\right)$.

С другой стороны, используя неравенство $a_{ii}\left(t\right)\ge \eta \ge {\epsilon }_0$, для каждого j ∈ J мы имеем

$x_j\left(t+1\right)\le a_{jj}\left(t\right)\underset{\le y_k\left(t\right)}{\underbrace{x_j\left(t\right)}}+\sum _{\mathcal{l}\in \mathcal{V}\backslash \left\{j\right\}}{a}_{j\mathcal{l}}\left(t\right)\underset{\le y_m\left(t\right)}{\underbrace{x_l\left(t\right)}}\le \left(1-{\epsilon }_0\right)y_n\left(t\right)+{\epsilon }_0{y}_k\left(t\right)$.

Следовательно, все компоненты x с индексами из множества $J\cup \left\{i\right\}$ не больше правой части из (27). Для доказательства (27) остается заметить, что мощность последнего множества равна k + 1.

Поскольку $y_n\left(t\right)=\max x\left(t\right)$ не возрастает, существует предел $y_{*}={\lim }_{t\to \infty }{y}_n\left(t\right)\ge -\infty$. Если y_* = –∞, то, очевидно, $x_i\left(t\right)\underset{t\to \infty }{\to }-\infty$. Иначе, мы можем использовать (27) для доказательства того, что $y_k\left(t\right)\underset{t\to \infty }{\to }{y}_{*}>-\infty$, используя обратную индукцию по $k=n, n-\mathrm{1,} \dots , 1$, иными словами, достигается консенсус (12).

Случай произвольного периода T > 1 сводится к уже рассмотренному случаю: достаточно заметить, что в силу равномерной положительности диагональных элементов графы матриц

$\tilde{A}\left(k\right)=A\left(kT\right)A\left(kT+1\right)\cdots A\left(kT+T-1\right)$

являются сильно $\tilde{\epsilon }$-связными при некотором $\tilde{\epsilon }=\tilde{\epsilon }\left(\epsilon ,\eta \right)>0$. Поэтому сходимость к консенсусу имеет место для подпоследовательности $\tilde{x}\left(k\right)=x\left(kT\right)$, удовлетворяющей рекуррентному неравенству

$\tilde{x}\left(k+1\right)\le \tilde{A}\left(k\right)\tilde{x}\left(k\right)$.

Поскольку для любого $\mathcal{l}=\mathrm{1,} 2, \dots , T-1$ справедливы неравенства

$\begin{array}{l}\tilde{x}\left(k+1\right)=x\left(kT+T\right)\le A\left(kT+T-1\right)\cdots A\left(kT+\mathcal{l}\right)x\left(kT+\mathcal{l}\right),\\ x\left(kT+\mathcal{l}\right)=A\left(kT+\mathcal{l}-1\right)\cdots A\left(kT\right)\tilde{x}\left(k\right),\end{array}$

то из сходимости $\tilde{x}\left(k\right)\underset{k\to \infty }{\to }\tilde{c}{1}_n$ (где $\tilde{c}\in ℝ$ и 1_n обозначают вектор-столбец из единиц размерности n) и стохастичности матриц A(t) вытекает сходимость $x\left(kT+\mathcal{l}\right)\underset{k\to \infty }{\to }\tilde{c}{1}_n$ при любом $\mathcal{l}=\mathrm{1,} \mathrm{2,} \dots , T-1$, следовательно, достигается консенсус между агентами.

Наконец, свойство (20) для ограниченных решений также очевидно из того, что матрицы A(t) стохастические (и, в частности, равномерно ограничены): если $x\left(t\right)\underset{t\to \infty }{\to }c{1}_n$ (при некотором $c\in ℝ$), то $A\left(t\right)1_n=1_n$, а следовательно,

$A\left(t\right)x\left(t\right)=A\left(t\right)\left(x\left(t\right)-c{1}_n\right)+c{1}_n\underset{t\to \infty }{\to }c{1}_n$.

2. Доказательство леммы 1 и теоремы 1.

Лемма о фейеровском отображении.

Доказательства теоремы и леммы используют следующий технический результат.

Лемма 4. Пусть P – фейеровский оператор в некоторой норме ||·||, и ξ⁰ – его неподвижная точка. Обозначим $d\left(\xi \right)\triangleq ||\xi -{\xi }^0||-||P\xi -{\xi }^0||\ge 0$ и рассмотрим ограниченную последовательность векторов ξ(t) такую, что $d\left(\xi \left(t\right)\right)\underset{t\to \infty }{\to }0$. Тогда

$||P\xi \left(t\right)-\xi \left(t\right)||\underset{t\to \infty }{\to }0$.

Доказательство. Предположим противное: $||P\xi \left(t_r\right)-\xi \left(t_r\right)||\ge \epsilon$ для любого $r\in \mathbb{N}$, ε > 0, и последовательности t_r → ∞. Переходя к меньшей подпоследовательности, можно предположить, не умаляя общности, что векторы ξ(t_r) сходятся к пределу ${\xi }_{*}\in {ℝ}^d$. Поскольку P – непрерывное отображение, имеем $||P{\xi }_{*}-{\xi }_{*}||\ge \epsilon$ при d(ξ_*) = 0. Пришли к противоречию с (7), так как ${\xi }_{*}\cancel{\in }\mathcal{F}\left(P\right)$, в то время как $||P{\xi }_{*}-{\xi }^0||=||{\xi }_{*}-{\xi }^0||$. Лемма 4 доказана.

Доказательство леммы 1. Очевидно, что последовательность ξ(t) из леммы 1 ограничена в силу того, что расстояния от ξ(t) до любой точки из M не возрастают. Невозрастающая последовательность

$a\left(t\right)\triangleq ||\xi \left(t\right)-{\xi }^0||\ge 0$

для произвольного элемента ξ⁰ ∈ M имеет конечный предел при t → ∞. В частности, поскольку $P\xi \left(t\right)=\xi \left(t+1\right)$, то

$a\left(t\right)-a\left(t+1\right)=||\xi \left(t\right)-{\xi }^0||-||P\xi \left(t\right)-{\xi }^0||=d\left(\xi \left(t\right)\right)\underset{t\to \infty }{\to }0$.

В силу леммы 4, мы доказали, что $||P\xi \left(t\right)-\xi \left(t\right)||\underset{t\to \infty }{\to }0$.

Отметим теперь, что в силу ограниченности, существует подпоследовательность ξ(t_k), сходящаяся к некоторому элементу ${\xi }_{*}\in {ℝ}^d$. Очевидно, что

$||P\left({\xi }_{*}\right)-{\xi }_{*}||=\underset{k\to \infty }{\lim }||P\left(\xi \left(t_k\right)\right)-\xi \left(t_k\right)||=0$,

т.е. ξ_* ∈ M. Поскольку ξ⁰ в рассуждении выше произвольно, мы можем выбрать ξ⁰ = ξ_*. Поскольку при t ≥ t_k, мы имеем

$0\le ||\xi \left(t\right)-{\xi }_{*}||\le ||\xi \left(t_k\right)-{\xi }_{*}||$,

где правая часть может быть сделана сколь угодно малой при большом k, то $||\xi \left(t\right)-{\xi }_{*}||\underset{t\to \infty }{\to }0$. Лемма 1 доказана.

Доказательство теоремы 1. Сначала введем некоторые вспомогательные обозначения. Выберем произвольную точку ξ⁰ ∈ Ξ_∗ и положим, по определению, ${\delta }_i\left(\xi \right)\triangleq ||\xi -{\xi }^0||-||P_i\xi -{\xi }^0||\ge 0$. Пусть ${\zeta }^i\left(t\right)={\sum }_{j\in \mathcal{V}}{a}_{ij}\left(t\right){\xi }^j\left(t\right)$. Центральная идея доказательства состоит в исследовании свойств векторов $x\left(t\right)={\left(x_i\left(t\right)\right)}_{i\in \mathcal{V}}$, компоненты которых $x_i\left(t\right)\triangleq ||{\xi }^i\left(t\right)-{\xi }^0||$ обозначают расстояния от состояний агентов ξ_i(t) до выбранной неподвижной точки.

Шаг 1. Покажем сначала, что для каждого из указанных в теореме алгоритмов векторы x(t) удовлетворяют усредняющему рекуррентному неравенству (18).

В случае алгоритма (21) имеем

$\begin{array}{c}{x}_i\left(t+1\right)=||P_i\left({\zeta }^i\left(t\right)\right)-{\xi }^0||\stackrel{\left(8\right)}{\le }||{\zeta }^i\left(t\right)-{\xi }^0||=\\ =\sum _j{a}_{ij}\left(t\right)\left({\xi }^j\left(t\right)-{\xi }^0\right)\le \sum _j{a}_{ij}\left(t\right)||{\xi }^j\left(t\right)-{\xi }^0||=\sum _j{a}_{ij}\left(t\right)x_j\left(t\right).\end{array}$ (28)

Аналогично рассматривается случай (22). Обозначив ${\overline{\zeta }}^i\left(t\right)\stackrel{\Delta }{=}{\sum }_{j\in \mathcal{V}}{a}_{ij}\left(t\right)P_j\left({\xi }^j\left(t\right)\right)$, имеем

$\begin{array}{c}{x}_i\left(t+1\right)=||P_i\left({\overline{\zeta }}^i\left(t\right)\right)-{\xi }^0||\stackrel{\left(8\right)}{\le }||{\overline{\zeta }}^i\left(t\right)-{\xi }^0||=\\ =\sum _j{a}_{ij}\left(t\right)\left(P_j\left({\xi }^j\left(t\right)\right)-{\xi }^0\right)\le \sum _j{a}_{ij}\left(t\right)||P_j\left({\xi }^j\left(t\right)\right)-{\xi }^0||\stackrel{\left(8\right)}{\le }\\ \le \sum _j{a}_{ij}\left(t\right)||{\xi }^j\left(t\right)-{\xi }^0||=\sum _j{a}_{ij}\left(t\right)x_j\left(t\right).\end{array}$ (29)

В случае алгоритма (23) нетрудно видеть, что

$\begin{array}{c}{x}_i\left(t+1\right)=\sum _j{a}_{ij}\left(t\right)\left(P_j\left({\xi }^j\left(t\right)\right)-{\xi }^0\right)\le \sum _j{a}_{ij}\left(t\right)||P_j\left({\xi }^j\left(t\right)\right)-{\xi }^0||\stackrel{\left(8\right)}{\le }\\ \le \sum _j{a}_{ij}\left(t\right)||{\xi }^j\left(t\right)-{\xi }^0||=\sum _j{a}_{ij}\left(t\right)x_j\left(t\right).\end{array}$ (30)

В случае алгоритма (24) имеем

$\begin{array}{c}{x}_i\left(t+1\right)=||a_{ii}\left(t\right)\left(P_i\left({\xi }^i\left(t\right)\right)-{\xi }^0\right)+\sum _{j\ne i}{a}_{ij}\left(t\right)\left({\xi }^j\left(t\right)-{\xi }^0\right)||\le \\ \le a_{ii}\left(t\right)||P_i\left({\xi }^i\left(t\right)\right)-{\xi }^0||+\sum _{j\ne i}{a}_{ij}\left(t\right)||{\xi }^j\left(t\right)-{\xi }^0||\stackrel{\left(8\right)}{\le }\\ \le a_{ii}\left(t\right)||{\xi }^i\left(t\right)-{\xi }^0||+\sum _{j\ne i}{a}_{ij}\left(t\right)x_j\left(t\right)=\sum _{j\in \mathcal{V}}{a}_{ij}\left(t\right)x_j\left(t\right).\end{array}$ (31)

Заметим, что x_i(t) неотрицательны в силу определения. В силу теоремы 3 усредняющее неравенство (18) устанавливает консенсус, т. е. $x_i\left(t\right)\underset{t\to \infty }{\to }c\ge 0 \forall i$, где зависит от конкретного решения. Из теоремы 3 также следует, что

${\Delta }_i\left(t\right)\underset{t\to \infty }{\to }0 \forall i\in \mathcal{V}$, (32)

где Δ_i(t) невязки определены формулой (19).

Шаг 2. Исследуя структуру невязок Δ_i, покажем, что

$||{\xi }^i\left(t+1\right)-{\zeta }^i\left(t\right)||\underset{t\to \infty }{\to }0 \forall i$, (33)

$||P_i\left({\xi }^i\left(t\right)\right)-{\xi }^i\left(t\right)||\underset{t\to \infty }{\to }0 \forall i$. (34)

Векторы ξⁱ(t) (а значит, и ζⁱ(t)) ограничены, так как расстояния x_i(t) от них до ξ⁰ ограничены сверху в силу (18). Для алгоритма (21) из неравенства (28) следует, что

${\Delta }_i\left(t\right)\ge ||{\zeta }^i\left(t\right)-{\xi }^0||-||P_i\left({\zeta }^i\left(t\right)\right)-{\xi }^0||={\delta }_i\left({\zeta }^i\left(t\right)\right)$. (35)

Применяя лемму 4 к P = P_i из (32) получаем $||P_i\left({\zeta }^i\left(t\right)\right)-{\zeta }^i\left(t\right)||\underset{t\to \infty }{\to }0$, что эквивалентно (33), поскольку ${\xi }^i\left(t+1\right)=P_i\left({\zeta }^i\left(t\right)\right)$. Чтобы вывести (34), заметим, что

$0\le ||P_i\left({\xi }^i\left(t+1\right)\right)-{\xi }^i\left(t+1\right)||\le ||P_i\left({\zeta }^i\left(t\right)\right)-{\zeta }^i\left(t\right)||+||{\zeta }^i\left(t\right)-{\xi }^i\left(t+1\right)||\underset{t\to \infty }{\to }0$.

В случае алгоритма (24), заметим, что (31) дает

${\Delta }_i\left(t\right)\ge a_{ii}\left(t\right)\left(||{\xi }^i\left(t\right)-{\xi }^0||-||P_i\left({\xi }^i\left(t\right)\right)-{\xi }^0||\right)\ge \eta {\delta }_i\left({\xi }^i\left(t\right)\right)$, (36)

где η > 0 – константа из предположения теоремы. Применяя лемму 4, можно доказать (34), что влечет за собой также (33), поскольку

${\xi }^i\left(t+1\right)={\zeta }^i\left(t\right)+a_{ii}\left(t\right)\left(P_i\left({\xi }^i\left(t\right)\right)-{\xi }^i\left(t\right)\right)$.

Доказательство в случае алгоритма (22) объединяет две вышеупомянутые оценки. Во-первых, (29) приводит к неравенству

${\Delta }_i\left(t\right)\ge ||{\overline{\zeta }}^i\left(t\right)-{\xi }^0||-||P_i\left({\overline{\zeta }}^i\left(t\right)\right)-{\xi }^0||={\delta }_i\left({\overline{\zeta }}^i\left(t\right)\right)$, (37)

которое аналогично (35) и, поскольку $P_i\left({\overline{\zeta }}^i\left(t\right)\right)={\xi }^i\left(t+1\right)$, влечет

$||{\xi }^i\left(t+1\right)-{\overline{\zeta }}^i\left(t\right)||\underset{t\to \infty }{\to }0$. (38)

Во-вторых, (29) также влечет (36), что, в свою очередь, влечет (34). Таким образом,

$||{\overline{\zeta }}^i\left(t\right)-{\zeta }^i\left(t\right)||\underset{t\to \infty }{\to }0$. (39)

Это доказывает (33), так как $||{\xi }^i\left(t+1\right)-{\zeta }^i\left(t\right)||\le ||{\xi }^i\left(t+1\right)-{\overline{\zeta }}^i\left(t\right)||+||{\overline{\zeta }}^i\left(t\right)-{\zeta }^i\left(t\right)||$.

Доказательство для алгоритма (23) аналогично доказательству для алгоритма (22). В этом случае (38) выполнено по определению ${\overline{\zeta }}^i$ (левая часть равна 0), а неравенство (36) легко следует из (30), поскольку

$a_{ij}\left(t\right)\left(||{\xi }^j\left(t\right)-{\xi }^0||-||P_j\left({\xi }^j\left(t\right)\right)-{\xi }^0||\right)\ge 0 \forall j\ne i$.

По аналогии с алгоритмом (22) можно проверить выполнение уравнений (34) и (33).

Таким образом, мы доказали, что при всех алгоритмах, изучаемых в теореме, решения обладают тем свойством, что

$f^i\left(t\right)\stackrel{\Delta }{=}{\xi }^i\left(t+1\right)-{\zeta }^i\left(t\right)={\xi }^i\left(t+1\right)-\sum _{j\in \mathcal{V}}{a}_{ij}\left(t\right){\xi }^j\left(t\right)\underset{t\to \infty }{\to }0$.

Отметим теперь, что состояния агентов ξⁱ, в силу определения fⁱ(t), могут рассматриваться как траектории усредняющей системы с возмущением:

${\xi }^i\left(t+1\right)=\sum _j{a}_{ij}\left(t\right){\xi }^j\left(t\right)+f^i\left(t\right)$,

где fⁱ(t) – нечто, сходящееся к нулю. В силу леммы 2 наличие исчезающих на бесконечности возмущений¹⁴ не нарушает синхронизации между агентами: $||{\xi }^i\left(t\right)-{\xi }^j\left(t\right)||\underset{t\to \infty }{\to }0$.

Шаг 3. Рассмотрим теперь состояние агента с индексом $i\in \mathcal{V}$. Поскольку векторы ξⁱ(t) ограничены, то существует последовательность t_r → ∞ такая, что ${\xi }^i\left(t_r\right)\underset{r\to \infty }{\to }{\xi }_{*}\in {ℝ}^d$. Ввиду синхронизации мы имеем ${\xi }^j\left(t_r\right)\underset{r\to \infty }{\to }{\xi }_{*}$ для каждого $j\in \mathcal{V}$. Из свойства (34) следует, что $P_i\left({\xi }_{*}\right)={\xi }_{*}\forall i$, отсюда ξ_* ∈ Ξ_∗. Остается показать, что ${\xi }^i\left(t\right)\underset{t\to \infty }{\to }{\xi }_{*}$. Заметим, что на шаге 1 мы не уточняли выбор ξ⁰, которая может быть произвольной точкой в Ξ_∗. Мы доказали, что для любой такой точки расстояния $x_i\left(t\right)=||{\xi }^i\left(t\right)-{\xi }^0||$ сходятся к некоторому значению c, зависящему от ξ⁰ и начальных условий. В частности, подставляя ξ⁰ = ξ_*, получаем, что существуют пределы

$x_i\left(t\right)=\underset{t\to \infty }{\lim }||{\xi }^i\left(t\right)-{\xi }_{*}||=c_{*} \forall i$.

Вспоминая, что $x_i\left(t_r\right)\underset{r\to \infty }{\to }0$, имеем c_* = 0, что доказывает достижение консенсуса (25), причем общий предел состояний агентов в (25) равен ξ_* ∈ Ξ_∗.

¹ Cимвол |·| всюду ниже обозначает обычную евклидову норму в ${ℝ}^d$: $|x{|}^2={\sum }_i{x}_i^2=x^{{\rm T}}x$.

² Символ $\measuredangle$ обозначает угол между векторами (в интервале [0, π]).

³ Здесь и далее элементы ${ℝ}^d$ понимаются как вектор-столбцы, соответственно a^Tξ есть скалярное произведение двух векторов a и ξ.

⁴ Также этот алгоритм называется методом построчного действия (row action method), поскольку на каждом шаге используется одна строка матрицы ограничений.

⁵ В случае необщего положения, когда точка равноудалена от нескольких множеств и argmax определен неоднозначно, можно выбрать произвольное значение; обычно, выбирается наименьший индекс (см. [13]).

⁶ К сожалению, при оцифровке переводной версии работы [41] фамилия первого автора была ошибочно написана как Gubin; такое написание до сих пор сохраняется в электронной базе ScienceDirect и попало в большинство обзоров по алгоритмам пересечения выпуклых множеств.

⁷ Термин “M-фейеровский оператор”, введенный в работах И.И. Ерёмина, мотивирован понятием монотонной по Фейеру (относительно M) последовательности, введенным в [39]. Так называется последовательность $\left\{x_n\right\}\subset {ℝ}^d\backslash M$, такая что $x_{n+1}\ne x_n$ при всех n и $\parallel x_n-y\parallel \ge \parallel x_{n+1}-y\parallel$ при всех n и y ∈ M. Это понятие, в свою очередь, восходит к работе Фейера [49] о расположении корней полиномов.

⁸ Норма строго выпукла, если выполнено строгое неравенство треугольника: $\parallel x+y\parallel <\parallel x\parallel +\parallel y\parallel$ для любых линейно независимых векторов x, y.

⁹ Отметим, что в настоящем обзоре мы не рассматриваем общую философию теории многоагентных (мультиагентных) систем и не даем точного определения агентов, которое различается в теории управления и компьютерных науках. С историей вопроса и основными задачами теории многоагентных систем (также называемых сетевыми) можно ознакомиться, например, в статьях и монографиях [52]–[58].

¹⁰ Иными словами, граф является (квази)сильно ε-связным, если он остается (квази)сильно связным после удаления всех дуг, которые имеют вес меньший, чем ε.

¹¹ Как вытекает из результатов [28], [30], на самом деле к коммуникационным запаздываниям робастны все алгоритмы (21)–(24), поскольку такие запаздывания не нарушают свойств усредняющих алгоритмов и неравенств. В настоящем обзоре мы не рассматриваем вопросы робастности, которые в основном изучаются в рамках теории управления многоагентными системами и представляют интерес, если агенты ограничены в возможности быстро передавать информацию (например, связаны через Интернет).

¹² Отметим, что [50] накладывает ряд ограничений, в частности, свойство Фейера должно выполняться относительно ${\mathcal{l}}_p$ нормы на ${ℝ}^d$; как мы увидим ниже, это ограничение можно снять.

¹³ Видеозапись семинара доступна по ссылке https://www.youtube.com/watch?v=_6p5qQ15fpw.

¹⁴ Формально, лемма 2 была сформулирована для случая агентов со скалярными состояниями $x_i\in ℝ$, однако она, очевидно, сохраняет свою силу и для многомерного случая (достаточно рассмотреть проекции состояний агентов на каждую координатную ось).

作者简介

A. Proskurnikov

编辑信件的主要联系方式.
Email: avp1982@gmail.com
意大利, Torino

I. Zabaryanskaya

Email: akshiira@yandex.ru
俄罗斯联邦, Saint Petersburg

参考

补充文件

附件文件

动作

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)

索引源数据