Successive Approximate Algorithm for Best Approximation from a Polyhedron

AbstractSupposeKis the intersection of a finite number of closed half-spaces {Ki} in a Hilbert spaceX, andx∈X\K. Dykstra's cyclic projections algorithm is a known method to determine an approximate solution of the best approximation ofxfromK, which is denoted byPK(x). Dykstra's algorithm reduces the problem to an iterative scheme which involves computing the best approximation from the individualKi. It is known that the sequence {xj} generated by Dykstra's method converges to the best approximationPK(x). But since it is difficult to find the definite value of an upper bound of the error ‖xj−PK(x)‖, the applicability of the algorithm is restrictive. This paper introduces a new method, called thesuccessive approximate algorithm, by which one can generate a finite sequencex0, x1, …, xkwithxk=PK(x). In addition, the error ‖xj−PK(x)‖ is monotone decreasing and has a definite upper bound easily to be determined. So the new algorithm is very applicable in practice