Dykstra's projection algorithm

Dykstra's algorithm is a method that computes a point in the intersection of <a href="/facts/Convex_set/vdAuJRJl">convex sets</a>, and is a variant of the <a href="/facts/Alternating_projection/xeo6T5Ud">alternating projection</a> method (also called the <a href="/facts/Projections_onto_convex_sets/xeo6T5Ud">projections onto convex sets</a> 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 Richard L. Dykstra who proposed it in the 1980s.
A key difference between Dykstra's algorithm and the standard alternating projection method occurs when there is more than one point in the intersection of the two sets. In this case, the alternating projection method gives some arbitrary point in this intersection, whereas Dykstra's algorithm gives a specific point: the projection of r onto the intersection, where r is the initial point used in the algorithm,

Dykstra's projection algorithm open-in-new

Dykstra's projection algorithm