Проекции на выпуклые множества

В математике проекции на выпуклые множества ( POCS ), иногда называемые методом чередующихся проекций , — это метод нахождения точки на пересечении двух замкнутых выпуклых множеств. Это очень простой алгоритм, который был переоткрыт много раз. ^[1] Простейший случай, когда множества являются аффинными пространствами , был проанализирован Джоном фон Нейманом . ^{[2] [3]} Случай, когда множества являются аффинными пространствами, является особым, поскольку итерации сходятся не только к точке на пересечении (предполагая, что пересечение непусто), но и к ортогональной проекции точки на пересечение. Для общих замкнутых выпуклых множеств предельная точка не обязательно должна быть проекцией. Классическая работа по случаю двух замкнутых выпуклых множеств показывает, что скорость сходимости итераций линейна. ^{[4] [5]} В настоящее время существуют расширения, которые рассматривают случаи, когда имеется более двух множеств или когда множества не являются выпуклыми , ^[6] или которые дают более быстрые скорости сходимости. Анализ POCS и связанных методов пытается показать, что алгоритм сходится (и если да, то найти скорость сходимости ), и сходится ли он к проекции исходной точки. Эти вопросы в основном известны для простых случаев, но являются темой активных исследований для расширений. Существуют также варианты алгоритма, такие как проекционный алгоритм Дайкстры . См. ссылки в разделе дополнительного чтения для обзора вариантов, расширений и приложений метода POCS; хорошую историческую справку можно найти в разделе III. ^[7]

Алгоритм

Пример на двух окружностях

Алгоритм POCS решает следующую задачу:

${\displaystyle {\text{find}}\;x\in \mathbb {R} ^{n}\quad {\text{such that}}\;x\in C\cap D}$

где C и D — замкнутые выпуклые множества .

Чтобы использовать алгоритм POCS, необходимо знать, как проецировать на множества C и D по отдельности, с помощью проекций . ${\displaystyle {\mathcal {P}}_{i}}$

Алгоритм начинается с произвольного значения и затем генерирует последовательность ${\displaystyle x_{0}}$

${\displaystyle x_{k+1}={\mathcal {P}}_{C}\left({\mathcal {P}}_{D}(x_{k})\right).}$

Простота алгоритма объясняет часть его популярности. Если пересечение C и D непустое, то последовательность , сгенерированная алгоритмом, будет сходиться к некоторой точке этого пересечения.

В отличие от алгоритма проекции Дайкстры , решение не обязательно должно быть проекцией на пересечение C и D.

Связанные алгоритмы

Пример усредненного варианта проекций

Метод усредненных проекций весьма похож. Для случая двух замкнутых выпуклых множеств C и D он осуществляется следующим образом:

${\displaystyle x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(x_{k}))}$

Давно известно, что он сходится глобально. ^[8] Более того, этот метод легко обобщить на более чем два множества; некоторые результаты сходимости для этого случая приведены в. ^[9]

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

${\displaystyle E=\{(x,y):x\in C,\;y\in D\}}$

который определен в пространстве продукта . Затем определите другой набор, также в пространстве продукта: ${\displaystyle \mathbb {R} ^{n}\times \mathbb {R} ^{n}}$

${\displaystyle F=\{(x,y):x\in \mathbb {R} ^{n},\,y\in \mathbb {R} ^{n},\;x=y\}.}$

Таким образом, нахождение эквивалентно нахождению . ${\displaystyle C\cap D}$ ${\displaystyle E\cap F}$

Чтобы найти точку в , используйте метод чередующейся проекции. Проекция вектора на множество F задается формулой . Следовательно ${\displaystyle E\cap F}$ ${\displaystyle (x,y)}$ ${\displaystyle (x+y,x+y)/2}$

${\displaystyle (x_{k+1},y_{k+1})={\mathcal {P}}_{F}({\mathcal {P}}_{E}((x_{k},y_{k})))={\mathcal {P}}_{F}(({\mathcal {P}}_{C}x_{k},{\mathcal {P}}_{D}y_{k}))={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(y_{k}),({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(y_{k})).}$

Так как и предполагая , то для всех и, следовательно, мы можем упростить итерацию до . ${\displaystyle x_{k+1}=y_{k+1}}$ ${\displaystyle x_{0}=y_{0}}$ ${\displaystyle x_{j}=y_{j}}$ ${\displaystyle j\geq 0}$ ${\displaystyle x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(x_{k}))}$

Ссылки

1. Bauschke, HH; Borwein, JM (1996). «О проекционных алгоритмах для решения выпуклых задач осуществимости». SIAM Review . 38 (3): 367–426. CiteSeerX  10.1.1.49.4940 . doi :10.1137/S0036144593251710.
2. Дж. фон Нейман, Нейман, Джон фон (1949). «О кольцах операторов. Теория редукции». Ann. of Math . 50 (2): 401–485. doi :10.2307/1969463. JSTOR  1969463.(переиздание конспектов лекций, впервые распространенное в 1933 году)
3. Дж. фон Нейман. Функциональные операторы, том II. Princeton University Press, Принстон, Нью-Джерси, 1950. Перепечатка мимеографированных лекционных заметок, впервые распространенных в 1933 году.
4. Губин, Л.Г.; Поляк, Б.Т.; Райк, Э.В. (1967). «Метод проекций для нахождения общей точки выпуклых множеств». Журнал вычислительной математики и математической физики СССР . 7 (6): 1–24. doi :10.1016/0041-5553(67)90113-9.
5. Bauschke, HH; Borwein, JM (1993). «О сходимости алгоритма чередующейся проекции фон Неймана для двух множеств». Set-Valued Analysis . 1 (2): 185–212. doi :10.1007/bf01027691. S2CID  121602545.
6. Льюис, Адриан С.; Малик, Жером (2008). «Переменные проекции на многообразиях». Математика исследования операций . 33 : 216–234. CiteSeerX 10.1.1.416.6182 . doi :10.1287/moor.1070.0291. 
7. Combettes, PL (1993). "Основы теоретико-множественной оценки" (PDF) . Труды IEEE . 81 (2): 182–208. doi :10.1109/5.214546. Архивировано из оригинала (PDF) 2015-06-14 . Получено 2012-10-09 .
8. А. Ауслендер. Численные методы для решения проблем оптимизации с учетом ограничений. Кандидатская диссертация, Факультет наук, Гренобль, 1969 год.
9. Льюис, А.С.; Люк, Д.Р.; Малик, Дж. (2009). «Локальная сходимость для чередующихся и усредненных невыпуклых проекций». Основы вычислительной математики . 9 (4): 485–513. arXiv : 0709.0109 . doi :10.1007/s10208-008-9036-y.

Дальнейшее чтение

• Книга 2011 года: «Методы чередующихся проекций» Рене Эскаланте и Маркоса Райдана (2011), изданная SIAM.