Content deleted Content added
m Task 18 (cosmetic): eval 6 templates: del empty params (4×); |
m Should say two sets |
||
Line 1:
{{confusing|date=April 2018}}
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 set|closed]] [[convex set|convex]] sets. It is a very simple algorithm and has been rediscovered many times.<ref>{{cite journal | last1 = Bauschke | first1 = H.H. | last2 = Borwein | first2 = J.M. | year = 1996 | title = On projection algorithms for solving convex feasibility problems | doi = 10.1137/S0036144593251710 | journal = SIAM Review | volume = 38 | issue = 3| pages = 367–426 | citeseerx = 10.1.1.49.4940 }}</ref> The simplest case, when the sets are [[affine spaces]], was analyzed by [[John von Neumann]].<ref>J. von Neumann,{{cite journal | year = 1949 | title = On rings of operators. Reduction theory | doi = 10.2307/1969463 | journal = Ann. of Math. | volume = 50 | issue = 2| pages = 401–485 | jstor = 1969463 | last1 = Neumann | first1 = John Von }} (a reprint of lecture notes first distributed in 1933)</ref><ref>J. von Neumann. Functional Operators, volume II. Princeton University Press, Princeton, NJ, 1950. Reprint of mimeographed lecture notes first distributed in 1933.</ref> 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 to the orthogonal projection of the point onto the intersection. 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.<ref>{{cite journal | last1 = Gubin | first1 = L.G. | last2 = Polyak | first2 = B.T. | last3 = Raik | first3 = E.V. | year = 1967 | title = The method of projections for finding the common point of convex sets | journal = U.S.S.R. Computational Mathematics and Mathematical Physics | volume = 7 | issue = 6| pages = 1–24 | doi=10.1016/0041-5553(67)90113-9}}</ref><ref>{{cite journal | last1 = Bauschke | first1 = H.H. | last2 = Borwein | first2 = J.M. | year = 1993 | title = On the convergence of von Neumann's alternating projection algorithm for two sets | journal = Set-Valued Analysis | volume = 1 | issue = 2| pages = 185–212 | doi=10.1007/bf01027691}}</ref>
There are now extensions that consider cases when there are more than
== Algorithm ==
|