The rate of convergence of dykstra's cyclic projections algorithm: The polyhedral case

Abstract

Suppose K is the intersection of a finite number of closed half-spaces in a Hilbert space X. Starting with any point xεX, it is shown that the sequence of iterates {x _n } generated by Dykstra's cyclic projections algorithm satisfies the inequality for all n, where P _K (x) is the nearest point in K to x;, ρ is a constant, and 0 ≤cK is the intersection of just two closed half-spaces, a stronger result is established: the sequence of iterates is either finite or satisfies 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.