Best Approximation from the Intersection of a Closed Convex Set and a Polyhedron in Hilbert Space, Weak Slater Conditions, and the Strong Conical Hull Intersection Property
Authors:
- Frank DeutschFDFrank Deutsch
- Wu LiWLWu Li
- Joseph D. WardJWJoseph D. Ward
- 1 January 1999
- journal article
- Published by Society for Industrial & Applied Mathematics (SIAM) in SIAM Journal on Optimization
- Vol. 10 (1) , 252-268
Abstract
Let X be a (real) Hilbert space, C be a closed convex subset, and $H_i =\{x\in X\mid \la x, h_i\ra \le b_i\} \quad (i=1,2,..., m)$ be a finite collection of half-spaces. Under the assumption that $K:=C\cap (\cap_1^mH_i)$ is not empty, the problem of characterizing the best approximation from K to any $x\in X$ is considered. The "strong conical hull intersection property" (strong CHIP), which was introduced by us in 1997, is shown to be both necessary and sufficient for the following "perturbation property" to hold: for each $x\in X$, an element $x_0\in K$ satisfies $x_0=P_K(x)$ if and only if $x_0=P_C(x-\sum_1^m\lambda_ih_i)$ for some scalars $\lambda_i\ge 0$ with $\lambda_i[\la x_0, h_i\ra -b_i]=0$ for each i. Here $P_D(z)$ denotes the unique best approximation from D to z. In other words, determining the best approximation from the set K to any point is equivalent to the (generally easier) problem of determining the best approximation from the set C to a perturbation of that point. Moreover, even when the strong CHIP does not hold, the perturbation property still holds, except now C must be replaced by a certain convex extremal subset of C. We also show that the strong CHIP is weaker than any of the weak Slater conditions that one can naturally impose on the sets in question. These results generalize the main results of our 1997 paper [J. Approx. Theory, 90, pp. 385--444] and hence those of several other papers as well.
Keywords
This publication has 17 references indexed in Scilit:
- Strong conical hull intersection property, bounded linear regularity, Jameson's property (G), and error bounds in convex optimizationMathematical Programming, 1999
- Fenchel Duality and the Strong Conical Hull Intersection PropertyJournal of Optimization Theory and Applications, 1999
- A Dual Approach to Constrained Interpolationfrom a Convex Subset of Hilbert SpaceJournal of Approximation Theory, 1997
- Constrained Best Approximation in Hilbert Space III. Applications to $n$-Convex FunctionsConstructive Approximation, 1996
- Convex Analysis and Minimization Algorithms I1993
- Gauss-seidel method for least-distance problemsJournal of Optimization Theory and Applications, 1992
- Partially finite convex programming, Part I: Quasi relative interiors and duality theoryMathematical Programming, 1992
- Constrained best approximation in Hilbert spaceConstructive Approximation, 1990
- ConstrainedL p approximationConstructive Approximation, 1985
- On “best” interpolationJournal of Approximation Theory, 1976