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

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

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

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