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

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

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

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

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

АлгоритмПравить

 

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

$\Vert <!--\; \Vert \; -->\stackrel{¯<!--\; ¯\; -->}{x}-<!--\; -\; -->r{\Vert <!--\; \Vert \; -->}^2⩽<!--\; ⩽\; -->\Vert <!--\; \Vert \; -->x-<!--\; -\; -->r{\Vert <!--\; \Vert \; -->}^2,$$\|{\bar {x}}-r\|^{2}\leqslant \|x-r\|^{2},$  для всех $x\in <!--\; \in \; -->C\cap <!--\; \cap \; -->D,$$x\in C\cap D,$ 

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

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

Сначала рассмотрим метод поочерёдного проецирования (типа POCS) (который исследовал первоначально для случая, когда множества $C,D$$C,D$  являются линейными подпространствами, Джон фон Нейман). Метод стартует с точки $x_0=r$$x_{0}=r$  и создаёт последовательность

$x_{k+1}={\mathcal{P}}_C\left({\mathcal{P}}_D(x_k)\right)$$x_{k+1}={\mathcal {P}}_{C}\left({\mathcal {P}}_{D}(x_{k})\right)$ .

Алгоритм Дикстры имеет аналогичный вид, но использует дополнительные переменные. Метод начинает с $x_0=r,p_0=q_0=0$$x_{0}=r,p_{0}=q_{0}=0$  и обновляет переменные по формулам

$y_k={\mathcal{P}}_D(x_k+p_k)$$y_{k}={\mathcal {P}}_{D}(x_{k}+p_{k})$ 

$p_{k+1}=x_k+p_k-<!--\; -\; -->y_k$$p_{k+1}=x_{k}+p_{k}-y_{k}$ 

$x_{k+1}={\mathcal{P}}_C(y_k+q_k)$$x_{k+1}={\mathcal {P}}_{C}(y_{k}+q_{k})$ 

$q_{k+1}=y_k+q_k-<!--\; -\; -->x_{k+1}.$$q_{k+1}=y_{k}+q_{k}-x_{k+1}.$ 

Последовательность точек $(x_k)$$(x_{k})$  сходится к решению исходной задачи. О сходимости и современных модификациях см. статью Комбета и Песке.