ERROR BOUNDS FOR ABSTRACT LINEAR INEQUALITY SYSTEMS^{∗}

KUNG FU NG^{†} AND WEI HONG YANG^{‡}

Abstract. In this paper we study error bounds of abstract linear inequality system (A, C, b) : Ax ⩽ b, where A is a bounded linear operator from a Banach space X to a Banach space Y partially ordered by a closed convex cone C. We also give some general results on the existence of error bounds for a convex function F; we show in particular that F has an error bound if and only if the directional derivative of the distance function (to the solution set S) at each boundary point of S along any non-tangential direction is bounded by that of F. As an application we prove that if C is a polyhedral cone then the system (A, C, b) has an error bound. When Y is a Hilbert space our results can be expressed in terms of the angles between Ax − b − P_{−C}(Ax − b) and Im(A), or in terms of the angles between Im(A) and the non-vertex supporting hyperplanes of C. In the case when X = ℝ^{n} and C is an “ice-cream” cone, we identify exactly when (A, C, b) has an error bound.

Key words. error bound, abstract linear inequality system, polyhedral cone, angles between subspaces, “ice-cream” cone

AMS subject classifications. 90C31,90C25,49J52

1. Introduction and Preliminaries. For convenience, we first set notations that would be used throughout the paper. X, Y denote Banach spaces, C a closed convex cone in Y introducing a partial order in the usual way: for y_{1}, y_{2} ∈ Y

y_{1} ⩽ y_{2} if and only if y_{2} − y_{1} ∈ C.

F denotes a continuous convex function on X and S := {x ∈ X : F (x) ⩽ 0}. A denotes a bounded linear operator on X into Y, and b denotes a vector in Y. For A, b as above we have a continuous convex function φ_{A,b} (henceforth denoted by φ_{b} if no need of emphasis for A):

φ_{b}(x) = dist(Ax − b, −C), ∀x ∈ X; (1.1)

let S_{C}^{b} denote the set of all x satisfying φ_{b}(x) ⩽ 0, that is,

S_{C}^{b} = {x : Ax − b ⩽ 0}. (1.2)

We will use (A, C, b) to denote the abstract inequality system

Ax − b ⩽ 0. (1.3)

It is said to have an error bound (and τ is called an error bound for the system) if there exists τ > 0 such that

dist(x, S_{C}^{b}) ⩽ τφ_{b}(x) ∀x ∈ X;

∗This research was supported by a direct grant(CUHK) and an Earmarked grant from the Research Grant Council of Hong Kong

†Department of Mathematics, The Chinese University of Hong Kong, Shatin, New Territory, Hong Kong (kfng@math.cuhk.edu.hk)

‡Department of Mathematics, The Chinese University of Hong Kong, Shatin, New Territory, Hong Kong (whyang@math.cuhk.edu.hk)

this is clearly the case if and only if φ_{b} has an error bound [9, 12, 10].

V will denote a nonempty closed convex set in X. Let x̄ ∈ V. If there exists a continuous linear functional f on X with norm 1 such that

f(x̄) = max{f(x) : x ∈ V }

then x̄ is called a support point of V and f is called a (normalized) supporting functional of V at x̄. The set of all support points of V will be denoted by supp(v).

Given a point x in the topological boundary bd(v) of V, h ∈ X\{0} is called a normal (direction) of V at x if dist(x + h, V) = ∥h∥; in view of the Variational Inequality, this is the case if and only if

dist(x + th, V) = t∥h∥, ∀t ∈ [0, 1]. (1.4)

More generally, for γ ∈ (0, 1], h ∈ X is called a γ-normal of V at x if

dist(x + th, V) ⩾ tγ∥h∥, ∀t ∈ [0, 1]. (1.5)

The set of all γ-normals of V at x will be denoted by N_{V} (x, γ). Note that sometimes N_{V} (x) has been used to denote N_{V} (x, 1), and that N_{V}^{1} (x) denotes the set of all unit vectors in N_{V} (x). Thus N_{V} (x, 1) equals to the cone generated by N_{V}^{1} (x) considered in [9]. Another closely related concept is on the so-called Bishop-Phelps cone P (f, γ) which is defined by

P (f, γ) = {h ∈ X : γ∥h∥ ⩽ f(h)},

where f is a continuous linear functional on X with norm 1. P (f, γ) is nonempty whenever 0 < γ < 1 ( P (f, 1) is also nonempty if X is assumed reflexive); note also that

P (f, γ) = ∩_{0<γ′<γ}P (f, γ′). (1.6)

For γ ∈ (0, 1] and x ∈ supp(v), let NV^{′} (x, γ) denote the union

∪_{f}P (f, γ) (1.7)

where f runs over all normalized continuous linear functionals on X supporting V at x.

Lemma 1.1 Let x ∈ supp(v) and γ ∈ (0, 1]. Then

NV^{′} (x, γ) ⊆ N_{V} (x, γ). (1.8)

Proof. Let 0 ≠ h ∈ NV^{′} (x, γ): there exists f ∈ X^{∗} with ∥f∥ = 1 such that f supports V at x and γ∥h∥ ⩽ f(h). Then, for any v ∈ V and t > 0,

∥x + th − v∥ ⩾ f(x + th − v) ⩾ f(th) ⩾ tγ∥h∥,

showing that dist(x+th, V) ⩾ tγ∥h∥, and hence that (1.5) holds and h ∈ N_{V} (x, γ). □

Recall that the tangent cone T_{V} (x) of V at x is defined by

T_{V} (x) = \{h ∈ X : lim_{t→0+} \frac{dist(x + th, V)}{t} = 0\}. (1.9)

Error Bound of Abstract Linear Inequality System 3

Lemma 1.2 Let x ∈ bd(v) and γ ∈ (0, 1]. Then N_{V} (x, γ)\{0} ⊆ X\T_{V} (x). (1.10)

Proof. Let 0 ≠ h ∈ N_{V} (x, γ); then (1.5) holds. It follows that

\frac{dist(x + th, V)}{t} ⩾ γ∥h∥ > 0, ∀t ∈ (0, 1]

and hence h ∉ T_{V} (x) by (1.9). □

We have observed that N_{V} (x, 1) is simply the set of all normals to V at x, and has played an important role in the error bound problems (cf. [9, 12, 10]). In attempting to generalize this study to the general setting of Banach spaces (in place of finite dimensional or reflexive spaces ), one must bear in mind that N_{V} (x, 1) can very well be empty for each x ∈ supp(v). The following result shows the nonemptiness of N_{V} (x, γ) for many x if γ < 1. Our proof is based on a standard Banach space theory technique (cf. [13, Proposition 3.20]). Proposition 1.3 Let 0 < γ < 1, and let y ∈ X\V. Then there exists x ∈ supp(v) such that

y − x ∈ NV^{′} (x, γ) (1.11)

(in particular y − x ∈ N_{V} (x, γ) and y − x ∉ T_{V} (x)). Moreover, if X is reflexive then the result also holds for γ = 1. Proof. Write d for the distance of y to V. Take ϵ > 0 such that

γ ⩽ \frac{d − \sqrt{ϵ}(d + ϵ + \sqrt{ϵ})}{(1 + ϵ)(d + ϵ + \sqrt{ϵ})}. (1.12)

By the Separation Theorem, take x_{0}^{∗} ∈ X^{∗} of norm 1 such that sup⟨x_{0}^{∗}, V ⟩ = inf⟨x_{0}^{∗}, y + dB⟩ = ⟨x_{0}^{∗}, y⟩ − d, (1.13) where B denotes the closed unit ball in X. Pick x_{0} ∈ V such that ∥x_{0} − y∥ ⩽ d + ϵ. (1.14) Then, (1.13) and (1.14) imply that, for each v ∈ V,

⟨x_{0}^{∗}, v⟩ ⩽ ⟨x_{0}^{∗}, y⟩ − d ⩽ ∥x_{0}^{∗}∥∥y − x_{0}∥ + ⟨x_{0}^{∗}, x_{0}⟩ − d ⩽ ϵ + ⟨x_{0}^{∗}, x_{0}⟩,

showing that x_{0}^{∗} is in the ϵ-subdifferential ∂_{ϵ}f(x_{0}) of f at x_{0}, where f denotes the indicator function of V (defined by f(x) = 0 or +∞ according to x ∈ V or x ∈ X\V). By the Bronstead-Rockafellar Theorem (cf.[13]), there exist x_{ϵ} ∈ dom f = V and (1.15) x_{ϵ}^{∗} ∈ ∂f(x_{ϵ}) (so sup⟨x_{ϵ}^{∗}, V ⟩) = ⟨x_{ϵ}^{∗}, x_{ϵ}⟩ and x_{ϵ} ∈ supp(v)) such that ∥x_{ϵ} − x_{0}∥ ⩽ \sqrt{ϵ} , ∥x_{ϵ}^{∗} − x_{0}^{∗}∥ ⩽ \sqrt{ϵ}. Then one has from (1.14) that ∥x_{ϵ} − y∥ ⩽ d + ϵ + \sqrt{ϵ} (1.16) and it follows from (1.13) that,

⟨x_{ϵ}^{∗}, x_{ϵ} − y⟩ = ⟨x_{ϵ}^{∗} − x_{0}^{∗}, x_{ϵ} − y⟩ + ⟨x_{0}^{∗}, x_{ϵ} − y⟩ ⩽ \sqrt{ϵ}(d + ϵ + \sqrt{ϵ}) − d;

therefore we have, by (1.16), that

⟨\frac{x_{ϵ}^{∗}}{∥x_{ϵ}^{∗}∥}, y − x_{ϵ}⟩ ⩾ \frac{d − \sqrt{ϵ}(d + ϵ + \sqrt{ϵ})}{1 + ϵ}
⩾ \frac{d − \sqrt{ϵ}(d + ϵ + \sqrt{ϵ})}{1 + ϵ} \frac{∥x_{ϵ} − y∥}{d + ϵ + \sqrt{ϵ}}
⩾ γ∥x_{ϵ} − y∥,

showing that y − x_{ϵ} ∈ NV^{′} (x_{ϵ}, γ). Together with Lemmas 1.1 and 1.2, the first assertion of Proposition 1.3 is proved. Moreover, suppose that X is reflexive. Then there exists x_{0} ∈ V satisfying (1.14) with ϵ = 0; hence the supremum in (1.13) is attained at x_{0} and the whole argument is then seen to be valid with γ = 1, ϵ = 0. □

2. Error Bounds for Convex Functions. We continue to use the notations introduced in Section 1; in particular, F is a continuous convex function on X and S = {x : F (x) ⩽ 0}. To avoid the triviality, we assume throughout that ∅ ≠ S ≠ X. Suppose that G is another continuous convex function such that G(x) ⩽ 0 if and only if F (x) ⩽ 0:

S = {x : F (x) ⩽ 0} = {x : G(x) ⩽ 0} (2.1)

(e.g. the function x → dist(x, S) has this property of G). Recall that the directional derivative F′(x; h) = lim_{t→0+} \frac{F (x+th)−F (x)}{t} always exists for x, h ∈ X; similarly for G. We begin with a general result for the existence of error bounds for F.

Theorem 2.1 Assume (2.1); let γ ∈ (0, 1) and M > 0 be such that, for each x ∈

supp(S) and h ∈ NS^{′}(x, γ),

G′(x; h) ⩽ M F′(x; h). (2.2)

Suppose that G has an error bound: there exists τ > 0 such that

dist(x, S) ⩽ τ[G(x)]_{+}, ∀x ∈ X. (2.3)

Then F also has an error bound:

dist(x, S) ⩽ γ^{−1}τM[F (x)]_{+}, ∀x ∈ X. (2.4)

Moreover, if X is reflexive then the result remains true for γ = 1.

Proof. Let y ∈ X\S. By Proposition 1.3 (which is valid for γ ∈ (0, 1), and also for γ = 1 if X is reflexive), take x ∈ supp(S) such that h := y − x ∈ NS^{′}(x, γ); thus by (1.5) and (1.8) one has for each t ∈ (0, 1] that

dist(x + th, S) ⩾ tγ∥h∥ ⩾ tγdist(x + h, S) > 0, (2.5) showing in particular that x + th ∉ S. It follows from (2.3) that

τG(x + th) ⩾ dist(x + th, S) ⩾ tγdist(x + h, S),

which implies that τG′(x; h) ⩾ γdist(x + th, S) > 0 because G(x) = 0. Since F is convex and F (x) = 0, it follows from (2.2) that

MτF (x + h) ⩾ MτF′(x; h) ⩾ τG′(x; h) ⩾ γdist(x + h, S),

that is MτF (y) ⩾ γdist(y, S) valid for each y ∈ X\S. Therefore (2.4) is seen to hold. □

Let D be the convex function on X defined by

D(x) = dist(x, S), ∀x ∈ X. (2.6)

It is trivial to see that D has an error bound τ = 1. By applying the preceding theorem to G = D, we have the following generalization of a theorem of Lewis and Pang [9].

Theorem 2.2 Let τ > 0 and γ ∈ (0, 1). Then one has (i) ⇒ (ii) ⇒ (iii) ⇒ (iv) ⇒ (i^{∗}):

(i) γτ is an error bound for F.
(ii) D′(x; h) ⩽ γτF′(x; h) for each x ∈ supp(S) and h ∈ X\T_{S}(x).
(iii) D′(x; h) ⩽ γτF′(x; h) for each x ∈ supp(S) and h ∈ N_{S}(x, γ).
(iv) D′(x; h) ⩽ γτF′(x; h) for each x ∈ supp(S) and h ∈ NS^{′}(x, γ).
(i^{∗}) τ is an error bound for F.

Moreover the result remains true for γ = 1 if X is reflexive.

Proof. By Theorem 2.1 (applied to γτ, 1 in place of M, τ), (iv) ⇒ (i^{∗}). In view of Lemmas 1.1 and 1.2, it is trivial that (ii) ⇒ (iii) ⇒ (iv). To prove (i) ⇒ (ii), let x ∈ bd(S) and h ∈ X\T_{S}(x). Then D(x + th) > 0 and so x + th ∉ S for all t > 0. By (i), one has

D(x + th) ⩽ γτ[F (x + th)]_{+} = γτF (x + th);

since D(x) = 0 = F (x), it follows from taking limits (after dividing by t) that

D′(x; h) ⩽ γτF′(x; h).

□

Remark 2.1 For γ = 1, it is clear from (1.4) that D′(x; h) = ∥h∥. Thus the implications (i) ⇒ (iii) ⇒ (i^{∗}) provide an extension of [9, Theorem 1], where they considered the case when X = ℝ^{n}.

Corollary 2.3 τ is an error bound for F if and only if

(ii^{∗}) D′(x; h) ⩽ τF′(x; h) for each x ∈ supp(S) and h ∈ X\T_{S}(x).

Proof. Apply Theorem 2.2 and let γ → 1. □

6 Kung Fu Ng and Wei Hong Yang

3. Error Bounds for Abstract Linear Inequality Systems. We continue to use the notations set in Section 1. In particular A is a bounded linear operator from X into Y which is partially ordered by a closed convex cone C. Let b ∈ Y; let φ_{b}, S_{C}^{b} and (A, C, b) be defined by (1.1),(1.2) and (1.3). Note that, φ_{b}(x) = g(Ax − b), ∀x ∈ X, (3.1) where g : Y → ℝ is defined by g(y) = dist(y, −C). (3.2) By the Chain Rules [3, Theorem 2.3.10], φ′_{b}(x; h) = g′(Ax − b; Ah) , ∂φ_{b}(x) = {A^{∗}y^{∗} : y^{∗} ∈ ∂g(Ax − b)}. (3.3) Let M := Im(A) and, for any y^{∗} ∈ Y^{∗}, let ∥y^{∗}∥_{M} denote the norm of the restriction y^{∗}|_{M} of y^{∗} to M:

∥y^{∗}∥_{M} := sup{|⟨y^{∗}, y⟩| : y ∈ M, ∥y∥ = 1}.

Here and throughout we assume that A ≠ 0 and so that M ≠ {0}. Lemma 3.1 Let M := Im(A), y^{∗} ∈ Y^{∗}, and let A^{∗}y^{∗} ∈ X^{∗} be defined by

(A^{∗}y^{∗})(x) = y^{∗}(Ax), ∀x ∈ X.

Then ∥A^{∗}y^{∗}∥ ⩽ ∥A∥∥y^{∗}∥_{M}. (3.4) If Im(A) is assumed closed then there exists λ > 0 such that ∥y^{∗}∥_{M} ⩽ λ∥A^{∗}y^{∗}∥. (3.5)

Proof. The proof for (3.4) is straightforward. To prove (3.5), we let λ := sup{dist(0, A^{−1}y) : y ∈ Im(A), ∥y∥ = 1}. (3.6) Since Im(A) is closed, it follows from the Open Mapping Theorem that λ < +∞. By (3.6), for each y ∈ Im(A) with ∥y∥ < 1 there exists z with ∥z∥ ⩽ λ such that Az = y. Then

|y^{∗}(y)| = |A^{∗}y^{∗}(z)| ⩽ λ∥A^{∗}y^{∗}∥,

which implies (3.5). □ Theorem 3.2 Suppose that S_{C}^{b} is nonempty and that M = Im(A) is closed. Then (A, C, b) has an error bound if and only if

inf_{\begin{matrix}x∈X\S_{C}^{b} \\ η∈∂g(Ax−b) \end{matrix}} ∥η∥_{M} > 0. (3.7)

Proof. Clearly φ_{b} is continuous and convex, and S_{C}^{b} = {x ∈ X : φ_{b}(x) ⩽ 0}. Therefore (A, C, b) has an error bound if and only if so does φ_{b}. By [5, Theorem 2.2] and (3.3), this is the case if and only if

inf_{\begin{matrix}x∈X\S_{C}^{b} \\ y^{∗}∈∂g(Ax−b) \end{matrix}} ∥A^{∗}y^{∗}∥ > 0. (3.8)

Take λ > 0 as in (3.6). Then, by (3.4) and (3.5), one has

λ^{−1} inf_{\begin{matrix}x∈X\S_{C}^{b} \\ y^{∗}∈∂g(Ax−b) \end{matrix}} ∥y^{∗}∥_{M} ⩽ inf_{\begin{matrix}x∈X\S_{C}^{b} \\ y^{∗}∈∂g(Ax−b) \end{matrix}} ∥A^{∗}y^{∗}∥ ⩽ inf_{\begin{matrix}x∈X\S_{C}^{b} \\ y^{∗}∈∂g(Ax−b) \end{matrix}} ∥A∥∥y^{∗}∥_{M},

showing that (3.7) and (3.8) are equivalent. □

The following result shows that, when Im(A) is closed, for the consideration of the existence of error bounds of (A, C, b) one may replace X, A by Im(A), I_{A} respectively, where I_{A} denotes the identity operator from Im(A) into Y.

Corollary 3.3 Suppose that Im(A) is closed in Y. Then (A, C, b) has an error bound if and only if (I_{A}, C, b) has an error bound.

Proof. Let M := Im(A). Then M = Im(I_{A}). Note also that the solution set for (I_{A}, C, b) equals to M ∩ (b − C). Thus, applying Theorem 3.2 to (I_{A}, C, b), one has that (I_{A}, C, b) has an error bound if and only if

inf_{\begin{matrix}y∈M\(b−C) \\ η∈∂g(I_{A}y−b) \end{matrix}} ∥η∥_{M} > 0,

which is seen to be exactly (3.7) by writing Ax for y in M. □

The next result deals with the special case when C is a polyhedral cone: there exist f_{1}, f_{2}, ⋯, f_{r} ∈ Y^{∗} such that

−C = {y ∈ Y : f_{i}(y) ⩽ 0 ∀i = 1, 2, ⋯, r}. (3.9)

That is

−C = {y ∈ Y : ψ(y) ⩽ 0},

where ψ : y → R is the max-function defined by

ψ(y) = max f_{i}(y), ∀y ∈ Y. (3.10)

Further define Ψ : X → R by

Ψ(x) = ψ(Ax − b), ∀x ∈ X. (3.11)

Thus

x ∈ S_{C}^{b} ⟺ Ψ(x) ⩽ 0 ⟺ (A^{∗}f_{i})(x) − f_{i}(b) ⩽ 0 ∀i = 1, 2, ⋯, r. (3.12)

The following theorem extends a result of Robinson [14, page 759-760] from the finite dimensional case to general Banach spaces.

Theorem 3.4 Suppose that C is a polyhedral cone in Y. Then the system (A, C, b) has an error bound for any b ∈ Y.

Proof. By Ioffe’s Theorem [8], there exists τ > 0 such that

dist(x, S_{C}^{b}) ⩽ τ[Ψ(x)]_{+}, x ∈ X. (3.13)

By Corollary 2.3, one has

D′(x; h) ⩽ τΨ′(x; h), h ∈ X\T_{S_{C}^{b}} (x), (3.14)

where D : X → R is defined by D(x) = dist(x, S_{C}^{b}). Letting F (x) := dist(Ax−b, −C) and ξ := max{∥f_{1}∥, ⋯, ∥f_{r}∥}, we claim that

Ψ′(x; h) ⩽ ξF′(x; h), ∀x ∈ bd(S_{C}^{b}) , ∀h ∈ X\T_{S_{C}^{b}} (x). (3.15)

By the Chain Rules and (3.11), Ψ′(x; h) = ψ′(Ax − b; Ah) and similarly F′(x; h) = g′(Ax − b; Ah) where g : Y → R is defined by

g(y) = dist(y, −C), ∀y ∈ Y.

hence (3.15) holds if and only if

ψ′(Ax − b; Ah) ⩽ ξg′(Ax − b; Ah), ∀x ∈ bd(S_{C}^{b}) , ∀h ∈ X\T_{S_{C}^{b}} (x). (3.16)

Thus (3.15) follows from

ψ′(y; k) ⩽ ξg′(y; k), ∀y ∈ bd(−C) , ∀k ∈ Y, (3.17)

which in turn is seen to hold because ψ(y) = g(y) for y ∈ bd(−C) and

f_{i}(y + tk) ⩽ f_{i}(y + tk − w) ⩽ ξ∥y + tk − w∥, ∀w ∈ (−C),

showing that ψ(y + tk) ⩽ ξg(y + tk) for any k ∈ Y. Therefore (3.15) is established. Combining (3.14) and (3.15) it follows from Corollary 2.3 that

dist(x, S_{C}^{b}) ⩽ τξ[F (x)]_{+}, ∀x ∈ X.

□

4. Angle Conditions. The aim of this section is to interpret the condition given in (3.7) by virtue of an angle condition and hence to seek further consequence geometrically. The angle condition given in Theorem 4.3 is more intuitive, and sometimes easier to apply (see Example 4.2 and Corollary 4.5, for example). While we retain all the notation introduced in the preceding section, we will assume throughout that M := Im(A) is closed and that the norm for Y is induced by an inner product ⟨·, ·⟩, that is, Y is a Hilbert space. M^{⊥} denotes the orthogonal complement of M. For any y, z ∈ Y \\{0\} we define ∡(y, z) ∈ [0, \frac{π}{2} ] by

∡(y, z) = arccos\{\frac{|⟨y, z⟩|}{∥y∥∥z∥}\}. (4.1)

If Z ≠ {0} is a closed vector subspace of Y, we also define

∡(y, Z) = min{∡(y, z) : z ∈ Z, ∥z∥ = 1} (4.2)

i.e.

cos ∡(y, Z) = max\{⟨\frac{y}{∥y∥}, z⟩ : z ∈ Z, ∥z∥ = 1\}. (4.3)

We recall that, for y ∈ Y,

∥y∥_{Z} := sup_{\begin{matrix}z∈Z \\ ∥z∥=1 \end{matrix}}\{⟨y, z⟩\} = max_{\begin{matrix}z∈Z \\ ∥z∥=1 \end{matrix}}\{⟨y, z⟩\}

Lemma 4.1 Let y ∈ Y with ∥y∥ = 1; let Z ≠ {0} be a closed vector subspace of Y and let P_{Z} denote the orthogonal projection of Y onto Z. Then

∥y∥_{Z} = ∥P_{Z}(y)∥ = cos ∡(y, Z). (4.4)

Proof. Write y = p + q with p ∈ Z and q ∈ Z^{⊥}, the orthogonal complement of Z. Then

∥y∥_{Z} = max{⟨p + q, z⟩ : z ∈ Z, ∥z∥ = 1}
= max{⟨p, z⟩ : z ∈ Z, ∥z∥ = 1}
= ∥p∥,

since p ∈ Z and because of the Cauchy-Schwarz inequality. Combining this with (4.3), (4.4) is seen to hold. □

Recall that g : Y → ℝ is defined by g(y) = dist(y, −C) for each y ∈ Y, and that P_{−C}(y) denotes the projection of y to −C.

Lemma 4.2 ∂g(y) = \{\frac{y−P_{−C}(y)}{∥y−P_{−C}(y)∥}\} for each y ∈ Y \(−C).

The proof given in [3, Proposition 2.5.4] can easily be adopted for our infinite dimensional setting (cf. [1, page 522-526]).

Theorem 4.3 Let b ∈ Y. The system (A, C, b) has an error bound if and only if

sup_{x∈X\S_{C}^{b}} ∡(Ax − b − P_{−C}(Ax − b), Im(A)) < \frac{π}{2} . (4.5)

In particular, if −b + C ⊆ Im(A) (e.g. A is onto Y), then the system (A, C, b) has an error bound.

Proof. Let M := Im(A). By Lemma 4.2 and (4.3) we have

inf_{\begin{matrix}x∈X\S_{C}^{b} \\ η∈∂g(Ax−b) \end{matrix}} \{∥η∥_{M}\} = inf_{x∈X\S_{C}^{b}} ∥\frac{Ax − b − P_{−C}(Ax − b)}{∥Ax − b − P_{−C}(Ax − b)∥}∥_{M}

= inf_{x∈X\S_{C}^{b}} cos ∡(Ax − b − P_{−C}(Ax − b), M)
= cos ( sup_{x∈X\S_{C}^{b}} ∡(Ax − b − P_{−C}(Ax − b), M )),

which is positive if and only if (4.5) holds. Thus Theorem 4.3 follows from Theorem 3.2. □

Theorem 4.4 Suppose that for some b ∈ Y,

sup_{x∈X\S_{C}^{b}} ∡(Ax − b − P_{−C}(Ax − b), Im(A)) < \frac{π}{2} . (4.6)

Then

sup_{x∈X\S_{C}^{0}} ∡(Ax − P_{−C}(Ax), Im(A)) < \frac{π}{2} .

Proof. Let M := Im(A). Assume that there exists a sequence {x_{n}} with Ax_{n} ∉ −C for each n such that

lim_{n→∞} ∡(Ax_{n} − P_{−C}(Ax_{n}), M) = \frac{π}{2} .

Assuming without loss of generality that Ax_{n} − P_{−C}(Ax_{n}) is of norm 1, it follows from (4.4) that

lim_{n→∞} cos ∡(Ax_{n} − P_{−C}(Ax_{n}), M)

= lim_{n→∞} ∥P_{M}(Ax_{n} − P_{−C}(Ax_{n}))∥
= 0.

Let U := {y ∈ Y |∥y∥ ⩽ 1/4}. Then for each y ∈ U, (Ax_{n} − y) ∉ −C because Ax_{n} is of distance 1 to −C. Let η_{n}(y) := Ax_{n} − y − P_{−C}(Ax_{n} − y) and

ϕ_{n}(y) := \frac{∥P_{M}(η_{n}(y))∥}{∥η_{n}(y)∥}, ∀y ∈ U.

Obviously |η_{n}(y)−η_{n}(y′)| ⩽ 2∥y −y′∥; letting y′ = 0, it follows from ∥η_{n}(0)∥ = 1 that ∥η_{n}(y)∥ ⩾ 1/2 for each y ∈ U. Then ϕ_{n}(y) is a sequence of equicontinuous functions of y from U to R. Let {ϵ_{n}} be a sequence of real numbers decreasing to 0. For each n, we can therefore find a large enough integer k_{n} such that \frac{b}{k_{n}} ∈ U and

(4.7) | arccos ϕ_{m}(\frac{b}{k_{n}}) − arccos ϕ_{m}(0)| ⩽ ϵ_{n}, for each m ∈ N.

Then, by Lemma 4.1, one has

lim_{n→∞} ∡(A(k_{n}x_{n}) − b − P_{−C}(A(k_{n}x_{n}) − b), M)

= lim_{n→∞} ∡(Ax_{n} − \frac{b}{k_{n}} − P_{−C}(Ax_{n} − \frac{b}{k_{n}}), M)
(4.8)  = lim_{n→∞} arccos ϕ_{n}(\frac{b}{k_{n}}) = lim_{n→∞} arccos ϕ_{n}(0)
= lim_{n→∞} ∡(Ax_{n} − P_{−C}(Ax_{n}), M)
= \frac{π}{2} .

Here (4.8) follows from (4.7). Note further that since \frac{b}{k_{n}} ∈ U, Ax_{n} − \frac{b}{k_{n}} ∉ −C and so k_{n}x_{n} ∈ X\S_{C}^{b}. This contradicts (4.6). □

Combining Theorem 4.3 and 4.4, we have:

Corollary 4.5 Suppose that the system (A, C, b) has an error bound for some b ∈ Y. Then the system (A, C, 0) has an error bound.

The converse of above corollary is inexact as the following example shows.

Example 4.1 Let X = Y = ℝ^{3}, C = \{(x, y, z) ∈ ℝ^{3}|z ⩾ \sqrt{x^{2} + y^{2}}\}. Let A : X → Y be defined by A(x, y, z) = (x, 0, 0) for each (x, y, z) ∈ X; and let b = (0, 1, 1). Then

S_{C}^{b} = {(x, y, z) ∈ ℝ^{3}|A(x, y, z) − b ∈ −C} = {(x, y, z) ∈ ℝ^{3} : x = 0}.

Let e_{k} = (\frac{1}{k} , 0, 0). Then dist(e_{k}, S_{C}^{b}) = \frac{1}{k}. Pick h_{k} := (\frac{1}{k} , −1, −\sqrt{1 + \frac{1}{k^{2}}} ) ∈ −C; then

dist(Ae_{k} − b, −C) ⩽ ∥Ae_{k} − b − h_{k}∥ = \sqrt{1 + \frac{1}{k^{2}}} − 1 < \frac{1}{k^{2}}

Therefore, dist(e_{k}, S_{C}^{b}) ⩾ k dist(Ae_{k}−b, −C), showing that the system (A, C, b) has no error bound. On the other hand, one can show that (A, C, 0) does have an error bound (this can be seen immediately by applying Proposition 5.4 because Im(A)∩C = {0}).

Extending (4.2) and (4.3), we consider angles between two vector subspaces. Let M, N be closed vector subspaces of Y. If M ⊆ N or N ⊆ M then we stipulate that ∡(M, N) = 0. Suppose that M ⊈ N and N ⊈ M (equivalently M ∩ (M ∩ N)^{⊥} and N ∩ (M ∩ N)^{⊥} are not {0}). Then we define

∡(M, N) := inf{∡(x, y) : x ∈ M ∩ (M ∩ N)^{⊥}, y ∈ N ∩ (M ∩ N)^{⊥} and x, y ≠ 0}.

Recall that C denotes a closed convex cone in Y; to avoid triviality, we assume that {0} ≠ C ≠ Y. We say that a hyperplane supports C if H ∩ C is nonempty and C lies on one side of H: there exists y^{∗} ∈ Y^{∗}\{0} such that

sup_{h∈H}⟨y^{∗}, h⟩ = inf_{c∈C}⟨y^{∗}, c⟩; (4.9)

note that the above supremum and the infimum are attained at the origin 0 ∈ H ∩ C (and so H is a vector subspace). If in addition H ∩ C = {0} then H is called a vertex supporting hyperplane of C, otherwise a non-vertex one. There exists many nonvertex supporting hyperplanes of C. For example, pick a non-zero boundary point c of C and d ∈ Y \C such that ∥d − c∥ < \frac{1}{2}∥c∥. Then 0 ≠ P_{C}(d) ∈ (d − P_{C}(d))^{⊥} ∩ (C); hence (d−P_{C}(d))^{⊥}) is a non-vertex supporting hyperplane. Let C^{+}, C^{+i} respectively denote

C^{+} = {y ∈ Y : ⟨y^{∗}, c⟩ ⩾ 0 ∀c ∈ C},
C^{+i} = {y ∈ Y : ⟨y^{∗}, c⟩ > 0 ∀c ∈ C\{0}}.

The following result follows immediately from (4.9).

Lemma 4.6

(a) H ⊂ Y is a supporting hyperplane of C if and only if it can be expressed in the form H = ξ^{⊥} for some ξ ∈ C^{+}\{0}.

(b) H ⊂ Y is a hyperplane supporting C at some c̄ ∈ C\{0} if and only if it can be expressed in the form H = ξ^{⊥} for some ξ ∈ C^{+}\{0} with ξ(c̄) = 0.

(c) H ⊂ Y is a vertex supporting hyperplane of C if and only if it can be expressed in the form H = ξ^{⊥} for some ξ ∈ C^{+i}.

The following lemma follows easily from the Variational Inequalities.

Lemma 4.7 Let ξ ∈ Y with ∥ξ∥ = 1. Let c̄ ∈ bd(C). Then the following statements are equivalent:

(i) ξ ∈ −C^{+} and ξ(c̄) = 0.

(ii) ξ ∈ N_{C}^{1}(c̄).

(iii) −ξ ∈ N_{−C}^{1}(−c̄).

To prepare for the proof of our next theorem, we define a function ϕ : Y → R by

ϕ(y) = max{⟨x, y⟩ : x ∈ −C, ∥x∥ = 1}, y ∈ Y.

It is easy to see that ϕ is a convex function. Moreover, in view of the Variational Inequalities, one has the following:

Lemma 4.8 Let y ∈ Y \ − C. Then

(i) ϕ(y) ⩽ 0 ⇔ P_{−C}(y) = 0.
(ii) ϕ(y) = 0 ⇔ P_{−C}(y) = 0 and there exists x̄ ∈ −C, x̄ ≠ 0 such that ⟨y, x̄⟩ = 0.
(iii)ϕ(y) < 0 ⇔ P_{−C}(y) = 0 and ⟨y, z⟩ < 0 for any z ∈ −C, z ≠ 0 .

Theorem 4.9 Let b ∈ Y, x ∈ X\S_{C}^{b} and M := Im(A). Then the following assertions hold.

(i) ∡(Ax − b − P_{−C}(Ax − b), M) < \frac{π}{2} .
(ii)There exists a non-vertex supporting hyperplane H of C such that

∡(Ax − b − P_{−C}(Ax − b), M) + ∡(H, M) ⩽ \frac{π}{2} . (4.10)

Proof. For simplicity, we write z , q for Ax − b and P_{−C}(Ax − b) respectively. Then for any y ∈ −C one has by the Variational Inequality that

⟨z − q, y − q⟩ ⩽ 0.

By considering y = 0 and y = 2q separately we have ⟨z − q, q⟩ = 0. Thus, for any y ∈ −C,

⟨z − q, y⟩ ⩽ ⟨z − q, q⟩ = 0 < ⟨z − q, z − q⟩ = ⟨z − q, z⟩. (4.11)

If ∡(z − q, M) = \frac{π}{2} , then ⟨z − q, Au⟩ = 0 for any u ∈ X and so

⟨z − q, Au − b⟩ = ⟨z − q, z⟩ > 0; (4.12)

it follows from (4.11) that Au−b ∉ −C, for any u ∈ X; this contradicts the assumption that S_{C}^{b} ≠ ∅, and proves (i). Moreover if q = 0 and b ∈ M then the first term of the left-hand member of (4.10) is zero and hence (4.10) is seen to hold with any non-vertex supporting hyperplane H of C.

The remainder of the proof is devoted to show (ii) and we consider the following two cases.

Case 1: ϕ(z) ⩾ 0.

Take H to be (z−q)^{⊥}, which is clearly a supporting hyperplane of C and q ∈ H∩(−C). We claim that it is non-vertex. Indeed, if ϕ(z) > 0 then q ≠ 0 by Lemma 4.8 (i), so 0 ≠ q ∈ H ∩ (−C); if ϕ(z) = 0 then by Lemma 4.8 (ii), q = 0 and there exists x̄ ∈ (−C)\{0} such that ⟨z, x̄⟩ = 0; hence 0 ≠ x̄ ∈ H ∩ (−C). Therefore our claim is proved.

Moreover, whether q = 0 or not, we have P_{M}(z − q) ≠ 0 by (i); and, from the definitions,

∡(z − q, M) = ∡(z − q, P_{M}(z − q)). (4.13)

If z − q ∈ M then (4.10) holds trivially. We can therefore assume that z − q ∉ M. Write p for P_{M}(z−q) and let V = span(z−q, p). Since z−q ⊥ H and (z−q−p) ⊥ M, these two vectors are perpendicular to H ∩ M and hence

V ⊥ (H ∩ M); (4.14)

in particular

p ⊥ (H ∩ M). (4.15)

Since (z − q) ∉ H, V ∩ H is a one dimensional space: There exists v ≠ 0 such that V ∩ H = {λv|λ ∈ R}. Then ⟨z − q, v⟩ = 0 since v ∈ H. By (4.14) we have

v ⊥ (H ∩ M). (4.16)

Combining (4.15) and (4.16), it follows from the definition of angle between two subspaces that

∡(H, M) ⩽ ∡(v, p). (4.17)

Moreover,

∡(z − q, p) + ∡(p, v) = ∡(z − q, v) = \frac{π}{2} (4.18)

since the three vectors involved lie in the same plane (the two dimensional subspace V). From (4.13), (4.17) and (4.18), we have

∡(z − q, M) + ∡(H, M) ⩽ \frac{π}{2} ,

showing that (4.10) is satisfied by H.

Case 2: ϕ(z) < 0.

By Lemma 4.8, one has q = P_{−C}(Ax−b) = 0. We can assume that b ∉ M (otherwise, the results of the theorem have already been shown). Then ϕ(P_{M}b − b) > 0. In fact,

⟨P_{M}b − b, Au − b⟩ = ∥P_{M}b − b∥^{2} > 0

14 Kung Fu Ng and Wei Hong Yang

for any u ∈ X because (P_{M}b − Au) ∈ M ⊥ (P_{M}b − b). Picking ū ∈ S_{C}^{b} and letting z̄ = Aū − b it follows that z̄ ∈ −C and ⟨P_{M}b − b, z̄⟩ > 0; hence ϕ(P_{M}b − b) > 0 by definition of ϕ. Since ϕ takes values of opposite signs at the end-points of the linesegment [z, P_{M}b − b] ⊂ M − b there exists w in that line-segment such that ϕ(w) = 0; write w := tz + (1 − t)(P_{M}b − b) ∈ M − b. (4.19) with some t ∈ (0, 1). Note that z, w ∉ M because b ∉ M. Since ϕ(w) = 0 one has that w ∉ −C; for otherwise, the definition of ϕ would imply that ϕ(w) ⩾ ⟨w, \frac{w}{∥w∥}⟩ = ∥w∥ > 0. According to (4.4)

cos ∡(w, M) = \frac{∥P_{M}(w)∥}{∥w∥}.

Since (w − P_{M}(w)) ⊥ P_{M}(w), it follows that

ctg∡(w, M) = \frac{∥P_{M}(w)∥}{∥w − P_{M}(w)∥}. (4.20)

Similarly,

ctg∡(z, M) = \frac{∥P_{M}(z)∥}{∥z − P_{M}(z)∥}. (4.21)

Let y ∈ M − b: y = Au − b for some u ∈ X. Note that

y − P_{M}y = Au − b − P_{M}(Au − b) = Au − b − [Au − P_{M}(b)] = P_{M}b − b. Considering z and w separately for the above y, we arrive at z − P_{M}z = w − P_{M}w = P_{M}b − b. (4.22) From (4.19) one has ∥P_{M}w∥ = ∥tP_{M}z∥. Together with (4.20), (4.21) and (4.22), we have ctg∡(z, M) > ctg∡(w, M), that is ∡(z, M) < ∡(w, M). (4.23) By Case 1 (applied to w in place of z) there exists a non-vertex supporting hyperplane H of C such that

∡(w, M) + ∡(H, M) ⩽ \frac{π}{2} . (4.24)

Combining (4.23) and (4.24), (4.10) is seen to hold. □ Theorem 4.10 Let T consist of all non-vertex supporting hyperplanes of C. If

inf_{H∈T} ∡(H, Im(A)) > 0, (4.25)

then system (A, C, b) has an error bound provided that S_{C}^{b} ≠ ∅.

Proof. Let α denote the infimum in (4.25). Then (4.10) implies that

∡(Ax − b − P_{−C}(Ax − b), M) ⩽ \frac{π}{2} − α < \frac{π}{2} , ∀x ∈ X\S_{C}^{b}.

Thus the result follows immediately from Theorem 4.3. □

The following example provides an application of Theorem 4.10.

Example 4.2 Let X = Y = ℝ^{2}, C = {(x, y) ∈ ℝ^{2}|x ⩾ 0 and y ⩾ 0}. Let A : X → Y be defined by A(x, y) = (−x, x). Then there are only two non-vertex supporting hyperplane (lines) of C: they are respectively defined by x = 0 and y = 0. Since the angles between Im(A) and these two lines are equal to \frac{π}{4} , Theorem 4.10 implies that the system (A, C, b) has an error bound for each b ∈ Y satisfying S_{C}^{b} ≠ ∅.

The following example shows that the converse of Theorem 4.10 is not true.

Example 4.3 Let X = Y = ℝ^{2}, C = {(x, y) ∈ ℝ^{2}|x ⩾ 0 and y ⩾ 0}. Let A : X → Y be defined by A(x, y) = (x, 0). Let H be the line defined by y = 0. Then ∡(Im(A), H) = 0, so (4.25) is not satisfied. But by Theorem 3.4, the system (A, C, b) has an error bound for any b ∈ ℝ^{2} with S_{C}^{b} ≠ ∅.

The following lemma gives a simple method to compute ∡(H, Im(A)).

Lemma 4.11 Let H be a hyperplane of Y and l ⊥ H. Let M be a proper subspace of Y. Then

∡(H, M) + ∡(l, M) = \frac{π}{2} . (4.26)

Proof. It is easy to see that (4.26) is equivalent to

cos^{2} ∡(H, M) + cos^{2} ∡(l, M) = 1. (4.27)

We assume that ∥l∥ = 1. If l ∈ M or M ⊂ H, (4.26) is obvious. We can therefore assume that l ∉ M and M ⊄ H. Let N = (M ∩ H)^{⊥} ∩ M. From M ⊄ H we know N ≠ {0}. Since N ∩H = (M ∩H)^{⊥} ∩(M ∩H) = {0} and H is a hyperplane it follows that dim(N) = 1: there exists a unit vector n_{0} which linearly spans N. Because the unit sphere of a Hilbert space is weak compact, there exists h_{0} ∈ (M ∩ H)^{⊥} ∩ H, ∥h_{0}∥ = 1, such that

∡(H, M) = ∡(h_{0}, n_{0}). (4.28)

We can express n_{0} in the form n_{0} = αl + βh, where h ∈ H, ∥h∥ = 1, and α^{2} + β^{2} = 1, αβ ≠ 0. Since l ⊥ (M ∩ H), we have h ⊥ (M ∩ H). From definition and (4.28) we have |⟨n_{0}, h_{0}⟩| ⩾ |⟨n_{0}, h⟩|, which implies that |β⟨h, h_{0}⟩| ⩾ |β⟨h, h⟩|. Replacing h_{0} by −h_{0} if necessary, it follows that βh = βh_{0}, so n_{0} = αl + βh_{0}. Thus, from (4.28),

cos ∡(H, M) = cos ∡(h_{0}, n_{0}) = |β|. (4.29)

Note that m ∈ M can be written in the form m = sn_{0} + tk, where k ∈ M ∩ H and ∥k∥ = 1; hence |⟨l, m⟩| = |s⟨l, n_{0}⟩| ⩽ ∥m∥ · |⟨l, n_{0}⟩|. It follows from (4.3) that

cos ∡(l, M) = |⟨l, n_{0}⟩| = |α|. (4.30)

Thus (4.27) and hence (4.26) hold. □

Theorem 4.12 Let C^{+} denote the set of all x satisfying ⟨x, c⟩ ⩾ 0 for each c ∈ C.If

sup_{\begin{matrix}l∈bd(C^{+}) \\ l≠0 \end{matrix}} ∡(l, Im(A)) < \frac{π}{2} (4.31)

then system (A, C, b) has an error bound provided that S_{C}^{b} ≠ ∅.

Proof. Let β denote the supremum in (4.31). Let H ∈ T : H is a hyperplane in Y supporting C at some c̄ ∈ C\{0}. Take l ∈ H^{+} with ∥l∥ = 1. By (a) of Lemma 4.6 and replacing l by −l if necessary, we can suppose that l ∈ C^{+} and l(c̄) = 0. Then l must not be in the interior of C^{+}. Hence it follows from Lemma 4.11 that

∡(H, Im(A)) = \frac{π}{2} − ∡(l, Im(A)) ⩾ \frac{π}{2} − β > 0,

showing that (4.25) holds. Therefore by Theorem 4.10, the system (A, C, b) has an error bound provided that S_{C}^{b} ≠ ∅. □

Next we give an example which shows the application of Theorem 4.12.

Example 4.4 Let X = ℝ^{3}, C = \{(x, y, z) : z ⩾ \sqrt{x^{2} + y^{2}}\}. Let A(x, y, z) = (x, y, 0). The boundary of C^{+} is \{(x, y, z) : z = \sqrt{x^{2} + y^{2}}\}. For l ∈ bd(C^{+}), l ≠ 0, ∡(l, Im(A)) = ∡(l, P_{Im(A)}l). We have

sup_{\begin{matrix}l∈bd(C^{+}) \\ l≠0 \end{matrix}} ∡(l, Im(A)) = \frac{π}{4} < \frac{π}{2} .

By Theorem 4.12 we know that system (A, C, b) has an error bound for each b such that S_{C}^{b} ≠ ∅.

5. The Ice-Cream Cone. We continue to use the notations defined in the preceding section; in particular, Y is a Hilbert space: infinite dimensional or finite dimensional. We assume throughout that M := Im(A) is closed. Let V be a closed convex set in Y and x ∈ bd(v). N_{V} (x) equals to the normal cone of V at x in the following sense:

v ∈ N_{V} (x) if and only if ⟨v, t⟩ ⩽ 0 for t ∈ T_{V} (x).

Lemma 5.1 Let V be a closed convex set in a Hilbert space Y and x ∈ bd(v). Let d_{V} (y) be defined by d_{V} (y) = dist(y, V). Then for each h ∈ Y, the maxima below are attained and

max{|⟨ξ, h⟩| : ξ ∈ N_{V}^{1} (x)} = max{|⟨η, h⟩| : η ∈ ∂d_{V} (x)},

If max{⟨η, h⟩ : η ∈ ∂d_{V} (x)} ⩾ 0 for some h, then

max{⟨ξ, h⟩ : ξ ∈ N_{V}^{1} (x)} = max{⟨η, h⟩ : η ∈ ∂d_{V} (x)}.

Proof. We assume that h ≠ 0. According to the result in [6, pages 259],

∂d_{V} (x) = N_{V} (x) ∩ B(0, 1), (5.1)

where B(0, 1) denotes the closed unit ball in H. In particular ∂d_{V} (x) is weak compact and contains N_{V}^{1} (x); hence there exists η̄ ∈ ∂d_{V} (x) such that

sup{|⟨ξ, h⟩| : ξ ∈ N_{V}^{1} (x)} ⩽ max{|⟨η, h⟩| : η ∈ ∂d_{V} (x)} = ⟨η̄, h⟩.

From (5.1), it follows that η̄ is of norm 1, that is η̄ ∈ N_{V}^{1} (x). This proves the first assertion of the theorem. The proof for the second assertion is similar. □

Let b ∈ Y and we assume as before that S_{C}^{b} ≠ ∅. For simplicity, let Ω denote (b−C)∩M where M := Im(A). Note that Ω ≠ ∅. Let I_{A} denote the identity operator from M into Y. Then Ω = {y ∈ M : I_{A}y − b ⩽ 0}. Let bd_{M}(Ω) denote the boundary of Ω relative to M and N_{Ω}^{1}(y) denote N_{Ω}^{1}(y) ∩ M. That is,

N_{Ω}^{1}(y) = {h : h ∈ Im(A) and dist(x + th, Ω) = t∥h∥, ∀t ∈ [0, 1]}.

We have the following theorem.

Theorem 5.2 The following statements are equivalent:

(i) The system (A, C, b) has an error bound.
(ii) inf_{\begin{matrix}x∈bd(S_{C}^{b}) \\ u∈N_{S^{b}_{C}}^{1} (x) \end{matrix}} max\{⟨ξ, Au⟩ : ξ ∈ N_{−C}^{1}(Ax − b)\} > 0.

(iii) inf_{\begin{matrix}y∈bd_{M} (Ω) \\ h∈N_{Ω}^{1}(y) \end{matrix}} max\{⟨ξ, h⟩ : ξ ∈ N_{−C}^{1}(y − b)\} > 0.

Proof. Let φ_{b}(x) and g be defined by (3.1) and (3.2). By the Chain Rules and [3, Proposition 2.1.2], we have

φb^{′}(x; u) = g′(Ax − b; Au) = max{⟨ξ, Au⟩ : ξ ∈ ∂g(Ax − b)}, ∀x, u ∈ X.

If x ∈ bd(S_{C}^{b}) then Ax − b ∈ bd(−C) and it follows from Lemma 5.1 that

φb^{′}(x; u) = max{⟨ξ, Au⟩ : ξ ∈ N_{−C}^{1}(Ax − b)},

which together with Theorem 2.2 and Remark 2.1 imply (i) ⇔ (ii). Similarly (iii) holds if and only if the system (I_{A}, C, b) has an error bound. Thus the result now follows from Corollary 3.3. □

Corollary 5.3 Suppose that there exist ȳ ∈ bd_{M}(Ω) and a hyperplane H satisfying the properties:

(a) N_{−C}^{1}(ȳ − b) is a singleton.
(b) M ⊂ H and H supports −C at ȳ − b.

Then the system (A, C, b) has no error bound.

Proof. Write c̄ for b − ȳ. Then c̄ ∈ bd(C) and, by assumption, take a hyperplane H ⊃ M such that it supports −C at −c̄. By Lemmas 4.6 and 4.7, there exists ξ̄ of norm 1 such that ξ̄(c̄) = 0 and ξ̄ ∈ H^{⊥} ∩ N_{−C}^{1}(−c̄). Hence, since N_{−C}^{1}(−c̄) is a singleton by assumption,

max {⟨ξ, h⟩ : ξ ∈ N_{−C}^{1}(−c̄)} = ⟨ξ̄, h⟩, ∀h ∈ Y. (5.2)

Note that, since ξ̄ ∈ H^{⊥} ⊂ M^{⊥}, ⟨ξ̄, l⟩ = 0 for each l ∈ M. Pick h̄ ∈ N_{Ω}^{1}(ȳ). Since N_{Ω}^{1}(ȳ) ⊂ M it follows that ⟨ξ̄, h̄⟩ = 0. Combining this with (5.2), one has

max {⟨ξ, h̄⟩ : ξ ∈ N_{−C}^{1}(ȳ − b)} = 0.

Since ȳ ∈ bd_{M}(Ω) and h̄ ∈ N_{Ω}^{1}(ȳ), this implies that (iii) of Theorem 5.2 does not hold, and therefore we conclude from Theorem 5.2 that the system (A, C, b) has no error bound. □

Proposition 5.4 Suppose that Y is finite dimensional, and that Im(A) ∩ C = {0}. Then the system (A, C, 0) has an error bound.

Proof. Suppose that (A, C, 0) has no error bound. Then according to Theorem 4.2, there exists a sequence {x_{k}} ⊂ X\S_{C}^{0} such that

lim_{k→∞} ∡(Ax_{k} − P_{−C}(Ax_{k}), Im(A)) = \frac{π}{2} . (5.3)

Without loss of generality we can assume that ∥Ax_{k}∥ = 1 for each k. Since Y is finite dimensional, {Ax_{k}} has a cluster point, which will be denoted by z. It is clear that ∥z∥ = 1 and that z = Ax̄ for some x̄ ∈ X because Im(A) is closed. From Im(A) ∩ −C = {0} we know that z ∉ −C and hence that x̄ ∉ S_{C}^{0}. But (5.3) implies that

∡(Ax̄ − P_{−C}(Ax̄), Im(A)) = \frac{π}{2} ,

contradicting to Theorem 4.9 (i). □

Lemma 5.5 Suppose that Y is finite dimensional. Let b ∈ Y. If (Im(A) − b) ∩ (−C) is bounded and (Im(A) − b) ∩ int(−C) ≠ ∅, then the system (A, C, b) has an error bound.

Proof. Write M for Im(A). Denote (b − C) ∩ M by Ω. By [16, Theorem 2.5] there exists a constant κ > 0 such that for any y ∈ M,

dist(y, Ω) = dist(y − b, Ω − b) ⩽ κ[dist(y − b, −C) + dist(y − b, M − b)]
(5.4)  = κ[dist(y − b, −C)].

Note that this just means that the system (I_{A}, C, b) has an error bound, and therefore it follows from Corollary 3.3 that the system (A, C, b) has an error bound. □

We conclude our paper with a discussion on the special case when C is an “icecream” cone. Here the so-called ice-cream cone is defined by S_{ice} = f^{−1}(−∞, 0], where f is defined by

f(x) = \sqrt{∑_{i=1}^{n−1} x_{i}^{2}} − x_{n}, x ∈ ℝ^{n}. (5.5)

Any set which is not a singleton will be referred as a ray if it can be expressed in the form {y_{0} + th : t ⩾ 0}. A ray which is an extreme subset of S_{ice} then it is called an extreme ray. The following lemma is stated for our easy reference; it is elementary and we need not give proof here.

Lemma 5.6 Let S_{ice} be the ice-cream cone in ℝ^{n} and let f be defined by (5.5). Then

(i) S_{ice} = S_{ice}^{+}, that is ξ belongs to S_{ice} if and only if ξ ∈ ℝ^{n} and

⟨ξ, y⟩ ⩾ 0, ∀y ∈ S_{ice}.

(ii) The union of the extreme rays of S_{ice} equals to the topological boundary

bd(S_{ice}). (iii) If s′ ∈ bd(S_{ice})\{0}, s ∈ S_{ice}, and s is not a multiple of s′ then the open

line-segment (s, s′) is contained in int(S_{ice}), the topological interior of S_{ice}. (iv) If x ∈ bd(S_{ice}) and x ≠ 0 then ∂f(x) = {▽f(x)}, where

▽f(x) = (\frac{x_{1}}{\sqrt{∑_{i=1}^{n−1} x_{i}^{2}}} , ⋯, −1).

and N_{S_{ice}}^{1}(x) = \{\frac{▽f(x)}{∥▽f(x)∥}\}. Moreover ⟨▽f(x), x−x′⟩ is strictly positive when-

ever x′ ∈ int(S_{ice}).

(v) If x ∈ −S_{ice} then dist(x, S_{ice}) = ∥x∥.

In what follows we will identify exactly when (A, S_{ice}, b) has an error bound (and when it has no), where A is linear operator from X into Y and Y = ℝ^{n} is equipped with the partial order defined by S_{ice}. As in the preceding section, let M := Im(A). Also we use K to denote the cone S_{ice}. It will be shown that there are three possible cases.

Case I. M contains an interior point of K; Case II. M ∩ K = {0}; Case III. M ∩ K is an extreme ray of K.

These cases are respectively to be dealt with in the next three theorems.

Theorem 5.7 Suppose that

Im(A) ∩ int(K) ≠ ∅. (5.6)

Then the system (A, K, b) has an error bound for each b ∈ ℝ^{n}.

Proof. Let b ∈ ℝ^{n} and Ω := M ∩ (b − K). We proceed as in the proof of Lemma 5.5. By virtue of (5.6), one can apply [16, Theorem 2.6] (instead of [16, Theorem 2.5]) to obtain (5.4), completing the proof. □

Theorem 5.8 Suppose that

M ∩ K = {0}. (5.7)

Let b ∈ ℝ^{n} be such that

(M − b) ∩ (−K) ≠ ∅. (5.8)

Then the following assertions hold.

(a) If (M − b) ∩ int(−K) ≠ ∅ then (A, K, b) has an error bound.

(b) If b ∈ M then (A, K, b) has an error bound.

(c) If (M − b) ∩ int(−K) = ∅ and b ∉ M then (A, K, b) has no error bound.

Proof. By (5.7) and [15, Corollary 8.4.1], (M − b) ∩ (−K) is bounded. Thus (a) holds by Lemma 5.2.

(b) By (5.7) and Proposition 5.4, (A, K, 0) has an error bound: there exists τ > 0 such that

dist(x, S_{K}^{0}) ⩽ τdist(Ax, −K), ∀x ∈ X. (5.9)

where S_{K}^{0} := {x ∈ X : Ax ∈ −K}. Since b ∈ M, take x̄ ∈ X such that Ax̄ = b. Then S_{K}^{b} = x̄ + S_{K}^{0}. Writing z for x + x̄ it follows from (5.9) that

dist(z, S_{K}^{b}) ⩽ τdist(Az − b, −K), ∀z ∈ X,

proving (b).

To prove (c), we take s̄ ∈ (M −b)∩(−K) by (5.8). By assumption in (c), it follows that s̄ ∈ bd(−K). By (iv) of Lemma 5.6, N_{−K}^{1}(s̄) is certainly a singleton (consisting of \frac{▽f(s̄)}{∥▽f(s̄)∥}).

Moreover, by the Separation Theorem, take ξ ∈ ℝ^{n} of norm 1 such that

sup_{y∈M−b}⟨ξ, y⟩ = ⟨ξ, s̄⟩ ⩽ inf_{y∈−K}⟨ξ, y⟩.

Since −K is a cone it follows that ⟨ξ, s̄⟩ = 0 and hence that ξ^{⊥} supports −K at s̄. Note also that ξ is bounded on M and hence vanishes on M, that is ξ^{⊥} ⊃ M.

We claim further that (M − b) ∩ (−K) is the singleton {s̄}. Indeed, let s ∈ (M−b)∩(−K). Then the segment [s, s̄] is also contained in (M−b)∩(−K); in particular 0 ∉ [s, s̄] as b ∉ M. By assumption in (c), it follows that [s, s̄] ⊂ bd(−K). By (iii) of Lemma 5.6, it follows that s̄ = ts for some t > 0. If t > 1 then s̄ − s ∈ M ∩ (−K), contradicting (5.7). Similarly t < 1 is also not possible. Therefore s̄ = s and our claim stands. Let Ω = M ∩ (b − K); then Ω = {s̄+ b}. By Corollary 5.3, (A, K, b) has no error bound. □

Theorem 5.9 Suppose that

{0} ≠ M ∩ K ⊂ bd(K). (5.10)

Let b ∈ ℝ^{n} be such that

(M − b) ∩ (−K) ≠ ∅. (5.11)

Then the following assertion hold.

(a) If dim(M) ≠ 1 then (A, K, b) has no error bound.

(b) If dim(M) = 1 then (A, K, b) has an error bound.

Proof. Pick s̄ ∈ M ∩ K, s̄ ≠ 0. By (iii) of Lemma 5.6 any element s of M ∩ K must be a multiple of s̄ (because by (5.10) we know that (s̄, s) does not contain any interior point of K); therefore M ∩ K is an extreme ray of K. Separating M and int(K), one obtains a hyperplane H containing M and supporting K at s̄.

(a) Suppose that dim(M) ≠ 1. Then the ray M ∩ K cannot contain any relative interior point in M. Let Ω = M ∩ (−K). Then −s̄ ∈ bd_{M}(Ω), and N_{−K}^{1}(−s̄) is a singleton by Lemma 5.6 (iv). Hence, by Corollary 5.3, (A, K, 0) has no error bound. In view of Corollary 4.5 this implies that (A, K, b) has no error bound for any b ∈ ℝ^{n}.

(b) Suppose that dim(M) = 1. We consider the system (I_{A}, K, b) where b satisfying (5.11). In view of Corollary 3.3 it is sufficient to show that (I_{A}, K, b) has an error bound, that is, to show that there exists τ > 0 such that

dist(m, S) ⩽ τdist(m − b, −K), ∀m ∈ M, (5.12)

where S := {m ∈ M : m − b ∈ −K} = M ∩ (b − K). Note from Lemma 5.6 (v) that if L is a line containing an extreme ray R of K then, for each l ∈ L\R,

dist(l, K) = dist(l, L ∩ K)(= ∥l∥).

Therefore, if b ∈ M,

dist(m, M ∩ (b − K)) = dist(m − b, (M − b) ∩ (−K))
= dist(m − b, −K), ∀m ∈ M.

Therefore (5.12) holds with τ = 1, and hence we may suppose henceforth that b ∉ M.

We recall from the first paragraph of the proof that there exists s̄ ∈ K, ∥s̄∥ = 1, such that

M ∩ (−K) = {−ts̄: t ⩾ 0}

is an extreme ray of −K. By (5.11), take s_{0} ∈ (m − b) ∩ (−K). Then it is easily that s_{0} +t(−s̄) also belongs to (m−b)∩(−K) for each t ⩾ 0. It follows that (m−b)∩(−K) is a ray; we suppose without loss of generality that its end point is s_{0}:

(m − b) ∩ (−K) = {s_{0} + t(−s̄) : t ⩾ 0}. (5.13)

Since s_{0} ∈ M − b and M − b is disjoint from M, s_{0} is not a multiple of s̄. Hence, for each t > 0, s_{0}+t(−s̄) is not multiple of s̄. By (iii) of Lemma 5.6 , s_{0}+t(−s̄) ∈ int(−K) and hence

⟨N_{−K}(s_{0}), −s̄⟩ < 0. (5.14)

This implies that (5.12) holds for some constant τ > 0. Indeed, if not, then for each k ∈ ℕ there exists m_{k} ∈ M such that

dist(m_{k} − b, (m − b) ∩ (−K)) > k · dist(m_{k} − b, −K).

Writing s_{0} + t_{k}s̄ (with t_{k} > 0) for m_{k} − b it follows that

t_{k} > k · dist(s_{0} + t_{k}s̄, −K), ∀k.

Since −K is convex, it follows that 0 must be a cluster point of {t_{k}}. This implies that s̄ ∈ T_{−K}(s_{0}), and ⟨N_{−K}(s_{0}), s̄⟩ ⩽ 0, contradicting (5.14). □

Acknowledgments. We are indebted to Professor J.-S. Pang (who suggested us to look at the ice-cream cone case) and to Professor X.Y.Zheng for many stimulating discussion.

REFERENCES

[1] J.M.Borwein, S.P.Fitzpatrick and J.R.Giles, The differentiability of real functions on normed linear space using generalized subgradients. J. Math. Anal. Appl. 128(1987), 512–534.

[2] J.V.Burke and P.Tseng, A unified analysis of Hoffman’s bound via Fenchel duality, SIAM J.Optim., 6(1996), 265–282.

[3] F.H.Clarke, Optimization and Nonsmooth Analysis, Wiley, New York, 1983.

[4] F.Deutsch, The angle between subspaces of a Hilbert space, In S.P.Singh, editor, Approximation Theory, Wavelets and applications, 107–130. Kluwer Academic Publishers, 1995.

[5] Y.R.He, Error bound for nonlinear complementarity problems, Preprint.

[6] J.-B. Hiriart-Urruty and C. Lemaréchal, Convex Analysis and Minimization Algorithms I, Springer-Verlag, New York, 1993.

[7] A.J.Hoffman, On approximate solutions of systems of linear inequalities, Journal of Research of the National Bureau of Standards, 49(1952), 263–265.

[8] A.D.Ioffe, Regular points of Lipschitz functions. Trans. Amer. Math. Soc., 251(1979), 61-69.

[9] A.Lewis and J.-S.Pang, Error bounds for convex inequality systems, in Generalized Convexity, Generalized Monotonicity: Recent Results, Proceedings of the Fifth Symposium on Generalized Convexity, Luminy, June 1996, J.-P. Crouzeix, J.-E. Martinez-Legaz, and M.Volle, eds., Kluwer Academic Publishers, Dordrecht, 1997, 75–100.

[10] K.F.Ng and X.Y.Zheng, Error bound for lower semicontinuous functions in normed spaces, SIAM J. Optim., 12(2001), 1-17.

[11] K.F.Ng and X.Y.Zheng, Global weak sharp minima on Banach spaces, Preprint.

[12] J.-S.Pang, Error bounds in mathematical programming, Math. Program., 79(1997), 299–332.

[13] R.R.Phelps, Convex Functions, Monotone Operators and Differentiability, Springer-Verlag, Berlin, Heidelberg, 1989.

[14] S.M.Robinson, Stability theory for systems of inequalities. Part I: Linear systems, SIAM J. Numer. Anal. 12(1975), 754-769.

[15] R.T.Rockafellar, Convex Analysis, Princeton Univeersity Press, Princeton, NJ, 1970.

[16] Shuzhong Zhang, Global error bounds for convex conic problems, SIAM J. Optim., 10(2000), 836–851.