Алгоритм проекции Дикстры

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

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

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

Алгоритм

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

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

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

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

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

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

.

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

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

p_{k+1}=x_{k}+p_{k}-y_{k}

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

q_{k+1}=y_{k}+q_{k}-x_{k+1}.

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

Цитаты

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

Ссылки

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

[1] Дж. фон Нейман, О кольцах операторов. Теория редукции, Анн. математики. 50 (1949) 401–485 (переиздание конспектов лекций, впервые распространенных в 1933 году).

[2] PL Combettes и Ж.-К. Песке, «Методы проксимального разделения при обработке сигналов», в: Алгоритмы с фиксированной точкой для обратных задач в науке и технике (Х. Х. Баушке, Р. С. Бурачик , П. Л. Комбеттс, В. Эльзер, Д. Р. Люк и Х. Волкович, редакторы), стр. 185–212. Спрингер, Нью-Йорк, 2011 г. [1]

[ 1 ]

[ 2 ]