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

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

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

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

Алгоритм

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

{ displaystyle | { bar {x}} - r | ^ {2} leq | x-r | ^ {2}, { text {для всех}} 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 х_ {к + 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]

Цитаты

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

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

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

[1]

[2]

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

Алгоритм

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

Цитаты