A convergence analysis of Dykstra's algorithm for polyhedral sets

摘要

Let H be a nonempty closed convex set in a Hilbert space X determined by the intersection of a finite number of closed half spaces. It is well known that given an x(0) is an element of X, Dykstra's algorithm applied to this collection of closed half spaces generates a sequence of iterates that converge to P-H(x(0)), the orthogonal projection of x(0) onto H. The iterates, however, do not necessarily lie in H. We propose a combined Dykstra conjugate-gradient method such that, given an epsilon > 0, the algorithm computes an x is an element of H with parallel tox - P-H(x(0))parallel to < ε. Moreover, for each iterate x(m) of Dykstra's algorithm we calculate a bound for &PAR;x(m) - P-H(x(0))&PAR; that approaches zero as m tends to infinity. Applications are made to computing bounds for &PAR;x(m) - P-H(x(0))&PAR; where H is a polyhedral cone. Numerical results are presented from a sample isotone regression problem. [References: 14]