CHARACTERIZATIONS OF ERROR BOUNDS FOR CONVEX MULTIFUNCTIONS ON BANACH SPACES

KUNG FU NG AND XI YIN ZHENG

Abstract. In terms of the contingent derivative, Dini derivative and the numerical derivative, we give a series of characterizations of error bounds for convex multifunctions defined on Banach spaces. Applications are given to improve some known results as well as to provide new results on the existence of error bounds for not necessarily lower semicontinuous convex functions (Our results are valid for general proper convex functions while they are new even for the continuous case).

1. Introduction. Let X be a Banach space, f : X → R ⋃{+∞} a proper function, and let S = {x ∈ X|f(x) ≤ 0}. Let τ ≥ 0. We say that f has an error bound τ if for each x ∈ X,

dist (x, S) ≤ τ[f(x)]_{+}. (1.1)

The research on error bounds especially for convex functions has attracted the interest of many researchers and there are a vast number of publications reporting the progress in this area. For more details, we refer the reader to surveys Lewis and Pang (1997), Pang (1997) and a recent special issue of Mathematical Programming (Vol. 88, No.2 (2000)). Li and Singer (1998), Zalinescu (2001) and Zheng (2001) considered error bounds in a more general setting: error bounds for convex inclusions. Let X be a Banach space, Y a normed space and let F : X → 2^{Y} be a convex multifunction, that is,

λF (x_{1}) + (1 − λ)F (x_{2}) ⊂ F (λx_{1} + (1 − λ)x_{2}) ∀x_{1}, x_{2} ∈ X, 0 ≤ λ ≤ 1. (1.2)

Let b ∈ Y and consider the convex inclusion problem:

b ∈ F x, (1.3)

(where we write F x for F (x) for simplicity of notation). τ ≥ 0 is called a (global) error bound for the problem (1.3) if for each x ∈ X,

dist(x, F^{−1}b) ≤ τdist(b, F x). (1.4)

If f is a convex function on X and F is defined by F x = [f(x), +∞) for each x ∈ X then (1.1) holds if and only if (1.4) holds with b = 0. Thus (1.4) may be regarded as an extension of (1.1).

In this paper, we establish some suffiecient/necessary conditions for the existence of τ satisfying (1.4). Along this line, the result given in Theorem 3.3 is applicable to the problem (1.3) even if the convexity requirement (1.2) is dropped, while other results of this paper do require the condition (1.2). Below we set some notations and give a short summary on our results, while more details on notations as well as some background materials will be given in section 2. For a convex closed set K in a normed space and x ∈ ∂K, N_{K}(x) denotes the normal cone of K at x consisting of all h in X for each of which there exists a normalized continuous linear functional x^{∗} on X supporting K at x such that

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

Key words. error bound, convex multifunction, convex function, Banach space.

⟨x^{∗}, h⟩ = ∥h∥. (1.5)

This type of cones appear to be adequate for our study when X is finite-dimensional or reflexive but not for a general Banach space X because it may happen that N_{K}(x) = {0} for all x in the topological boundary ∂K of K. For γ ∈ (0, 1), let N_{K}(x, γ) denote the cone consisting of all h similarly as above but (1.5) is replaced by a weaker condition:

⟨x^{∗}, h⟩ ≥ γ∥h∥. (1.6)

Lemma 2.1 implies in particular that for each x ∈ X \ K there exist a point a in a certain subset of K and a recession direction c of K such that the ray {a + tc : t ≥ 0} is contained in ∂K and

\frac{x − a − c}{∥x − a − c∥} ∈ N_{K}(a + tc, γ), ∀t ≥ 0.

A special case of Theorem 3.2 implies that τ > 0 is an error bound for the convex inclusion problem (1.1) if F satisfies the following regularity at b with ratio τ: for each a ∈ ∂(F^{−1}b) there exists r_{a} > 0 such that

B(b, r_{a}) ⊂ F (B(a, τr_{a})).

The proof of Theorem 3.2 is based on Theorem 3.1 where we study relationship between global and local error bounds. In section 4, we present characterizations for a constant to be an error for (1.3). It is shown in Theorem 4.1 that

\frac{1}{τ^{∗}} = lim_{γ→1^{−}} inf\{dist(0, DF (a, b)(h)) : a ∈ ∂(F^{−1}b), h ∈ N_{F^{−1}b}(a, γ), ∥h∥ = 1\}, (1.7)

where τ^{∗} := inf{τ ≥ 0 : τ is an error bound of (1.3)}, and DF denotes the contingent derivative [Aubin and Frankowska (1990)] of F. Theorem 4.2 shows that (1.7) remains true even if that DF is replaced by the Dini-derivative D̂F (see section 4 for its definition). In section 4, we also introduce the numerical derivative d̃F of F, which is defined by, for each (x, y) ∈ X × Y and h ∈ X,

d̃F (x, y)(h) := d^{+}ϕ(0)

where ϕ(t) := ϕ_{x,y,h}(t) denotes the distance of (x + th, y) to the graph of F and d^{+}ϕ(0) := lim_{t→0^{+}} \frac{ϕ(t)−ϕ(0)}{t}. In terms of this derivative several more characterizations are given for (1.3) to have an error bound; one of these characterizations is

d̃F (a, b)(h) ≥ δ, ∀a ∈ ∂(F^{−1}b), h ∈ N_{F^{−1}b}(a, γ) with ∥h∥ = 1 (1.8)

for some constants δ > 0 and γ ∈ (0, 1). While this condition infers to the situation when points on the boundary of the solution F^{−1}b of (1.3) move along the “γ–outer” normals (the unit vectors in N_{F^{−1}b}(·, γ)), one can also infer to the situation when points outside F^{−1}b move toward to the solution set (see (v) of Theorem 4.3).

For a general closed convex set K it follows from the definition of recession cones that K = K + Rec(K). More generally a subset A of K is said to have the property (R) (the recession property) if K = A + Rec(K). It may happen that certain bounded subsets have property (R) even if K itself is unbounded; for instance, a polyhedron, the solution set of a linear inequality system, always has a bounded subset with the property (R). In many of our discussions above (e.g. in (1.8)), ∂(F^{−1}b) can be replaced by A∩∂(F^{−1}b) (or by A_{ε}∩∂(F^{−1}b), where A_{ε} := {x ∈ X : dist(x, A) < ε}). Another example is Theorem 4.4 where we show that (assuming a Slater condition for F), (1.3) has an error bound if and only if there exist γ ∈ (0, 1) and ε > 0 such that

lim inf_{∥a∥→∞,a∈A_{ε}∩∂(F^{−1}b)} inf{dist(0, DF (a, b)(h)) : ∥h∥ = 1, h ∈ N_{F^{−1}b}(a, γ)} > 0.

Thus, for example, (1.3) has an error bound if there exists a bounded subset of F^{−1}b with the property (R) (the above lower limit is clearly is +∞ when A_{ε} is bounded). As applications, some new results on the existence of error bounds for singled-valued convex functions are given in the last section of the paper.

2. Preliminaries. Let X, Y be normed spaces; we use B(z, r) to denote the ball (in X or Y) with center z and radius r. Let K ⊂ X be a closed convex set and σ_{K} : X^{∗} → R be the support function of K, that is, σ_{K}(x^{∗}) = sup{⟨x^{∗}, x⟩ : x ∈ K} for each x^{∗} ∈ X^{∗}. We use ∂K to denote the topological boundary of K. Let F : X → 2^{Y} be a convex multifunction. For y_{0} ∈ F (X) and r > 0, B_{F} (y_{0}, r) is defined by

B_{F} (y_{0}, r) := \{y_{0}\} ∪ \{y ∈ B(y_{0}, r) : y_{0} + (r − ∥y − y_{0}∥)\frac{y_{0} − y}{∥y_{0} − y∥} ∈ F (X)\}. (2.1)

Let Σ_{X^{∗}} denote the unit sphere of X^{∗}, that is, Σ_{X^{∗}} = {x^{∗} ∈ X^{∗} : ∥x^{∗}∥ = 1}. As in Ng and Zheng (2001), for x ∈ ∂K and γ ∈ (0, 1], let

N_{K}(x, γ) := {h ∈ X : dist(x + th, K) ≥ γt∥h∥ for all t > 0}

and

N_{K}(x, γ) := {h ∈ X : ∃x^{∗} ∈ Σ_{X^{∗}} such that ⟨x^{∗}, x⟩ = σ_{K}(x^{∗}) and ⟨x^{∗}, h⟩ ≥ γ∥h∥}.

It is known (Ng and Zheng (2001)) and easy to verify that

N_{K}(x, γ) ⊂ N_{K}(x, γ) (2.2)

In the case when γ = 1, one has that N_{K}(x, 1) = N_{K}(x, 1). [Indeed, by (2.2), it suffices to show that h ∈ N_{K}(x, 1) for each h ∈ N_{K}(x, 1)\{0}. Fix an h in N_{K}(x, 1)\{0}. Then int(B(x+h, ∥h∥))∩K = ∅. By the Separation Theorem, there exists x^{∗} ∈ Σ_{X^{∗}} such that

⟨x^{∗}, x + h⟩ − ∥h∥ = inf{⟨x^{∗}, z⟩ : z ∈ B(x + h, ∥h∥)} ≥ σ_{K}(x^{∗}).

It follows from x ∈ B(x + h, ∥h∥) ∩ K that

⟨x^{∗}, x + h⟩ − ∥h∥ = ⟨x^{∗}, x⟩ = σ_{K}(x^{∗})

and so ⟨x^{∗}, h⟩ = ∥h∥. This shows that h ∈ N_{K}(x, 1).] Henceforth, we use N_{K}(x) to denote both N_{K}(x, 1) and N_{K}(x, 1). For convenience, let

N_{K}^{1}(x) := {h ∈ N_{K}(x) : ∥h∥ = 1}

and

N_{K}^{1}(x, γ) := {h ∈ N_{K}(x, γ) : ∥h∥ = 1}, for γ ∈ (0, 1).

Following Zheng (2001), we say that a subset A of K has the property (R) if K = A + Rec(K), where Rec(K) := {h ∈ X : K + th ⊂ K for all t > 0}, the recession cone of K. For example K itself has the property (R). In the case when X is an Euclidean space it is well-known and important (cf. Lewis and Pang(1997)) that if x ∈ X\K and u ∈ P_{K}(x) the projection of x to K then x−u ∈ N_{K}(u). Writing h for \frac{x−u}{∥x−u∥}, one has h ∈ N_{K}^{1}(u). Moreover, if A is a subset of K with the property (R) then u can be expressed as u = a + c with some a ∈ A, c ∈ Rec(K). Then h is orthogonal to c, a + tc ∈ ∂K and h ∈ N_{K}^{1}(a + tc) for each t ≥ 0. The following lemma is an attempt to generalize the above result to an arbitrary Banach space X where the role of N_{K} is to be replaced by N_{K}(·, γ) with 0 < γ < 1 for our analysis on error bounds.

Lemma 2.1. Let K be a nonempty closed convex subset of a Banach space X and let A be a subset of K with the property (R). Let γ ∈ (0, 1). Then for each x ∈ X \ K there exist a ∈ A and c ∈ Rec(K) such that

a + tc ∈ ∂K and h := \frac{x − a − c}{∥x − a − c∥} ∈ N_{K}^{1}(a + tc, γ), ∀t ∈ [0, +∞).

In particular A ∩ ∂K is nonempty provided that K ≠ X. Moreover, if X is assumed to be a reflexive Banach space then the above conclusion remains true for γ = 1.

Proof. Let x ∈ X \K and r := dist(x, K). Then r > 0 and K ∩int(B(x, r)) = ∅. By the Separation Theorem, there exists x^{∗} ∈ Σ_{X^{∗}} such that

σ_{K}(x^{∗}) ≤ inf{⟨x^{∗}, z⟩ : z ∈ B(x, r)} = ⟨x^{∗}, x⟩ − r.

Let 0 < ε < 1 and take u ∈ K ∩ B(x, r + ε); then

σ_{K}(x^{∗}) − ⟨x^{∗}, u⟩ ≤ ε and ⟨x^{∗}, x − u⟩ ≥ r. (2.3)

By the Phelps-Brondsted-Rockafellar Lemma (cf. Homels (1975), p.165) there exist v ∈ K and v^{∗} ∈ X^{∗} with σ_{K}(v^{∗}) = ⟨v^{∗}, v⟩ such that

∥v − u∥ ≤ \sqrt{ε} and ∥x^{∗} − v^{∗}∥ ≤ \sqrt{ε}. (2.4)

Since A is a subset of K with the property (R), v can be expressed in the form v = a + c for some a ∈ A and c ∈ Rec(K). It follows from a + R_{+}c ⊂ K that

⟨v^{∗}, a + tc⟩ ≤ ⟨v^{∗}, a + c⟩, ∀t > 0;

hence ⟨v^{∗}, c⟩ = 0 and ⟨v^{∗}, a + tc⟩ = σ_{K}(v^{∗}) for all t ≥ 0. In particular, a + tc ∈ ∂K for all t ≥ 0. Let h := \frac{x−v}{∥x−v∥} and w^{∗} := \frac{v^{∗}}{∥v^{∗}∥} (by (2.4), v^{∗} ≠ 0 because ε < 1 and ∥x^{∗}∥ = 1). It remains to show that h ∈ N_{K}(a + tc, γ); to do this, it suffices to show that ⟨w^{∗}, h⟩ ≥ γ. By (2.4) and ∥x^{∗}∥ = 1, one has that

∥x^{∗} − w^{∗}∥ = ∥x^{∗} − \frac{v^{∗}}{∥v^{∗}∥}∥ ≤ |1 − \frac{1}{∥v^{∗}∥}| + \frac{∥x^{∗} − v^{∗}∥}{∥v^{∗}∥}
≤ \frac{|1 − ∥v^{∗}∥| + \sqrt{ε}}{∥v^{∗}∥} ≤ \frac{2\sqrt{ε}}{1 − \sqrt{ε}}.

Noting that ∥x − u∥ ≤ r + ε, it follows from (2.3) and (2.4) that

⟨w^{∗}, x − v⟩ = ⟨w^{∗}, x − u⟩ + ⟨w^{∗}, u − v⟩
≥ ⟨x^{∗}, x − u⟩ − ∥x^{∗} − w^{∗}∥∥x − u∥ − ∥u − v∥
≥ r − \frac{2\sqrt{ε}(r + ε)}{1 − \sqrt{ε}} − \sqrt{ε}.

Since γ < 1 and ∥x − v∥ ≤ ∥x − u∥ + ∥u − v∥ ≤ r + ε + \sqrt{ε}, it follows that

⟨w^{∗}, h⟩ ≥ \frac{r − \frac{2\sqrt{ε}(r+ε)}{1−\sqrt{ε}} − \sqrt{ε}}{r + ε + \sqrt{ε}} > γ,

where the last inequality holds provided that ε > 0 small enough. In the case when X is reflexive, one can find a point v in K ∩ B(x, r). This and the Separation Theorem imply that there exists w^{∗} ∈ Σ_{X^{∗}} such that ⟨w^{∗}, v⟩ = σ_{K}(w^{∗}) and ⟨w^{∗}, x − v⟩ = r. Taking a ∈ A and c ∈ Rec(K) such that v = a + c, it follows as before that a + tc ∈ ∂K and \frac{x−a−c}{∥x−a−c∥} ∈ N_{K}(a + tc) for all t ≥ 0. This completes the proof.

The following lemma taken from Theorem 2.1 in Zheng (2001) provides in particular a sufficient condition for (1.1) to have a local error bound at y_{0} ∈ F (X).

Lemma 2.2. Let F : X → 2^{Y} be a convex multifunction with closed values (i.e., F x is closed subset of Y for each x ∈ X). Let y_{0} ∈ F (X), x_{0} ∈ X, r > 0, δ > 0 and let B_{F} (y_{0}, r) be defined by (2.1). Suppose that B_{F} (y_{0}, r) ⊂ F (B(x_{0}, δ)). Then

dist(x, F^{−1}(y_{0})) ≤ \frac{dist(y_{0}, F x)}{r}(δ + ∥x − x_{0}∥) for all x ∈ X.

3. Sufficient conditions for convex inclusions to have error bounds. In what follows, let X be a Banach space, Y a normed space, F : X → 2^{Y} a convex multifunction and b ∈ F (X). We assume throughout that

F^{−1}b is closed, and A ⊂ F^{−1}b has the property (R).

Let a ∈ F^{−1}b and τ > 0. τ is called a local error bound at a for the convex inclusion (1.3) if there exists δ_{a} > 0 such that for each x ∈ X with ∥x − a∥ < δ_{a},

dist(x, F^{−1}b) ≤ τdist(b, F x). (3.1)

The next two theorems present some sufficient conditions for (1.3) to have global error bounds. They improve some results in Zheng (2001) where X is required to be reflexive.

Theorem 3.1. Let τ > 0. Suppose that τ is a local error bound for the inclusion problem (1.3) at each a ∈ A ∩ ∂(F^{−1}b). Then τ is a global error bound for (1.3), namely (3.1) holds for all x ∈ X.

Proof. Let x ∈ X. To prove (3.1), we may suppose that dist(x, F^{−1}b) > 0. Let γ ∈ (0, 1). By Lemma 2.1 there exist a ∈ A ∩ ∂(F^{−1}b) and c ∈ Rec(F^{−1}b) such that

h := \frac{x − a − c}{∥x − a − c∥} ∈ N_{F^{−1}b}^{1}(a + tc, γ) ∀t ≥ 0.

Thus, by definition and (2.2),

dist(a + tc + sh, F^{−1}b) ≥ γs, ∀s, t ∈ [0, +∞).

6 Kung Fu Ng and Xi Yin Zheng

Setting s = t∥x − a − c∥, one has that dist(a + t(x − a), F^{−1}b) ≥ γt∥x − a − c∥ ≥ γtdist(x, F^{−1}b) ∀t ≥ 0, (3.2) where the last inequality holds because a + c ∈ A + Rec(F^{−1}b) = F^{−1}b by the property (R) of A. On the other hand, since τ is assumed to be a locally error bound at a, one can take t ∈ (0, 1) small enough such that dist(a + t(x − a), F^{−1}b) ≤ τdist(b, F (a + t(x − a))). (3.3) Since F is convex and a ∈ F^{−1}b,

dist(b, F (a + t(x − a))) ≤ dist(b, (1 − t)F (a) + tF (x))
≤ (1 − t)dist(b, F a) + tdist(b, F x)
= tdist(b, F x).

It follows from (3.2) and (3.3) that γdist(x, F^{−1}b) ≤ τdist(b, F x). Letting γ → 1^{−}, (3.1) is seen to hold. Theorem 3.2. Let F have closed values. Let τ > 0. Suppose that for each a ∈ A ∩ ∂(F^{−1}b) there exists r_{a} > 0 such that B_{F} (b, r_{a}) ⊂ F (B(a, τr_{a})). (3.4) Then τ is an error bound for (1.3). Proof. Let x ∈ X with dist(b, F x) > 0 and γ ∈ (0, 1). As in the proof of Theorem 3.1, there exists a ∈ A ∩ ∂(F^{−1}b) such that for all t ∈ (0, 1], (3.2) holds: dist(a + t(x − a), F^{−1}b) ≥ γtdist(x, F^{−1}b). (3.5) By virtue of (3.4), Lemma 2.2 implies that

dist(a + t(x − a), F^{−1}b) ≤ \frac{dist(b, F (a + t(x − a)))}{r_{a}}(τr_{a} + t∥x − a∥)
≤ \frac{tdist(b, F x)}{r_{a}}(τr_{a} + t∥x − a∥)

for all t > 0. This and (3.5) imply that

γdist(x, F^{−1}b) ≤ dist(b, F x)(τ + \frac{t∥x − a∥}{r_{a}})

for each t ∈ (0, 1]. Letting t → 0 and γ → 1^{−}, (3.1) is seen to hold. This completes the proof.

We end this section with a result giving a sufficient and necessary condition for a nonconvex multifunction to have a (global) error bound. Theorem 3.3. Let G : X → 2^{Y} be a closed multifunction (not necessarily convex) and G denote the graph of G. Let b ∈ Y. Then there exists τ > 0 such that dist(x, G^{−1}b) ≤ τdist(b, Gx), ∀x ∈ X (3.6) if and only if there exists τ′ > 0 such that for each x ∈ X with (x, b) ∉ G there exists x′ ∈ X \ {x} satisfying

dist((x′, b), G) ≤ dist((x, b), G) − \frac{1}{τ′} ∥x − x′∥. (3.7)

Proof. The sufficiency part: Suppose that (3.7) holds and let

ϕ(x) := dist((x, b), G), ∀x ∈ X.

Then ϕ is continuous on X. By assumption, for each x ∈ X with ϕ(x) > 0 there exists x′ ∈ X \ {x} such that

ϕ(x′) ≤ ϕ(x) − \frac{1}{τ′} ∥x − x′∥.

This and Theorem 2 in [Hamel (1994)] imply that ϕ^{−1}(0) (= G^{−1}b since G is closed) is nonempty and

dist(x, G^{−1}b) ≤ τ′dist((x, b), G) ∀x ∈ X.

Since it is easy to verify that dist((x, b), G) ≤ dist(b, Gx), it follows that (3.6) holds with τ = τ′. The necessity part: Let τ > 0 such that (3.6) holds. Let η > 1 and x ∉ G^{−1}b. Pick a ∈ G^{−1}b such that

ηdist(x, G^{−1}b) > ∥x − a∥

and pick u ∈ X such that

ηdist((x, b), GraphG) > (∥x − u∥ + dist(b, Gu))
≥ (∥x − u∥ + \frac{1}{τ} dist(u, G^{−1}b))
≥ \frac{1}{(1 + τ)}(∥x − u∥ + dist(u, G^{−1}b))
≥ \frac{1}{(1 + τ)}dist(x, G^{−1}b),

where we have used (3.6) and the triangle inequality. Thus

dist((x, b), G) ≥ \frac{1}{η^{2}(1 + τ)}∥x − a∥.

Since (a, b) ∈ G, (3.7) is seen to hold with x′ = a and τ′ = η^{2}(1 + τ).

4. Characterizations for convex inclusions to have error bounds. As in theorems 3.1 and 3.2, let F be a convex multifunction from X to Y. Let x ∈ X, y ∈ F x and let DF (x, y) denote the contingent derivative of F at (x, y), that is, DF (x, y) is a (positively homogeneous and subadditive) multifunction with

Graph(DF (x, y)) = T_{Graph(F)}(x, y),

where T_{Graph(F)}(x, y) is the tangent cone of Graph(F) at (x, y). It is known (see Aubin and Frankowska (1990), Proposition 5.1.4) that for each h ∈ X,

DF (x, y)(h) = \{v ∈ Y : lim inf_{t→0^{+},h′→h} dist (v, \frac{F (x + th′) − y}{t} ) = 0\} , (4.1)

and in particular that v ∈ DF (x, y)(h) if and only if there exist sequences {t_{n}}, {h_{n}} and {y_{n}} such that t_{n} → 0^{+}, h_{n} → h, y_{n} ∈ F (x + t_{n}h_{n}) (∀n) and \frac{y_{n}−y}{t_{n}} → v. Another kind of derivative is D̂F (x, y) which is defined by

D̂F (x, y)(h) := \{v ∈ Y : lim inf_{t→0^{+}} dist (v, \frac{F (x + th) − y}{t} ) = 0\} , ∀h ∈ X.

Clearly D̂F (x, y)(h) ⊂ DF (x, y)(h). Since F is convex, it is easy to verify that t ↦ dist(v, \frac{F (x+th)−y}{t}) is increasing and hence

D̂F (x, y)(h) := \{v ∈ Y : lim_{t→0^{+}} dist (v, \frac{F (x + th) − y}{t} ) = 0\} . (4.2)

For reasons given below, D̂F (x, y) may be referred to as the Dini-derivative of F at (x, y) in the direction h. Let f : X → R ∪ {+∞} be a convex function and F be defined by F x = [f(x), +∞) for each x ∈ X. Then for each x ∈ X with f(x) ≠ +∞,

D̂F (x, f(x))(h) = d^{+}f(x)(h) + R_{+} ∀h ∈ X, (4.3)

where d^{+}f(x) denotes the Dini-derivative of at x, namely,

d^{+}f(x)(h) := lim_{t→0^{+}} \frac{f(x + th) − f(x)}{t}.

Indeed, by (4.2), v ∈ D̂F (x, f(x))(h) is equivalent to

lim_{t→0^{+}} dist (v, \frac{f(x + th) + R_{+} − f(x)}{t}) = 0.

Note that for each t > 0,

dist (v, \frac{f(x + th) + R_{+} − f(x)}{t}) = dist (v, \frac{f(x + th) − f(x)}{t} + R_{+})
= dist (\frac{f(x + th) − f(x)}{t}, v − R_{+});

it follows by passing to the limits that

lim_{t→0^{+}} dist (v, \frac{f(x + th) + R_{+} − f(x)}{t}) = lim_{t→0^{+}} dist (\frac{f(x + th) − f(x)}{t}, v − R_{+})
= dist ( lim_{t→0^{+}} \frac{f(x + th) − f(x)}{t}, v − R_{+})
= dist(d^{+}f(x)(h), v − R_{+})
= dist(v, d^{+}f(x)(h) + R_{+}).

Therefore, v ∈ D̂F (x, f(x))(h) is equivalent to v ∈ d^{+}f(x)(h) + R_{+}. This shows that (4.3) holds. The third kind of derivative of F is d̃F defined by

d̃F (x, y)(h) := lim_{t→0^{+}} \frac{dist((x + th, y), GraphF) − dist((x, y), GraphF)}{t}

for any (x, y) ∈ X × Y and h ∈ X; that is, d̃F (x, y)(h) = d^{+}ϕ(0), where ϕ is the real-valued convex function of a real variable defined by

ϕ(t) = dist((x + th, y), GraphF), ∀t ≥ 0.

Note that d̃F (x, y)(h) ∈ (−∞, +∞) while D̂F (x, y)(h) ⊂ DF (x, y)(h) ⊂ Y. To emphasize this distinction, d̃F will be referred to as the numerical derivative of F. Another distinction is that the definition of d̃F (x, y)(h) makes sense (and in fact is of importance for our subsequent study) even if (x, y) does not lie in the graph of F.

Lemma 4.1. Let X be a Banach space, Y a normed space and let F : X → 2^{Y} be a convex multifunction. Let (u, w) ∈ GraphF, h ∈ X with ∥h∥ = 1 and δ > 0. Suppose that either

(a) δ ≤ inf{∥v∥ : v ∈ DF (u, w)(h)} or

(b) Y is a reflexive Banach space and δ ≤ inf{∥v∥ : v ∈ D̂F (u, w)(h)}. Then

δt ≤ dist(w, F (u + th)), ∀t ≥ 0. (4.4)

Proof. Since F is convex,

\frac{1}{t}(\{u + th\} × F (u + th) − (u, w)) ⊂ T_{GraphF} (u, w) ∀t ≥ 0,

that is,

\frac{F (u + th) − w}{t} ⊂ DF (u, w)(h), ∀t ≥ 0.

It follows that if (a) holds then

δt ≤ dist(w, F (u + th)), ∀t ≥ 0.

Next we consider the case (b). Since t ↦ dist(w, F (u + th)) is a convex function (by convexity of F) and takes value zero at t = 0, it follows that t ↦ \frac{dist(w,F (u+th))}{t} is increasing on (0, +∞). In particular, (4.4) holds trivially if lim_{t→0^{+}} \frac{dist(w,F (u+th))}{t} = +∞. In what follows, we assume that there exists r ∈ [0, +∞) such that

(4.5) r = lim_{t→0^{+}} \frac{dist(w, F (u + th))}{t}; thus r = inf_{t>0} \frac{dist(w, F (u + th))}{t}.

Let t_{n} = \frac{1}{n}. Then lim_{n→∞} \frac{dist(w,F (u+t_{n}h))}{t_{n}} = r. For each n, take y_{n} ∈ F (u + t_{n}h) such that

∥y_{n} − w∥ < dist(w, F (u + t_{n}h)) + t_{n}^{2}.

Note that lim_{n→∞} \frac{∥y_{n}−w∥}{t_{n}} = r and in particular \{\frac{y_{n}−w}{t_{n}} \} is a bounded sequence in Y. Since Y is reflexive and by the Eberlein-Smulian Theorem (cf. Homels (1975), p.147), we may assume without loss of generality that \frac{y_{n}−w}{t_{n}} →^{w} v ∈ Y (passing to a subsequence if necessary), where w denotes the weak topology. By the lower w-semicontinuity of the norm, one has that

r ≥ ∥v∥. (4.6)

Since F is convex and w ∈ F u, it is easy to verify that

\frac{F (u + t_{n}h) − w}{t_{n}} ⊂ \frac{F (u + t_{n+1}h) − w}{t_{n+1}} (because t_{n} > t_{n+1}).

Thus, D := ⋂_{k=1}^{∞} ⋃_{n=k}^{∞} \frac{F (u+t_{n}h)−w}{t_{n}} is convex and \frac{y_{n}−w}{t_{n}} ∈ D for each n. Since the w-closure of a convex set coincides with its norm-closure (cf. Homels (1975), p.66), it follows that v ∈ cl(D). Hence there exists a sequence {d_{k}} in D such that lim_{k→} d_{k} = v. Since

d_{k} ∈ D ⊂ ⋃_{n=k}^{∞} \frac{F (u + t_{n}h) − w}{t_{n}} ,

there exists a natural number n_{k} ≥ k such that d_{k} ∈ \frac{F (u+t_{n_{k}} h)−w}{t_{n_{k}}}. Thus

dist (v, \frac{F (u + t_{n_{k}}h) − w}{t_{n_{k}}} ) → 0 and t_{n_{k}} → 0.

This shows that v ∈ D̂F (u, w)(h), it follows from assumption (b) together with (4.5) and (4.6) that

δ ≤ ∥v∥ ≤ r ≤ \frac{dist(w, F (u + th))}{t}, ∀t > 0.

Thus (4.4) is seen to hold.

Remark. From the above proof, one can see that, in the case (b),

D̂F (u, w)(h) = \{v ∈ X : ∃t_{n} → 0^{+} and y_{n} ∈ F (u + t_{n}h) such that \frac{y_{n} − w}{t_{n}} →^{w} v\}.

The remaining results to be considered in this section all concern with the convex inclusion problem (1.3); we fix the following notations: X is a Banach space, Y a normed space, b ∈ Y and F : X → 2^{Y} is a convex multifunction. We always assume that

(4.7) b ∈ F (X) and F^{−1}b is closed.

Moreover, A will always denote a subset of F^{−1}b with the property (R), that is,

A + Rec(F^{−1}b) = F^{−1}b. (4.8)

We write A_{ε} for the set {x ∈ X : dist(x, A) < ε}. All under these umbrella assumptions and respectively in terms of the derivatives DF, D̂F and d̃F of F, the next three theorems provide answers to the question when the inclusion problem (1.3) has an error bound.

Theorem 4.1. The following statements are equivalent.

(i) The inclusion (1.3) has an error bound τ > 0. (ii) For each γ ∈ (0, 1] there exists δ > 0 such that

dist(0, DF (a, b)(h)) ≥ δ, ∀a ∈ ∂(F^{−1}b), h ∈ N_{F^{−1}b}^{1}(a, γ). (4.9)

(iii) There exist γ ∈ (0, 1) and δ > 0 such that (4.9) holds. (iv) There exist δ, ε > 0 and γ ∈ (0, 1) such that

dist(0, DF (a, b)(h)) ≥ δ ∀a ∈ A_{ε} ∩ ∂(F^{−1}b), h ∈ N_{F^{−1}b}^{1}(a, γ). (4.10)

Moreover if X is assumed to be reflexive then each of (i)–(iv) is also equivalent to

(v) Same as (iv) but γ = 1, that is, there exist δ, ε > 0 such that

dist(0, DF (a, b)(h)) ≥ δ, ∀a ∈ A_{ε} ∩ ∂(F^{−1}b), h ∈ N_{F^{−1}b}^{1}(a).

Proof. (i)⇒(ii): Let γ ∈ (0, 1]. We will show that (ii) holds with δ := \frac{γ}{τ}. Indeed, if not, then there exist a ∈ ∂(F^{−1}b), h ∈ N_{F^{−1}b}^{1}(a, γ) and v ∈ DF (a, b)(h) such that ∥v∥ < \frac{γ}{τ}. By definition of N_{F^{−1}b}(a, γ), there exists x^{∗} ∈ Σ_{X^{∗}} such that

⟨x^{∗}, a⟩ = σ_{F^{−1}b}(x^{∗}) and ⟨x^{∗}, h⟩ ≥ γ.

Take ε ∈ (0, 1) small enough such that

∥v∥ < (1 − 2ε)\frac{γ}{τ} .

By (4.1), one has that there exist h′ ∈ X, v′ ∈ Y and t′ > 0 such that

∥h − h′∥ < εγ, ∥v − v′∥ < \frac{εγ}{τ} and (h′, v′) ∈ \frac{Graph(F) − (a, b)}{t′}.

Then

⟨x^{∗}, h′⟩ > (1 − ε)γ, ∥v′∥ < \frac{(1 − ε)γ}{τ} and b + t′v′ ∈ F (a + t′h′).

It follows from (i) that

dist(a + t′h′, F^{−1}b) ≤ τdist(b, F (a + t′h′)) ≤ τt′∥v′∥ < t′(1 − ε)γ. (4.11)

Let L := {x ∈ X : ⟨x^{∗}, x⟩ ≤ σ_{F^{−1}b}(x^{∗})}. Then, F^{−1}b ⊂ L and by a standard result,

dist(z, L) = ⟨x^{∗}, z⟩ − σ_{F^{−1}b}(x^{∗}), ∀z ∈ X \ L.

Hence

dist(a + t′h′, F^{−1}b) ≥ dist(a + t′h′, L)
= ⟨x^{∗}, a + t′h′⟩ − σ_{F^{−1}b}(x^{∗})
= ⟨x^{∗}, t′h′⟩ ≥ t′(1 − ε)γ,

contradicting (4.11). Therefore (i)⇒(ii). It is trivial that (ii)⇒(iii)⇒(iv). Assuming that (iv) holds, we will establish (i) by showing that (4.10) with γ ∈ (0, 1) implies (i) with τ := \frac{1}{δ}. Let x ∈ X with dist(x, F^{−1}b) > 0. By Lemma 2.1 (applied to F^{−1}b for K), there exist a ∈ A, c ∈ Rec(F^{−1}b) such that for all t ≥ 0,

a + tc ∈ ∂(F^{−1}b) and h := \frac{x − a − c}{∥x − a − c∥} ∈ N_{F^{−1}b}^{1}(a + tc, γ). (4.12)

Take t_{0} ∈ (0, 1) small enough such that ∥t_{0}c∥ < ε; thus a + t_{0}c ∈ A_{ε} ∩ ∂(F^{−1}b). Then, by (4.10), dist(0, DF (a + t_{0}c, b)(h)) ≥ δ and it follows from Lemma 4.1 (applying to u = a + t_{0}c and w = b) that

δt ≤ dist(b, F (a + t_{0}c + th)), ∀t ≥ 0.

Putting t := t_{0}∥x − a − c∥, we have

δt_{0}∥x − a − c∥ ≤ dist(b, F (a + t_{0}(x − a))) ≤ t_{0}dist(b, F x),

where the last inequality holds because b ∈ F a and F is convex. Therefore, as a + c ∈ ∂(F^{−1}b) ⊂ F^{−1}b,

dist(x, F^{−1}b) ≤ ∥x − a − c∥ ≤ \frac{1}{δ}dist(b, F x).

Therefore, (i)–(iv) are equivalent. Since (i)⇒(ii)⇒(v), it remains to prove that (v)⇒(i) (under the assumption that X is reflexive). This is done in the same way as in the above proof for (iv)⇒(i) except that we can choose our h in (4.12) to satisfy the stronger requirement that h ∈ N_{F^{−1}b}^{1}(a+tc, γ) with γ = 1 for t ≥ 0. Thanks to the reflexivity of X, this can be accomplished by virtue of the last part of Lemma 2.1.

Remark. Let τ^{∗} and δ(γ, ε) be defined by

τ^{∗} := inf{τ ∈ (0, +∞) : τ is an error bound of (1.3)}

and

δ(γ, ε) := inf{dist(0, DF (z, b)(h)) : z ∈ A_{ε} ∩ ∂(F^{−1}b), h ∈ N_{F^{−1}b}^{1}(a, γ)},

where γ ∈ (0, 1) and ε > 0. Note that (1.3) has an error bound if and only if τ^{∗} is finite (τ^{∗} is the smallest error bound for (1.3)). Here and throughout we adopt the convention that infimum over the empty set and the distance of any point to the empty set are +∞. From the definitions it is easy to see that γ ↦ N_{F^{−1}b}(z, γ) is decreasing (with respect to the set-inclusion) and hence that γ ↦ δ(γ, ε) is increasing; thus

sup{δ(γ, ε) : 0 < γ < 1} = lim_{γ→1^{−}} δ(γ, ε) ≤ δ(1, ε).

Corollary 4.1. The following assertions hold.

(i) τ^{∗} ≤ [δ(γ, ε)]^{−1} ≤ \frac{τ^{∗}}{γ} , ∀γ ∈ (0, 1), ε > 0.

(ii) τ^{∗} = [ lim_{γ→1^{−}} δ(γ, ε)]^{−1}, ∀ε > 0.

Proof. (i) has already been established in the proof of Theorem 4.1 in the case when τ^{∗} is finite (equivalently when δ(γ, ε) > 0 for some ε > 0 and for some (and hence all) γ ∈ (0, 1)). When τ^{∗} is infinite, δ(γ, ε) must be zero for all γ ∈ (0, 1) and ε > 0. Thus (i) holds in any case. (ii) follows from (i) immediately.

Similarly, we have:

Corollary 4.2. If X is assumed to be reflexive then τ^{∗} = [δ(1, ε)]^{−1} for any ε > 0.

Corollary 4.2 is inexact if the reflexivity assumption is dropped. For example, let X be a nonreflexive Banach space (e.g., X = l^{1}); then by the James Theorem (cf. Homels (1975), p.157), there exists x^{∗} ∈ X^{∗} with ∥x^{∗}∥ = 1 such that

⟨x^{∗}, x⟩ < ∥x∥, ∀x ∈ X \ {0}.

Let K := {x ∈ X : ⟨x^{∗}, x⟩ ≤ 0}; then each supporting functional of K must be a multiple of x^{∗} and it follows that

N_{K}^{1}(z) = ∅, ∀z ∈ ∂K. (4.13)

Define F : X → 2^{R} by F x = ⟨x^{∗}, x⟩ + R_{+} for all x ∈ X. Then F is a closed convex multifunction. Letting b = 0, it is easy to verify that F^{−1}b = K and 1 is the least error of the inclusion b ∈ F x. But (4.13) implies that δ(1, ε) = +∞ for each ε > 0 and hence τ^{∗} = 1 ≠ [δ(1, ε)]^{−1}.

The next result shows that, when Y is reflexive, Theorem 4.1 can be strengthened by replacing the contingent derivative DF with the Dini-derivative D̂F. In the following Theorem 4.2, (ii^{∗}), (iii^{∗}), (iv^{∗}) and (v^{∗}) denote the corresponding statements of (ii), (iii), (iv) and (v) in Theorem 4.1 but with DF replaced by D̂F. Here and in the following Theorem 4.2 including its proof, (i)–(v) are referred to the statements of Theorem 4.1.

Theorem 4.2. Suppose, in addition to (4.7) and (4.8), that Y is reflexive. Then (i), (ii^{∗}), (iii^{∗}) and (iv^{∗}) are equivalent to each other. Moreover, if X is also assumed to be reflexive then they are equivalent to (v^{∗}).

Proof. By Theorem 4.1, (i)⇒(ii)⇒ (ii^{∗}) where the second implication holds because D̂F (a, b)(h) ⊂ DF (a, b)(h). It is trivial that (ii^{∗}) ⇒ (iii^{∗}) and (iii^{∗}) ⇒ (iv^{∗}). The proof of (iv^{∗}) ⇒(i) is the same as that for (iv)⇒(i) in Theorem 4.1 except that when apply Lemma 4.1 we use part (b) instead of part (a). Part (b) is applicable because Y is reflexive. Similarly, if X is assumed to be reflexive the proof for (v)⇒(i) can easily be modified to show that (v^{∗}) ⇒(i). Since it is clear that (ii^{∗}) ⇒ (v^{∗}), the proof is completed.

For γ ∈ (0, 1) and ε > 0, let

δ̂(γ, ε) := inf{dist(0, D̂F (z, b)(h)) : z ∈ A_{ε} ∩ ∂(F^{−1}b), h ∈ N_{F^{−1}b}^{1}(a, γ)}.

Corollary 4.3. Assumptions are as in Theorem 4.2. Then one has:

(i) τ^{∗} ≤ [δ̂(γ, ε)]^{−1} ≤ \frac{τ^{∗}}{γ} , ∀γ ∈ (0, 1), ε > 0.

(ii) τ^{∗} = [ lim_{γ→1^{−}} δ̂(γ, ε)]^{−1}, ∀ε > 0.

We have noted that D̂F (a, b)(h) ⊂ DF (a, b)(h). The following example shows that the inclusion may be proper even when X and Y are finite dimensional.

Define F : R^{2} → 2^{R} by F x = [−1, 1] if ∥x∥ ≤ 1 and F x = ∅ if ∥x∥ > 1. It is clear that GraphF = B_{R^{2}} × [−1 1], where B_{R^{2}} is the unit ball of R^{2} under the Euclidean norm. Let a = (1, 0) and h = (0, 1). Then

T_{GraphF} (a, 0) = R_{−} × R × R;

hence DF (a, 0)(h) = R. Noting that F (a + th) = ∅ for each t > 0, it is clear from definition that D̂F (a, 0)(h) = ∅.

The next result is expressed in terms of the numerical derivative d̃F. We continue to assume (4.7) and (4.8) for the remaining two theorems in this section.

Theorem 4.3. The following statements are equivalent.

(i) (1.3) has an error bound τ > 0. (ii) For each γ ∈ (0, 1] there exists δ > 0 such that

inf{d̃F (a, b)(h) : a ∈ ∂(F^{−1}b) and h ∈ N_{F^{−1}b}^{1}(a, γ)} ≥ δ.

(iii) There exist γ ∈ (0, 1) and δ > 0 such that

inf{d̃F (a, b)(h) : a ∈ ∂(F^{−1}b) and h ∈ N_{F^{−1}b}^{1}(a, γ)} ≥ δ.

(iv) There exist γ ∈ (0, 1) and δ, ε > 0 such that

inf{d̃F (a, b)(h) : a ∈ A_{ε} ∩ ∂(F^{−1}b) and h ∈ N_{F^{−1}b}^{1}(a, γ)} ≥ δ.

Moreover, if F is assumed to be closed, then each of (i)–(iv) is also equivalent to:

(v) There exists δ > 0 such that each x ∈ X \ F^{−1}b has the property that

d̃F (x, b)(h) ≤ −δ for some unit vector h ∈ X.

Remark. Theorem 4.3 differs from Theorems 4.1 and 4.2 especially in following two aspects.

(1) The correlation of the constant τ in (i) and the constants δ in the other parts of Theorem 4.3 is not as simple as that appeared in Corollaries 4.1, 4.1 and 4.3.

(2) There is no counter-part of Theorem 4.3 (v) in Theorems 4.1 and 4.2. Loosely speaking, (v) ensures that each point outside the solution set F^{−1}b can move along a certain direction with negative “rate of change” bounded away from zero. Proof of Theorem 4.3. (i)⇒(ii): Let a ∈ ∂(F^{−1}b), γ ∈ (0, 1] and h ∈ N_{F^{−1}b}^{1}(a, γ). Then, by (2.2),

γt ≤ dist(a + th, F^{−1}b), ∀t > 0. (4.14)

Let η > 1. By the proof of the necessity part of Theorem 3.3,

\frac{1}{(1 + τ)}dist(a + th, F^{−1}b) ≤ ηdist((a + th, b), GraphF), ∀t > 0.

It follows from (4.14) that

\frac{γ}{η(1 + τ)} ≤ \frac{dist((a + th, b), GraphF)}{t}.

Letting t → 0^{+} and noting that (a, b) ∈ GraphF, this implies that d̃F (a, b)(h) ≥ \frac{γ}{η(1+τ)}. This shows that (ii) holds with δ = \frac{γ}{η(1+τ)}. (ii)⇒(iii)⇒(iv) are trivial. (iv)⇒(i): We will show that \frac{1}{δ} is an error bound for (1.3). By Theorem 3.1, it is sufficient to show that \frac{1}{δ} is a local error bound for (1.3) at each a ∈ A ∩ ∂(F^{−1}b). To do this, let a ∈ A ∩ ∂(F^{−1}b) and x ∈ X with ∥x − a∥ < \frac{γε}{2}. We can assume that x ∉ F^{−1}b. By Lemma 2.1 there exists a_{0} ∈ ∂(F^{−1}b) such that h := \frac{x−a_{0}}{∥x−a_{0}∥} ∈ N_{F^{−1}b}^{1}(a_{0}, γ). Thus, by (2.2),

γ∥x − a_{0}∥ ≤ dist(a_{0} + ∥x − a_{0}∥h, F^{−1}b) = dist(x, F^{−1}b) ≤ ∥x − a∥ < \frac{γε}{2},

and so ∥x − a_{0}∥ < \frac{ε}{2}. Hence ∥a_{0} − a∥ ≤ ∥x − a∥ + ∥x − a_{0}∥ < ε. This shows that a_{0} ∈ A_{ε} ∩ ∂(F^{−1}b). It follows from (iv) that d̃F (a_{0}, b)(h) ≥ δ, that is, d^{+}ϕ(0) ≥ δ where ϕ is defined by

ϕ(t) = dist((a_{0} + th, b), GraphF), ∀t ≥ 0.

By the convexity of F, ϕ is convex so

\frac{ϕ(t)}{t} ≥ d^{+}ϕ(0) ≥ δ, ∀t > 0

because ϕ(0) = 0 as (a_{0}, b) ∈ GraphF. Putting t = ∥x − a_{0}∥, we have that

\frac{dist((a_{0} + ∥x − a_{0}∥h, b), GraphF)}{∥x − a_{0}∥} ≥ δ.

Therefore,

δdist(x, F^{−1}b) ≤ δ∥x − a_{0}∥ < dist((x, b), GraphF) ≤ dist(b, F x).

This show that \frac{1}{δ} is a local error bound for (1.3) at a. (v)⇒(i): (Under the assumption that F is closed). Assuming (v), take any δ′ ∈ (0, δ). Let x ∈ X \ F^{−1}b and by (v) take a unit vector h so that d̃F (x, b)(h) < −δ′; hence

\frac{dist((x + th, b), Graph(F)) − dist((x, b), Graph(F))}{t} < −δ′

for sufficiently small t > 0. Letting x′ = x + th, we see that (3.7) of Theorem 3.3 holds with τ′ = \frac{1}{δ′} (and F in place of G). Therefore (3.6) holds and so does (i). (iii)⇒(v): Let x ∈ X \ F^{−1}b and γ ∈ (0, 1). By Lemma 2.1, we can take a ∈ ∂(F^{−1}b) such that h := \frac{x−a}{∥x−a∥} ∈ N_{F^{−1}b}(a, γ). By (iii) d̃F (a, b)(h) ≥ δ. Define the convex function ϕ : R → R by ϕ(t) := dist((a+th, b), Graph(F)), and use d_{−}ϕ and d^{+}ϕ respectively to denote the left and the right derivatives of ϕ. By the convexity, −(d_{−}ϕ)(t_{0}) ≤ −(d^{+}ϕ)(0) for each t_{0} > 0. With t_{0} := ∥x − a∥, the above inequality reads d̃F (x, b)(−h) ≤ −d̃F (a, b)(h) ≤ −δ. Thus (v) is seen to hold.

Remark. We have actually proved that (v)⇒(i) is true for any (not necessarily convex) closed multifunction F.

Definition 4.1. F is said to satisfy the Slater condition at b if there exist x_{0} ∈ X, r > 0 and δ > 0 such that

B(b, r) ⊂ F (x_{0} + δB_{X}). (4.15)

Theorem 4.4. Suppose, in addition to (4.7) and (4.8), that F has closed values. Further suppose that F satisfies the Slater condition at b. Then the following statements are equivalent.

(i) There exists an error bound for inclusion (1.3). (ii) There exist τ > 0 and r > 0 such that τ is a local error bound for inclusion problem (1.3) at each point of the set {a ∈ A ∩ ∂(F^{−1}b) : ∥a∥ > r}. (iii) There exist ε > 0 and γ ∈ (0, 1) such that

lim inf_{∥a∥→∞,a∈A_{ε}∩∂(F^{−1}b)} inf{dist(0, DF (a, b)(h)) : h ∈ N_{F^{−1}b}^{1}(a, γ)} ≠ 0.

Moreover, if Y is assumed to be reflexive then each of (i), (ii) and (iii) is equivalent to: (iv) Same statement as (iii) but DF is replaced by D̂F.

Remark. If A is bounded then so is A_{ε} and hence the lower limits in (iii) and in (iv) are +∞; thus (iii) and (iv) hold trivially. Consequently (1.1) always has an error bound if A is bounded, and F satisfies the Slater condition at b. Proof of Theorem 4.4. By Theorems 4.1 and 4.2, (i) implies (iii) and (iv). Note also that (i)⇒(ii) holds trivially. Since F has closed values and satisfies the Slater condition at b, Lemma 2.2 implies that for each α > 0 there exists τ_{α} such that

dist(x, F^{−1}b) ≤ τ_{α}dist(b, F x), ∀x ∈ X with ∥x∥ ≤ α. (4.16)

To prove that (ii)⇒(i), let τ and r be as in (ii). Let τ′ = max{τ, τ_{r+1}}. Then τ′ is an error bound for the inclusion problem (1.3). By Theorem 3.1, to prove this assertion it suffices to show that τ′ is a local error bound for (1.3) at each point a of A ∩ ∂(F^{−1}b). In view of (ii), this is indeed the case if the point a satisfies the condition that ∥a∥ > r. It remains to consider the case when ∥a∥ ≤ r. Let x ∈ B(a, 1). Then ∥x∥ ≤ r + 1 and it follows from (4.16) that

dist(x, F^{−1}b) ≤ τ_{r+1}dist(b, F x) ≤ τ′dist(b, F x),

showing that τ′ is an error bound for (1.3) on the neighborhood B(a, 1) of a, as required to show. (iii)⇒(i): Suppose that (iii) holds. Then there exists δ > 0 and r > 0 such that for each a ∈ A_{ε} ∩ ∂(F^{−1}b) with ∥a∥ > r,

inf{dist(0, DF (a, b)(h) : h ∈ N_{F^{−1}b}^{1}(a, γ)} > δ. (4.17)

Let τ = max\{\frac{τ_{r+1}}{γ} , \frac{1}{δ}\}. Then (i) holds with this τ. To see this, let x ∈ X and we may assume that dist(x, F^{−1}b) > 0. By Lemma 2.1, there exist a ∈ A, c ∈ Rec(F^{−1}b) and t_{0} ∈ (0, 1) (small enough) such that a + t_{0}c ∈ A_{ε} ∩ ∂(F^{−1}b), t_{0}∥x − z∥ < 1 and h ∈ N_{F^{−1}b}^{1}(a + t_{0}c, γ), where h := \frac{x−z}{∥x−z∥} and z = a + c. We subdivide into two cases: 1) ∥a + t_{0}c∥ ≤ r and 2) ∥a + t_{0}c∥ > r. 1): In this case, ∥(a + t_{0}c + t_{0}∥x − z∥h)∥ < r + 1 and it follows from (4.16) that

dist(a + t_{0}c + t_{0}∥x − z∥h, F^{−1}b) ≤ τ_{r+1}dist(b, F (a + t_{0}c + t_{0}∥x − z∥h)).

Noting that a + t_{0}c + t_{0}∥x − z∥h = a + t_{0}(x − a) and

γt_{0}∥x − z∥ ≤ dist(a + t_{0}c + t_{0}∥x − z∥h, F^{−1}b),

it follows that

γt_{0}∥x − z∥ ≤ τ_{r+1}dist(b, F (a + t_{0}(x − a))) ≤ τ_{r+1}t_{0}dist(b, F x),

where the last inequality holds by the convexity of F and b ∈ F a. It follows from dist(x, F^{−1}b) ≤ ∥x − z∥ that

dist(x, F^{−1}b) ≤ \frac{τ_{r+1}}{γ} dist(b, F x) ≤ τdist(b, F x).

2): In this case, (4.17) implies that dist(0, DF (a + t_{0}c, b)(h)) > δ and it follows from Lemma 4.1 (applying to a + t_{0}c, b in place of u, w) that

tδ ≤ dist(b, F (a + t_{0}c + th)) ∀t ≥ 0.

Putting t := t_{0}∥x − z∥ and noting that a + t_{0}c + t_{0}∥x − z∥h = a + t_{0}(x − a), one has that

t_{0}∥x − z∥ ≤ \frac{1}{δ}dist(b, F (a + t_{0}(x − a))) ≤ \frac{t_{0}}{δ} dist(b, F x).

Therefore, dist(x, F^{−1}b) ≤ \frac{1}{δ}dist(b, F x). Combining 1) and 2), one has that dist(x, F^{−1}b) ≤ τdist(b, F x), verifying (i). (iv)⇒(i): Assume that Y is reflexive. The proof given above for (iii)⇒(i) can easily be adopted here but we apply part (b) of Lemma 4.1 in place of part (a).

5. Applications to convex functions. In this section, we apply results in sections 3 and 4 to study error bounds for extended real-valued convex functions on Banach spaces. Throughout this section, X denotes a Banach space, f denotes a proper convex (not necessarily lower semicontinuous) function from X into R ∪ {+∞}, and S := {x ∈ X : f(x) ≤ 0}. We always assume that

(5.1) S is a closed nonempty set in X.

A denotes a subset of S with the property (R): A + Rec(S) = S. To relate to our studies made in the preceding sections, we assume for the remaining part of the paper that F : X → 2^{R} is defined by

F x = [f(x), +∞), ∀x ∈ X.

Then F is a convex multifunction with closed values, dist(0, F x) = [f(x)]_{+} for each x ∈ X and

S = F^{−1}0. (5.2)

Thus for τ ≥ 0 and x ∈ X,

(5.3) dist(x, S) ≤ τ[f(x)]_{+} if and only if dist(x, F^{−1}0) ≤ τdist(0, F x).

Note also that f satisfies the Slater condition if and only if F satisfies the Slater condition at 0. Indeed if f(x_{0}) < −r for some r > 0, then

[−r, r] ⊂ [−r, +∞) ⊂ F (x_{0}) ⊂ F (B(x_{0}, δ))

for any δ > 0.

Theorem 5.1. Let ε > 0. For each γ ∈ (0, 1), let

δ_{γ}(ε) := inf{d^{+}f(a)(h) : a ∈ A_{ε} ∩ ∂S and h ∈ N_{S}^{1}(a, γ)}. (5.4)

Let δ(ε) := lim_{γ→1^{−}} δ_{γ}(ε) and

τ_{0} := inf{τ ∈ (0, +∞] : dist(x, S) ≤ τ[f(x)]_{+} ∀x ∈ X}.

Then τ_{0} = \frac{1}{δ(ε)}. Moreover, if X is assumed to be reflexive then τ_{0} = \frac{1}{δ_{1}(ε)} where δ_{1}(ε) is defined by (5.4) with γ = 1.

Remark. The result was proved by Lewis and Pang (1997) in the special case when X is finite dimensional, A = S and f is lower semicontinuous (their result was extended to reflexive Banach spaces in Ng and Zheng (2001a). Proof of Theorem 5.1. By (5.2), (5.3) and Corollaries 4.1 and 4.2, we need only show that for each a ∈ A_{ε} ∩ ∂S and h ∈ N_{S}^{1}(a, γ), where γ may be taken to be 1 if X is assumed to be reflexive,

d^{+}f(a)(h) = dist(0, D̂F (a, 0)(h)). (5.5)

To do this, let a ∈ A_{ε} ∩ ∂S and h ∈ N_{S}^{1}(a, γ). We subdivide into two cases: 1) f(a + th) = +∞ for all t > 0 and 2) f(a + t_{0}h) < +∞ for some t_{0} > 0. 1): In this case, it is clear that d^{+}f(a)(h) = +∞ (noting that f(a) ≤ 0 is finite), and F (a + th) = ∅ for all t > 0. Thus, D̂F (a, 0)(h) = ∅ and so dist(0, D̂F (a, 0)(h)) = +∞. Thus (5.5) holds trivially in the case 1).

2): In this case, by (4.3), it suffices to show that f(a) = 0. By h ∈ N_{S}^{1}(a, γ) and (2.2), one has that for each t > 0,

tγ ≤ dist(a + th, S) and in particular a + th ∉ S.

This shows that f(a + th) > 0 for each t > 0. It follows from the convexity of f that

0 < f(a + th) ≤ (1 − \frac{t}{t_{0}} )f(a) + \frac{t}{t_{0}} f(a + t_{0}h) ∀t ∈ (0, t_{0}].

Letting t → 0^{+}, one has that 0 ≤ f(a). This and a ∈ ∂S ⊂ S (by (5.1)) imply that f(a) = 0. The proof is completed.

The Slater condition is implicitly assumed in the next result.

Theorem 5.2. Let τ > 0. Suppose that for each a ∈ A ∩ ∂S there exists h_{a} ∈ X with ∥h_{a}∥ = 1 such that

d^{+}f(a)(h_{a}) ≤ −\frac{1}{τ} . (5.6)

Then

dist(x, S) ≤ τ[f(x)]_{+} for all x ∈ X. (5.7)

Proof. Let τ′ > τ and a ∈ A ∩ ∂(F^{−1}0). Then a ∈ S by (5.2); it follows from (5.6) that there exist t_{a} > 0 and h_{a} ∈ X with ∥h_{a}∥ = 1 such that

\frac{f(a + t_{a}h_{a}) − f(a)}{t_{a}} < −\frac{1}{τ′} .

Letting r_{a} := \frac{t_{a}}{τ′}, it follows from f(a) ≤ 0 that f(a + τ′r_{a}h_{a}) < −r_{a}. This implies that

[−r_{a}, r_{a}] ⊂ [−r_{a}, +∞) ⊂ F (a + τ′r_{a}B_{X}).

By Theorem 3.2, this implies that

dist(x, F^{−1}0) ≤ τ′dist(0, F x) for all x ∈ X,

that is,

dist(x, S) ≤ τ′[f(x)]_{+} for all x ∈ X.

Letting τ′ → τ, (5.7) is seen to hold.

Theorem 5.3. Let f satisfy the Slater condition. Suppose that

lim inf_{∥a∥→∞,a∈A∩∂S} dist(0, ∂f(a)) ≠ 0. (5.8)

Then there exists τ > 0 such that

dist(x, S) ≤ τ[f(x)]_{+} for all x ∈ X.

Proof. Since f satisfies the Slater condition, F satisfies the Slater condition at 0 as remarked at the beginning of this section. Hence there exist x_{0} ∈ X, δ_{0} > 0 and r_{0} > 0 such that

[−r_{0}, r_{0}] ⊂ F (B(x_{0}, δ_{0})). (5.9)

On the other hand, by (5.8) there exist α > 0 and δ > 0 such that

inf{dist(0, ∂f(a)) : a ∈ A ∩ ∂S with ∥a∥ ≥ α} > δ. (5.10)

Let τ = max\{\frac{1}{δ}, \frac{∥x_{0}∥+δ_{0}+α}{r_{0}}\}. We will show that

dist(x, S) ≤ τ[f(x)]_{+}, ∀x ∈ X.

By (5.3), we need only show that τ is an error bound for the inclusion problem 0 ∈ F x. To do this, by Theorem 3.2 and (5.2) it suffices to show that for each a ∈ A ∩ ∂S there exists r_{a} > 0 such that

[−r_{a}, r_{a}] ⊂ F (B(a, τr_{a})). (5.11)

Fix a ∈ A ∩ ∂S. We subdivide into two cases: 1) ∥a∥ < α and 2) ∥a∥ ≥ α. 1): In this case, ∥x_{0} − a∥ + δ_{0} ≤ τr_{0} and hence B(x_{0}, δ_{0}) ⊂ B(a, τr_{0}). It follows from (5.9) that (5.11) holds with r_{a} := r_{0}. 2): Let ∥a∥ ≥ α; suppose for contradiction that (5.11) does not hold for any r_{a} > 0. Let x ∈ X \ {a} and r_{x} := \frac{∥x−a∥}{τ}. Then [−r_{x}, r_{x}] is not a subset of F (B(a, τr_{x})); in particular −r_{x} ∉ F x = [f(x), +∞) and hence

f(a) − r_{x} ≤ −r_{x} < f(x).

This implies that

f(a) < \frac{1}{τ} ∥x − a∥ + f(x) ∀x ∈ X \ \{a\}.

Hence

0 ∈ ∂(\frac{1}{τ} ∥ · −a∥ + f)(a) ⊂ \frac{1}{τ} B_{X^{∗}} + ∂f(a)

(cf. [Clarke (1989), p.105]). It follows that dist(0, ∂f(a)) ≤ \frac{1}{τ} ≤ δ, contradicting (5.10). Combining 1) and 2), one has that (5.11) holds for all a ∈ A ∩ ∂S. This completes the proof.

Suppose, in addition to (5.1), that f is lower semicontinuous. It is known [Ng and Zheng (2001b)] that f has an error bound if and only if

inf{dist(0, ∂f(x)) : x ∈ X \ S} > 0. (5.12)

The necessity part of this assertion holds even if f is not assumed to be lower semicontinuous and X is not assumed to be complete:

Proposition 5.1. Let τ > 0 be an error bound for f. Then

inf\{dist(0, ∂f(x)) : x ∈ X \ S\} ≥ \frac{1}{τ} .

Proof. Let x ∈ X \S and x^{∗} ∈ ∂f(x); and pick a sequence {z_{n}} in S such that ∥z_{n}−x∥ → dist(x, S). Then

⟨x^{∗}, z_{n} − x⟩ ≤ f(z_{n}) − f(x) ≤ −f(x).

Noting that dist(x, S) ≤ τf(x), it follows that ⟨x^{∗}, \frac{z_{n}−x}{∥z_{n}−x∥}⟩ ≤ −\frac{dist(x,S)}{τ∥z_{n}−x∥}. This and ∥z_{n} − x∥ → dist(x, S) imply that ∥x^{∗}∥ ≥ \frac{1}{τ}. The proof is completed.

We end the paper with an example which shows that (5.12) does not imply that f has an error bound if the lower semicontinuity assumption is dropped.

Let C := {(x, y) ∈ R^{2} : 0 < x ≤ 1, 0 ≤ y ≤ 1} ∪ {(0, 0)}. Define f : R^{2} → R ∪ {+∞} by f(x, y) = x if (x, y) ∈ C and f(x, y) = +∞ if (x, y) ∈ R^{2} \ C. Then C is a convex subset of R^{2}, f is a convex function and S = {(0, 0)}. We claim that

dist(0, ∂f(x, y)) ≥ 1, ∀(x, y) ∈ C \ S. (5.13)

Let (x, y) ∈ C \ S and x^{∗} ∈ ∂f(x, y). Then

⟨x^{∗}, (−t, 0)⟩ ≤ f(x − t, y) − f(x, y) = −t, ∀t ∈ (0, x),

and hence ∥x^{∗}∥ ≥ 1, verifying (5.13). Therefore (5.12) is seen to hold because dist(0, ∂f(x, y)) = +∞

if (x, y) ∉ C. On the other hand, since f(\frac{1}{n}, 1) = \frac{1}{n} and dist((\frac{1}{n}, 1), S) = \sqrt{1 + \frac{1}{n^{2}}} for each natural number n, f has no error bound.

Acknowledgments. This research was supported by an Earmarked grant from the Research Grant Council of Hong Kong. Research of the second author was also supported by the National Natural Science Foundation of P. R. China and ABSF of Yunnan Province, P. R. China.

References

[Aubin and Frankowska (1990)] Aubin, J. P. and H. Frankowska (1990), Set-Valued Analysis, Birkhauser, Boston. [Clarke (1989)] Clarke, F. H. (1989). Optimization and Nonsmooth Analusis , CRM, Montrel, Canada. [Hamel (1994)] Hamel, A. (1994). Remarks to an equivalent formulation of Ekeland’s variational principle, Opti-

mization, 31, pp. 233-238. [Holmes (1975)] Holmes, R. B. (1975). Geometric Functional Analysis and Its Applications, Springer-Verlag, Berlin. [Lewis and Pang (1997)] Lewis, A. and J. S. Pang (1997). Error bounds for convex inequality syst ems, 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, pp. 75–100.

[Li and Singer. (1998)] Li, W. and I. Singer. (1998). Global error bounds for convex muiltifunctions and applications,

Math. Oper. Res., 23, pp. 443-462. [Ng and Yang (2001)] Ng, K. F. and W. H. Yang (2001). Error bound of abstract linear inequality system, Preprint. [Ng and Zheng (2001a)] Ng, K. F. and X. Y. Zheng (2001a). Error bounds for lower continuous functions in normed

spaces, SIAM J. Optim., 12 pp.1–17 (on line publication). [Ng and Zheng (2001b)] Ng, K. F. and X. Y. Zheng (2001b). Global weak sharp minima on Banach spaces, Preprint. [Pang (1997)] Pang, J.S. (1997). Error bounds in Mathematical programming, Math. Prog. Ser. B, 79, pp.299–332. [Zalinescu (2001)] Zalinescu, C. (2001). A nonlinear extension of Hoffman’s error bounds for linear inequalities,

Preprint. [Zheng (2001)] Zheng, X.Y. (2001). Error bounds for set inclusions, Preprint.

X.Y. Zheng: Department of Mathematics, The Chinese University of Hong Kong, Shatin, New Territory, Hong Kong: e-mail: xyzheng@math.cuhk.edu.hk

K.F. Ng: Department of Mathematics, The Chinese University of Hong Kong, Shatin, New Territory, Hong Kong: e-mail: kfng@math.cuhk.edu.hk