Interested Article - Алгоритм Дикстры

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

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

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

Алгоритм

Алгоритм Дикстры находит для каждой точки единственную точку в , такую что:

для всех

где являются выпуклыми множествами . Эта задача эквивалентна поиску проекции точки во множество , которую мы обозначим .

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

Сначала рассмотрим метод поочерёдного проецирования (типа POCS ) (который исследовал первоначально для случая, когда множества являются линейными подпространствами, Джон фон Нейман ). Метод стартует с точки и создаёт последовательность

.

Алгоритм Дикстры имеет аналогичный вид, но использует дополнительные переменные. Метод начинает с и обновляет переменные по формулам

Последовательность точек сходится к решению исходной задачи. О сходимости и современных модификациях см. статью Комбета и Песке .

Примечания

  1. , с. 401–485.
  2. , с. 185–212.

Литература

  • P. L. Combettes, J.-C. Pesquet. Proximal splitting methods in signal processing // Fixed-Point Algorithms for Inverse Problems in Science and Engineering / H. H. Bauschke, R. S. Burachik, P. L. Combettes, V. Elser, D. R. Luke, H. Wolkowicz (ред.). — New York: Springer,, 2011.
  • J. von Neumann. On rings of operators. Reduction theory // Ann. of Math.. — 1949. — Вып. 50 . (Репринт лекционных заметок, выпущенных в 1933)
  • Boyle J. P., Dykstra R. L. A method for finding projections onto the intersection of convex sets in Hilbert spaces // Lecture Notes in Statistics. — 1986. — Т. 37 . — С. 28–47 . — ISBN 978-0-387-96419-5 . — doi : .
  • Gaffke N., Mathar R. A cyclic projection algorithm via duality // Metrika. — 1989. — Т. 36 . — С. 29–54 . — doi : .
Источник —

Same as Алгоритм Дикстры