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

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

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

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

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

${\displaystyle \|{\bar {x}}-r\|^{2}\leqslant \|x-r\|^{2},}$ для всех ${\displaystyle 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 x_{k+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].

Для улучшения этой статьи желательно: Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.