THE RATE OF CONVERGENCE OF DYKSTRAS CYCLIC PROJECTIONS ALGORITHM - THE POLYHEDRAL CASE

Suppose K is the intersection of a finite number of closed half-spaces in a Hilbert space X. Starting with any point x E X, it is shown that the sequence of iterates {x(n)} generated by Dykstra's cyclic projections algorithm satisfies the inequality \\x(n) - P(K)(x)\\ less-than-or-equal-to rho(c)n for all n, where P(K)(x) is the nearest point in K to x, p is a constant, and 0 less-than-or-equal-to c < 1. In the case when K is the intersection of just two closed half-spaces, a stronger result is established: the sequence of iterates is either finite or satisfies \\x(n) - P(K)(x)\\ less-than-or-equal-to c(n-1)\\x - p(K)(x)\\ for all n, where c is the cosine of the angle between the two functionals which define the half-spaces. Moreover, the constant c is the best possible. Applications are made to isotone and convex regression, and linear and quadratic programming.