Алгоритм проекции Дикстра - Dykstras projection algorithm - Wikipedia

Не путать с Алгоритм Дейкстры.

Алгоритм Дикстры это метод, который вычисляет точку на пересечении выпуклые множества, и является вариантом переменная проекция метод (также называемый проекции на выпуклые множества метод). В своей простейшей форме метод находит точку на пересечении двух выпуклых множеств путем итеративного проецирования на каждое из выпуклых множеств; он отличается от метода переменного проецирования тем, что в нем есть промежуточные этапы. Параллельная версия алгоритма была разработана Гаффке и Матаром.

Метод назван в честь Ричарда Л. Дикстры, который предложил его в 1980-х годах.

Ключевое различие между алгоритмом Дикстры и стандартным методом чередующейся проекции возникает, когда на пересечении двух множеств имеется более одной точки. В этом случае метод попеременной проекции дает некоторую произвольную точку на этом пересечении, тогда как алгоритм Дикстры дает конкретную точку: проекцию р на перекресток, где р - начальная точка, используемая в алгоритме,

Алгоритм

Алгоритм Дикстры находит для каждого ${\displaystyle r}$ единственный ${\displaystyle {\bar {x}}\in C\cap D}$ такой, что:

${\displaystyle \|{\bar {x}}-r\|^{2}\leq \|x-r\|^{2},{\text{for all }}x\in C\cap D,}$

куда ${\displaystyle C,D}$ находятся выпуклые множества. Эта проблема эквивалентна поиску проекция из ${\displaystyle r}$ на съемочную площадку ${\displaystyle C\cap D}$, который обозначим через ${\displaystyle {\mathcal {P}}_{C\cap D}}$.

Чтобы использовать алгоритм Дикстры, нужно знать, как проецировать на множества ${\displaystyle C}$ и ${\displaystyle D}$ раздельно.

Сначала рассмотрим основные переменная проекция (он же POCS) метод (впервые изученный, в случае, когда множества ${\displaystyle C,D}$ были линейными подпространствами, согласно Джон фон Нейман^[1]), который инициализирует ${\displaystyle x_{0}=r}$ а затем генерирует последовательность

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

Алгоритм Дикстры имеет аналогичную форму, но использует дополнительные вспомогательные переменные. Начать с ${\displaystyle x_{0}=r,p_{0}=q_{0}=0}$ и обновить

${\displaystyle y_{k}={\mathcal {P}}_{D}(x_{k}+p_{k})}$

${\displaystyle p_{k+1}=x_{k}+p_{k}-y_{k}}$

${\displaystyle x_{k+1}={\mathcal {P}}_{C}(y_{k}+q_{k})}$

${\displaystyle q_{k+1}=y_{k}+q_{k}-x_{k+1}.}$

Тогда последовательность ${\displaystyle (x_{k})}$ сходится к решению исходной задачи. Результаты сходимости и современный взгляд на литературу см. ^[2]

Рекомендации

• Boyle, J.P .; Дикстра, Р. Л. (1986). Метод нахождения проекций на пересечение выпуклых множеств в гильбертовых пространствах. Конспект лекций по статистике. 37. С. 28–47. Дои:10.1007/978-1-4613-9940-7_3. ISBN  978-0-387-96419-5.
• Gaffke, N .; Матар, Р. (1989). «Алгоритм циклической проекции через двойственность». Метрика. 36: 29–54. Дои:10.1007 / bf02614077.

Цитаты

1. Дж. Фон Нейман, О кольцах операторов. Теория редукции, Ann. математики. 50 (1949) 401–485 (перепечатка конспектов лекций, впервые распространенная в 1933 году).
2. П. Л. Комбетс, Ж.-К. Песке, "Методы проксимального расщепления в обработке сигналов", в: Алгоритмы с фиксированной точкой для обратных задач в науке и технике, (Х. Х. Баушке, Р. С. Бурачик, П. Л. Комбеттс, В. Эльзер, Д. Р. Люк, Х. Волкович, редакторы), стр. 185–212. Спрингер, Нью-Йорк, 2011 г. [1]