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

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

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

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

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

Алгоритм

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

$\|{\bar {x}}-r\|^{2}\leqslant \|x-r\|^{2},$ для всех $x\in C\cap D,$

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

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

Сначала рассмотрим метод поочерёдного проецирования (типа POCS) (который исследовал первоначально для случая, когда множества $C,D$ являются линейными подпространствами, Джон фон Нейман). Метод стартует с точки $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})$ сходится к решению исходной задачи. О сходимости и современных модификациях см. статью Комбета и Писке.