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

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

Примечания

Литература