A dual approach to constrained interpolation from a convex subset of hilbert space

Many interesting and important problems of best approximation are included in (or can be reduced to) one of the following type: in a Hilbert space X, find the best approximation P-K(x) to any x is an element of X from the set K:= C boolean AND A(-1)(b), where C is a closed convex subset of X, A is a bounded linear operator from X into a finite-dimensional Hilbert space Y, and b is an element of Y: The main point of this paper is to show that P-K(x) is identical to P-c(x + A*y)-the best approximation to a certain perturbation x + A*y of x-from the convex set C or from a certain convex extremal subset C-b OF C. The latter best approximation is generally much easier to compute than the former. Prior to this, the result had been known only in the case of a convex cane or for special data sets associated with a closed convex set. In fact, we give an intrinsic characterization of those pairs of sets C and A(-1)(b) for which this can always be done. Finally, in many cases, the best approximation P-c(x + A*y) can be obtained numerically from existing algorithms or from modifications to existing algorithms. We give such an algorithm and prove its convergence. (C) 1997 Academic Press.