Projections onto convex sets

In mathematics, projections onto convex sets (POCS), sometimes known as the alternating projection method, is a method to find a point in the intersection of two closed convex sets. It is a very simple algorithm and has been rediscovered many times.[1] The simplest case, when the sets are affine spaces, was analyzed by John von Neumann.[2] [3] The case when the sets are affine spaces is special, since the iterates not only converge to a point in the intersection (assuming the intersection is non-empty) but in fact to the orthogonal projection onto the intersection of the initial iterate. For general closed convex sets, the limit point need not be the projection. Classical work on the case of two closed convex sets shows that the rate of convergence of the iterates is linear. [4] [5] There are now extensions that consider cases when there are more than one set, or when the sets are not convex,[6] or that give faster convergence rates. Analysis of POCS and related methods attempt to show that the algorithm converges (and if so, find the rate of convergence), and whether it converges to the projection of the original point. These questions are largely known for simple cases, but a topic of active research for the extensions. There are also variants of the algorithm, such as Dykstra's projection algorithm. See the references in the further reading section for an overview of the variants, extensions and applications of the POCS method; a good historical background can be found in section III of.[7]

Algorithm

Example on two circles.

The POCS algorithm solves the following problem:

${\displaystyle {\text{find}}\;x\in {\mathcal {R}}^{n}\quad {\text{such that}}\;x\in C\cap D}$

where C and D are closed convex sets.

To use the POCS algorithm, one must know how to project onto the sets C and D separately. The algorithm starts with an arbitrary value for ${\displaystyle x_{0}}$ and then generates the sequence

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

The simplicity of the algorithm explains some of its popularity. If the intersection of C and D is non-empty, then the sequence generated by the algorithm will converge to some point in this intersection.

Unlike Dykstra's projection algorithm, the solution need not be a projection onto the intersection C and D.

Related algorithms

Example of averaged projections variant.

The method of averaged projections is quite similar. For the case of two closed convex sets C and D, it proceeds by

${\displaystyle x_{k+1}={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(x_{k}))}$

It has long been known to converge globally.[8] Furthermore, the method is easy to generalize to more than two sets; some convergence results for this case are in.[9]

The averaged projections method can be reformulated as alternating projections method using a standard trick. Consider the set

${\displaystyle E=\{(x,y):x\in C,\;y\in D\}}$

which is defined in the product space ${\displaystyle {\mathcal {R}}^{n}\times {\mathcal {R}}^{n}}$. Then define another set, also in the product space:

${\displaystyle F=\{(x,y):x\in {\mathcal {R}}^{b},\,y\in {\mathcal {R}}^{n},\;x=y\}.}$

Thus finding ${\displaystyle C\cap D}$ is equivalent to finding ${\displaystyle E\cap F}$.

To find a point in ${\displaystyle E\cap F}$, use the alternating projection method. The projection of a vector ${\displaystyle (x,y)}$ onto the set F is given by ${\displaystyle (x+y,x+y)/2}$. Hence

${\displaystyle (x_{k+1},y_{k+1})={\mathcal {P}}_{F}({\mathcal {P}}_{E}((x_{k},y_{k})))={\mathcal {P}}_{F}(({\mathcal {P}}_{C}x_{k},{\mathcal {P}}_{D}y_{k}))={\frac {1}{2}}({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(y_{k}),({\mathcal {P}}_{C}(x_{k})+{\mathcal {P}}_{D}(y_{k})).}$

References

<references> [1]

1. H.H. Bauschke and J.M. Borwein. On projection algorithms for solving convex feasibility problems. SIAM Review, 38(3):367–426, 1996.
2. J. von Neumann, On rings of operators. Reduction theory, Ann. of Math. 50 (1949) 401–485 (a reprint of lecture notes first distributed in 1933).
3. J. von Neumann. Functional Operators, volume II. Princeton University Press, Princeton, NJ, 1950. Reprint of mimeographed lecture notes first distributed in 1933.
4. L.G. Gubin, B.T. Polyak, and E.V. Raik. The method of projections for finding the common point of convex sets. U.S.S.R. Computational Mathematics and Mathematical Physics, 7:1–24, 1967.
5. H.H. Bauschke and J.M. Borwein. On the convergence of von Neumann's alternating projection algorithm for two sets. Set-Valued Analysis, 1:185–212, 1993.
6. Template:Cite DOI
7. P. L. Combettes, "The foundations of set theoretic estimation," Proceedings of the IEEE, vol. 81, no. 2, pp. 182–208, February 1993. PDF
8. A. Auslender. Methodes Numeriques pour la Resolution des Problems d’Optimisation avec Constraintes. PhD thesis, Faculte des Sciences, Grenoble, 1969
9. Local convergence for alternating and averaged nonconvex projections. A Lewis, R Luke, J Malick, 2007. arXiv