Алгоритм Дикстры
Алгоритм Дикстры — это метод нахождения точки из пересечения выпуклых множеств. Является вариантом метода поочерёдного проецирования, известного также как метод проецирования в выпуклые множества. В простейшем варианте метод находит точку из пересечения двух выпуклых множеств путём итеративного проецирования в каждое из них. Метод отличается от метода поочерёдного проецирования наличием промежуточных шагов. Параллельную версия алгоритма разработали Гафке и Матар.
Метод назван именем Ричарда Л. Дикстры, предложившего его в 1980-х годах.
Ключевое отличие между алгоритмом Дикстры и методом стандартного поочерёдного проецирования возникает в случае, когда пересечение двух множеств состоит из более чем одной точки. В этом случае метод поочерёдного проецирования даёт некоторую произвольную точку в пересечении, в то время как алгоритм Дикстры даёт вполне определённую точку — проекцию точки r в пересечение, где r — данная алгоритму начальная точка.
Алгоритм
![](http://upload.wikimedia.org/wikipedia/commons/thumb/0/02/Dykstra_algorithm.svg/400px-Dykstra_algorithm.svg.png)
Алгоритм Дикстры находит для каждой точки единственную точку в , такую что:
- для всех
где являются выпуклыми множествами. Эта задача эквивалентна поиску проекции точки во множество , которую мы обозначим .
Чтобы использовать алгоритм Дикстры, нужно знать, каким образом находить проекцию точки во множества и по отдельности.
Сначала рассмотрим метод поочерёдного проецирования (типа POCS) (который исследовал первоначально для случая, когда множества являются линейными подпространствами, Джон фон Нейман[1]). Метод стартует с точки и создаёт последовательность
- .
Алгоритм Дикстры имеет аналогичный вид, но использует дополнительные переменные. Метод начинает с и обновляет переменные по формулам
Последовательность точек сходится к решению исходной задачи. О сходимости и современных модификациях см. статью Комбета и Песке[2].
Примечания
- ↑ von Neumann, 1949, с. 401–485.
- ↑ Combettes, Pesquet, 2011, с. 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:10.1007/978-1-4613-9940-7_3.
- Gaffke N., Mathar R. A cyclic projection algorithm via duality // Metrika. — 1989. — Т. 36. — С. 29–54. — doi:10.1007/bf02614077.
Для улучшения этой статьи желательно:
|