Dykstra's projection algorithm

Not to be confused with Dijkstra's algorithm.

Dykstra's algorithm is a method that computes a point in the intersection of convex sets, and is a variant of the alternating projection method (aka Projections onto Convex Sets method). In its simplest form, the method finds a point in the intersection of two convex sets by iteratively projecting onto each of the convex set; it differs from the alternating projection method in that there are intermediate steps. A parallel version of the algorithm was developed by Gaffke and Mathar.

The method is named after R. L. Dykstra who proposed it in the 1980s.

Algorithm

Dykstra's algorithm solves the following problem:

${\text{minimize}}_{x\in {\mathcal {R}}^{n}}\|x-r\|^{2}\quad {\text{subject to}}\;x\in C\cap D$

where $C,D$ are convex sets. This problem is equivalent to finding the projection of $r$ onto the set $C\cap D$, which we denote by ${\mathcal {P}}_{C\cap D}$.

To use Dykstra's algorithm, one must know how to project onto the sets $C$ and $D$ separately.

First, consider the basic alternating projection (aka POCS) method (first studied, in the case when the sets $C,D$ were linear subspaces, by John von Neumann), which initializes $x_{0}=r$ and then generates the sequence

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

Dykstra's algorithm is of a similar form, but uses additional auxiliary variables. Start with $x_{0}=r,p_{0}=q_{0}=0$ and update by

$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}$.

Then the sequence $(x_{k})$ converges to the solution of the original problem. For convergence results and a modern perspective on the literature, see

References

• Boyle, J. P.; Dykstra, R. L. (1986). "A method for finding projections onto the intersection of convex sets in Hilbert spaces". Lecture Notes in Statistics. 37: 28–47.
• Gaffke, N.; Mathar, R. (1989). "A cyclic projection algorithm via duality". Metrika. 36: 29–54.