ERROR BOUNDS FOR LOWER SEMICONTINUOUS FUNCTIONS IN NORMED SPACES^{∗}

KUNG FU NG^{†} AND XI YIN ZHENG^{‡}

Abstract. Without the convexity or analyticity assumption, we study error bounds for a inequality system defined by a general lower semicontinuous function and establish sufficient/necessary conditions on the existence of error bounds in infinite dimensional normed spaces. Some characterizations for a convex inequality system to possess an error bound in a reflexive Banach space are also given. As applications, in dealing with the Hoffman error bound result in normed spaces, we give a computable Lipschitz bound constant, which is better than previous Lipschitz bound constants in some examples; we also consider error bounds for quadratic functions on R^{n}.

Key words. error bound, lower semicontinuous function, convex function, normed space, Lipschitz bound constant.

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

1. Introduction. Let X be a normed space, f : X → R ⋃{+∞} a proper lower semicontinuous function, and let S = {x ∈ X|f(x) ⩽ 0}. We always assume S ≠ ∅. We say that an error bound for f holds if there is a positive constant τ such that for each x ∈ X,

dist(x, S) ⩽ τ[f(x)]_{+},

where dist(x, S) = inf{∥x − y∥|y ∈ S} and [f(x)]_{+} = max{f(x), 0}. Error bounds have important applications in sensitivity analysis of mathematical programming and in convergence analysis of some algorithms. In recent years, the study of error bounds have received growing attentions in the mathematical programming literatures. See [1, 5, 6, 8-11, 13-27] especially the excellent survey papers [16], [26] for details. However, most of the previous error bound results are concerned with either convex or analytic [20] inequality systems, and to the best of our knowledge, an error bound for a general lower semicontinuous function has not been studied. One of our aims is to study an error bound for a lower semicontinuous function on X. Using the Dini-directional derivatives, a main result (Theorem 2.5) in section 2 implies that if X is a Banach space and f is lower semicontinuous then an error bound for f holds provided that

sup_{x∈X\S} inf_{∥h∥=1} \underline{d}^{+}f(x)(h) < 0 (1.1)

(a partial converse is given in Theorem 2.7). If f is convex and X is a reflexive Banach space then one has: an error bound for f holds if and only if (1.1) holds, and this is

∗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, China.

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

‡Department of Mathematics, Yunnan University, Kunming 650091, P. R. China (xyzheng@ynu.edu.cn).

the case if and only if there exists a positive constant δ such that

inf{d^{+}f(x)(h)|h ∈ N_{S}^{1}(x)} ⩾ δ, (1.2)

whenever x is a boundary point of S with

∅ ≠ N_{S}^{1}(x) := {h ∈ X|∥h∥ = 1 and dist(x + th, S) = t for some t > 0}

(the above characterization in terms of N_{S}^{1}(x) is due to Lewis and Pang [16] for the case when X = R^{n}). As applications, we deal with, in Theorem 4.4, the Hoffman error bound result in normed spaces (our proof is very different from that of Hoffman [14] and that others of [10, 3]), and give a computable Lipschitz bound constant; we also give a systematic treatment for the existence (or nonexistence) of error bounds for quadratic functions.

2. An error bound for a proper lower semicontinuous function on a normed space. We will need the following notations. For x ∈ X and h ∈ X with ∥h∥ = 1, we denote the upper and lower Dini-directional derivatives respectively by

d̄^{+}f(x)(h) := lim sup_{t→0^{+}} \frac{f(x + th) − f(x)}{t}

and

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

(In the case when f(x) = +∞, we define \underline{d}^{+}f(x)(h) = −∞.) Clearly, \underline{d}^{+}f(x)(h) ⩽ d̄^{+}f(x)(h). If \underline{d}^{+}f(x)(h) = d̄^{+}f(x)(h), f is said to be right differentiable at x in the direction h. For x ∈ ∂S (the boundary of S), define

N_{S}^{1}(x) = {h ∈ X|∥h∥ = 1 and dist(x + th, S) = t for some t > 0}

and

∂_{N}S = {x ∈ ∂S|N_{S}^{1}(x) ≠ ∅}.

If X is a Hilbert space and S is convex, then it is easy to verify that

N_{S}^{1}(x) = {h ∈ N_{S}(x)|∥h∥ = 1}, where N_{S}(x) = {v ∈ X|⟨v, y − x⟩ ⩽ 0, y ∈ S}

is the normal cone of S at x. The following result of the mean-valued theorem type will be useful for us to establish error bound results in terms of the Dini-directional derivatives. It is known (cf. [4] and [6]) when f is assumed continuous.

Lemma 2.1. Let X be a normed space and f a proper lower semicontinuous function on X; let x ∈ dom(f) := {x ∈ X|f(x) < +∞}, h ∈ X with ∥h∥ = 1 and t > 0. Assume that there exists δ ∈ R such that for each α ∈ [0, t), \underline{d}^{+}f(x + αh)(h) ⩽ δ. Then

f(x + th) − f(x) ⩽ tδ.

Proof. For any ε > 0, let t_{ε} = sup{0 ⩽ s ⩽ t|f(x + sh) − f(x) ⩽ s(δ + ε)}. By the lower semicontinuity of f, one has

f(x + t_{ε}h) − f(x) ⩽ t_{ε}(δ + ε) (2.1)

We claim that t_{ε} = t. Indeed, if t_{ε} < t, then x+t_{ε}h ∈ dom(f) and so \underline{d}^{+}f(x+t_{ε}h)(h) ⩽ δ by assumption. Consequently there exists t′ ∈ (t_{ε}, t) such that

f(x + t′h) − f(x + t_{ε}h) ⩽ (t′ − t_{ε})(δ + ε).

This and (2.1) imply that f(x + t′h) − f(x) ⩽ t′(δ + ε). It follows from the definition of t_{ε} that t′ ⩽ t_{ε}, a contradiction. This shows that f(x+th)−f(x) ⩽ t(δ +ε). Letting ε → 0, one has that f(x + th)(h) − f(x) ⩽ tδ.

The following lemma itself is an interesting result on an error bound for a general function (without the continuity assumption).

Lemma 2.2. Let (X, d) be a metric space and f : X → R ⋃{+∞} a proper function; let τ > 0 and 0 ⩽ ρ < 1 be constants. Suppose that for each x ∈ f^{−1}(0, +∞) = {y ∈ X|0 < f(y) < +∞}, there is x′ ∈ f^{−1}[0, +∞) such that

dist(x′, S) ⩽ ρdist(x, S) (2.2)

and

d(x, x′) ⩽ τ[f(x) − f(x′)].

Then, for each x ∈ X, dist(x, S) ⩽ τ[f(x)]_{+}.

Proof. It suffices to show that for each x ∈ f^{−1}(0, +∞), dist(x, S) ⩽ τf(x). For each x ∈ f^{−1}(0, +∞), let x_{0} = x and suppose that x_{0}, ⋯, x_{k} have been chosen in f^{−1}(0, +∞) such that for each 1 ⩽ i ⩽ k,

dist(x_{i}, S) ⩽ ρ^{i}dist(x, S) and d(x_{i−1}, x_{i}) ⩽ τ[f(x_{i−1}) − f(x_{i})].

By the given condition, there is x_{k+1} ∈ f^{−1}[0, +∞) such that

dist(x_{k+1}, S) ⩽ ρdist(x_{k}, S) ⩽ ρ^{k+1}dist(x, S) and d(x_{k}, x_{k+1}) ⩽ τ[f(x_{k}) − f(x_{k+1})].

If f(x_{k+1}) = 0 then

dist(x, S) ⩽ d(x_{0}, x_{k+1}) ⩽ ∑_{i=1}^{k+1} d(x_{i−1}, x_{i}) ⩽ τ ∑_{i=1}^{k+1}[f(x_{i−1}) − f(x_{i})] = τf(x).

Thus we may assume that f(x_{k+1}) ≠ 0 and hence inductively we obtain a sequence {x_{n}} in f^{−1}(0, +∞) such that x_{0} = x,

dist(x_{n}, S) ⩽ ρ^{n}dist(x, S) and d(x_{n−1}, x_{n}) ⩽ τ[f(x_{n−1}) − f(x_{n})]

for all n ∈ N, where N is the natural number set. Hence for n ∈ N,

dist(x, S) ⩽ d(x, x_{n}) + dist(x_{n}, S)
⩽ ∑_{i=1}^{n} d(x_{i−1}, x_{i}) + ρ^{n}dist(x, S)

= τ ∑_{i=1}^{n}[f(x_{i−1}) − f(x_{i})] + ρ^{n}dist(x, S)
⩽ τf(x) + ρ^{n}dist(x, S),

as f(x_{n}) ⩾ 0. It follows that

dist(x, S) ⩽ \frac{τ}{1 − ρ^{n}} f(x) for each n ∈ N.

This implies that

dist(x, S) ⩽ τf(x).

The following lemma is a straightforward consequence of Theorem 2 (ii) in Hamel [11]; it shows that in Lemma 2.2, if we add the conditions that X is complete and f is lower semicontinuous, then the conclusion is still true when (2.2) is removed. We are grateful to the referee who drew our attention to this reference and pointed out its connection with our works here.

Lemma 2.3. Let (X, d) be a complete metric space and f : X → R ⋃{+∞} a proper lower semicontinuous function; let τ > 0 be a constant. Suppose that for each x ∈ f^{−1}(0, +∞), there is x′ ∈ f^{−1}[0, +∞) such that

0 ≠ d(x, x′) ⩽ τ[f(x) − f(x′)].

Then, for each x ∈ X, dist(x, S) ⩽ τ[f(x)]_{+}.

Proof. We may assume that X ≠ S. Let g(x) = max{f(x), 0} for each x ∈ X. Then g_{min} := inf{g(x)|x ∈ X} = 0 and S = {x ∈ X|g(x) = g_{min}}. For each x ∈ dom(g) with g(x) > g_{min} (i.e., x ∈ f^{−1}(0, +∞)), by the given condition there exists x′ ∈ f^{−1}[0, +∞) such that 0 ≠ d(x, x′) ⩽ τ[f(x)−f(x′)], that is, g(x′)+ \frac{1}{τ} d(x, x′) ⩽ g(x); this last inequality is trivially true if x ∉ dom(g). By Theorem 2 (ii) in Hamel [11], for each x ∈ X, one has

dist(x, S) ⩽ τ(g(x) − g_{min}),

that is,

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

Theorem 2.4. Let X be a normed space and f a proper lower semicontinuous function on X; let 0 < δ < +∞ and 0 ⩽ ρ < 1. Suppose that for each x ∈ f^{−1}(0, +∞) there exist h_{x} ∈ X with ∥h_{x}∥ = 1 and t_{x} > 0 such that for t ∈ [0, t_{x}),

dist(x + t_{x}h_{x}, S) ⩽ ρdist(x, S) and \underline{d}^{+}f(x + th_{x})(h_{x}) ⩽ −δ. (2.3)

Then for each x ∈ X, dist(x, S) ⩽ \frac{1}{δ}[f(x)]_{+}.

Proof. Given x ∈ f^{−1}(0, +∞), we will check that there exists x′ ∈ f^{−1}([0, +∞)) satisfying the properties stated in Lemma 2.2 with τ = \frac{1}{δ}. If f(x + t_{x}h_{x}) ⩾ 0, then we can take x′ := x + t_{x}h_{x} because, by Lemma 2.1 (applied to −δ instead of δ) and assumption (2.3), one has ∥x − x′∥ = t_{x} ⩽ \frac{1}{δ}[f(x) − f(x + t_{x}h_{x})]. If f(x + t_{x}h_{x}) < 0, let s_{x} = sup{0 ⩽ t ⩽ t_{x}|f(x + sh_{x}) > 0 for each s ∈ [0, t]}. Then f(x + s_{x}h_{x}) ⩽ 0 and f(x + th_{x}) > 0 for all t ∈ [0, s_{x}). By the lower semicontinuity of f, S is a closed set. It follows from x ∉ S that dist(x, S) > 0. Thus, there exists s′_{x} ∈ (0, s_{x}) such that

dist(x + s′_{x}h_{x}, S) ⩽ ∥x + s′_{x}h_{x} − (x + s_{x}h_{x})∥ = s_{x} − s′_{x} ⩽ ρdist(x, S)

and x + s′_{x}h_{x} ∈ f^{−1}([0, +∞)). Note that \underline{d}^{+}f(x + th_{x})(h_{x}) ⩽ −δ for each t ∈ [0, s′_{x}]. As in the first part of our proof, it follows that x + s′_{x}h_{x} has the desired properties for x′.

If X is assumed a Banach space, conditions in Theorem 2.4 can been simplified (by considering \underline{d}^{+}f(x) in place of \underline{d}^{+}f(x + th_{x})).

Theorem 2.5. Let X be a Banach space, f : X → R ⋃{+∞} a proper lower semicontinuous function, and let 0 < δ < +∞. Suppose that for each x ∈ f^{−1}(0, +∞) there exists h_{x} ∈ X with ∥h_{x}∥ = 1 such that \underline{d}^{+}f(x)(h_{x}) ⩽ −δ. Then for each x ∈ X, dist(x, S) ⩽ \frac{1}{δ}[f(x)]_{+}.

Proof. Let x ∈ X with 0 < f(x) < +∞. Then \underline{d}^{+}f(x)(h_{x}) ⩽ −δ < −(δ − ε) for any ε ∈ (0, δ). It follows from the lower semicontinuity of f and f(x) > 0 that there exists t > 0 small enough such that x+th_{x} ∈ f^{−1}[0, +∞) and \frac{1}{t}[f(x+th_{x})−f(x)] < −(δ−ε). Thus

∥x − (x + th_{x})∥ = t ⩽ \frac{1}{δ − ε}[f(x) − f(x + th_{x})].

By Lemma 2.3, one has that for each x ∈ X, dist(x, S) ⩽ \frac{1}{δ−ε}[f(x)]_{+}. Letting ε → 0, the proof is completed.

Recall that the cone of feasible directions of a convex set C ⊂ X at a point x ∈ C is, by definition, the set

F_{C}(x) = {v ∈ X|x + tv ∈ C; for some t > 0}.

The following is a general constraint error bound result.

Corollary 2.6. Let X be a Banach space, f : X → R ⋃{+∞} a proper lower semicontinuous function; let 0 < δ < +∞ and C be a closed convex subset of X such that S_{C} = S ⋂ C ≠ ∅. Suppose that for each x ∈ f^{−1}(0, +∞) ⋂ C there exists h_{x} ∈ F_{C}(x) with ∥h_{x}∥ = 1 such that \underline{d}^{+}f(x)(h_{x}) ⩽ −δ. Then for each x ∈ C, dist(x, S_{C}) ⩽ \frac{1}{δ}[f(x)]_{+}.

Proof. Define g(x) := f(x) + δ_{C}(x) for each x ∈ X, where δ_{C} is the indicator function of C. Then g is a proper lower semicontinuous function, g^{−1}(0, +∞) = f^{−1}(0, +∞) ⋂ C, S_{C} = {x ∈ X|g(x) ⩽ 0} and for each x ∈ g^{−1}(0, +∞) and h ∈ F_{C}(x), \underline{d}^{+}g(x)(h) = \underline{d}^{+}f(x)(h). It follows from the given conditions and Theorem 2.5 that for each x ∈ X, dist(x, S_{C}) ⩽ \frac{1}{δ}[g(x)]_{+}. This implies that dist(x, S_{C}) ⩽ \frac{1}{δ}[f(x)]_{+} for all x ∈ C.

The following result gives a necessary condition for f to have a local error bound.

Theorem 2.7. Let X be a normed space, f a proper lower semicontinuous function on X, and let τ > 0. Suppose that for each x ∈ ∂S, there is δ(x) > 0 such that whenever y ∈ X with ∥y − x∥ < δ(x),

dist(y, S) ⩽ τ[f(y)]_{+}. (2.4)

Then for each x ∈ ∂_{N}S,

inf\{\underline{d}^{+}f(x)(h)|h ∈ N_{S}^{1}(x)\} ⩾ \frac{1}{τ} .

Proof. For each x ∈ ∂_{N}S and each h ∈ N_{S}^{1}(x), one has, by definitions, that there exists t > 0 such that dist(x + th, S) = t. It is easy to verify that for each s ∈ (0, t), dist(x + sh, S) = s > 0, and so x + sh ∉ S; that is, f(x + sh) > 0. Hence, for 0 < s < min{δ(x), t}, (2.4) gives

s ⩽ τf(x + sh) = τ[f(x + sh) − f(x)].

This implies that \underline{d}^{+}f(x)(h) ⩾ \frac{1}{τ}, and hence that

inf\{\underline{d}^{+}f(x)(h)|h ∈ N_{S}^{1}(x)\} ⩾ \frac{1}{τ} .

Corollary 2.8. Let X be a normed space and f a proper lower semicontinuous function on X. Suppose τ > 0 such that for each x ∈ X, dist(x, S) ⩽ τ[f(x)]_{+}. Then, for each x ∈ ∂_{N}S,

inf\{\underline{d}^{+}f(x)(h)|h ∈ N_{S}^{1}(x)\} ⩾ \frac{1}{τ} . (2.5)

In section 3, we shall show that (2.5) is also sufficient for f to have an error bound when f is assumed convex.

Corollary 2.9. Let X be a finite dimensional normed space and f a differentiable function on X. Suppose that an error bound for f holds. Then f satisfies the Slater condition (i.e., there exists x_{0} ∈ X such that f(x_{0}) < 0).

Proof. Suppose to the contrary that f does not satisfy the Slater condition. Then for each x ∈ S, one has f(x) = inf{f(y)|y ∈ X}, and so ▽f(x) = 0. It follows from Corollary 2.8 that N_{S}^{1}(x) must be empty for each x ∈ ∂S. Pick a point z in X\S. Since X is a finite dimensional space, there exists x_{0} ∈ ∂S such that dist(z, S) = ∥z − x_{0}∥. This implies that

\frac{z − x_{0}}{∥z − x_{0}∥} ∈ N_{S}^{1}(x_{0}),

contradicting to an earlier remark.

For convex f, the finite dimension assumption of X can be relaxed.

Corollary 2.10. Let X be a reflexive Banach space and f a differentiable convex function on X. Suppose that an error bound for f holds. Then f satisfies the Slater condition.

Proof. Since f is a differentiable convex function, S is closed convex in X. Pick a point z ∈ X \ S, by the reflexivity of X, there exists x_{0} ∈ ∂S such that dist(z, S) = ∥z − x_{0}∥. The proof follows as in the proof of Corollary 2.9.

3. Error bounds for lower semicontinuous convex functions on reflexive spaces. The aim of this section is to show that, when f is assumed of convexity, the results presented in the preceding section lead to conditions which are both necessary and sufficient for f to have an error bound. Throughout this section we let f be a proper lower semicontinuous convex function on X. Recall that the right directional derivative and the left directional derivative of f are defined by

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

and

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

They always exist and d^{−}f(x)(h) = −d^{+}f(x)(−h) for each x ∈ dom(f) and h ∈ X \ {0}. When f(x) = +∞, we define d^{+}f(x)(h) = −∞ for all h ∈ X. It is known [7] that for 0 ⩽ t_{1} < t_{2} with x + t_{1}h and x + t_{2}h in dom(f),

d^{+}f(x + t_{1}h)(h) ⩽ d^{−}f(x + t_{2}h)(h) ⩽ d^{+}f(x + t_{2}h)(h) (3.1)

Theorem 3.1. Let X be a reflexive Banach space and f a proper lower semicontinuous convex function on X. Let τ > 0. Then the following statements are equivalent.

(i) τ is an error bound: dist(x, S) ⩽ τ[f(x)]_{+} for each x ∈ X.

(ii) τ is a local error bound for f at each boundary point of S: for each x ∈ ∂S, there exists δ(x) > 0 such that whenever y ∈ X with ∥y − x∥ < δ(x), one has dist(y, S) ⩽ τ[f(y)]_{+}.

(iii) For each x ∈ ∂_{N}S,

inf\{d^{+}f(x)(h)|h ∈ N_{S}^{1}(x)\} ⩾ \frac{1}{τ} . (3.2)

(iv) For each x ∈ X \ S there exist t_{x} > 0 and h_{x} ∈ X with ∥h_{x}∥ = 1 satisfying

x + t_{x}h_{x} ∈ S and d^{+}f(x + th_{x})(h_{x}) ⩽ −\frac{1}{τ} for all t ∈ [0, t_{x}).

(v) For each x ∈ X \ S, there exists h_{x} ∈ X with ∥h_{x}∥ = 1 satisfying

d^{+}f(x)(h_{x}) ⩽ −\frac{1}{τ} .

Proof. (i)⇒(ii) and (iv)⇒(v) are trivial; (ii)⇒(iii) and (v)⇒(i) are directly from Theorems 2.7 and 2.5.

(iii)⇒(iv): Note that for each x ∈ X with f(x) = +∞, d^{+}f(x)(h) = −∞ for all h ∈ X with ∥h∥ = 1. Given an x ∈ f^{−1}(0, +∞), by the reflexivity of X and the convexity of S, there exists x_{0} ∈ ∂S such that ∥x − x_{0}∥ = dist(x, S). Let

t_{x} = ∥x − x_{0}∥ and h_{x} = \frac{1}{t_{x}} (x_{0} − x).

Then x_{0} = x + t_{x}h_{x} ∈ S and −h_{x} ∈ N_{S}^{1}(x_{0}). By the convexity of f and x, x + t_{x}h_{x} ∈ dom(f), it is clear that x + th_{x} ∈ dom(f) for each t ∈ [0, t_{x}]. By (iii), one has that d^{+}f(x_{0})(−h_{x}) ⩾ \frac{1}{τ}, that is, d^{−}f(x_{0})(h_{x}) ⩽ −\frac{1}{τ}. Consequently, by (3.1), we have that for each t ∈ [0, t_{x}),

d^{+}f(x + th_{x})(h_{x}) ⩽ d^{−}f(x + t_{x}h_{x})(h_{x}) = d^{−}f(x_{0})(h_{x}) ⩽ −\frac{1}{τ} .

Let β = inf{τ > 0|dist(x, S) ⩽ τ[f(x)]_{+} for each x ∈ X}. Note that β = 0 if and only if X = S and that β = +∞ if and only if f does not have any error bound. The following result is directly from Theorem 3.1.

Corollary 3.2. Let X be a reflexive Banach space and f a proper lower semicontinuous convex function. Then

\frac{1}{β} = − sup_{x∈X\S} inf_{h∈X,∥h∥=1} d^{+}f(x)(h) = inf_{x∈∂_{N} S} inf_{h∈N_{S}^{1}(x)} d^{+}f(x)(h).

If the continuity is assumed in place of the lower semicontinuity, we have:

Theorem 3.3. Let X be a reflexive Banach space and f a continuous convex function. Then f has an error bound if and only if

δ := inf_{x∈X\S} inf{∥x^{∗}∥|x^{∗} ∈ ∂f(x)} > 0. (3.3)

In this case, dist(x, S) ⩽ \frac{1}{δ}[f(x)]_{+} for each x ∈ X.

Proof. Suppose that (3.3) holds. Then, for each x ∈ X \S, int(δB(X^{∗})) ⋂ ∂f(x) = ∅, and so by the Separation Theorem, there exists h_{x} ∈ X with ∥h_{x}∥ = 1 such that

−δ = inf{⟨x^{∗}, h_{x}⟩|x^{∗} ∈ δB(X^{∗})} ⩾ sup{⟨x^{∗}, h_{x}⟩|x^{∗} ∈ ∂f(x)}, (3.4)

where B(X^{∗}) denotes the unit ball of the dual space X^{∗} of X. Since f is continuous at x, d^{+}f(x)(h_{x}) = sup{⟨x^{∗}, h_{x}⟩|x^{∗} ∈ ∂f(x)}, and so, d^{+}f(x)(h_{x}) ⩽ −δ. By Theorem 3.1, one obtains that dist(x, S) ⩽ \frac{1}{δ}[f(x)]_{+} for each x ∈ X. This shows the sufficiency part. It is clear that the necessity part is directly from (v) of Theorem 3.1 and d^{+}f(x)(h_{x}) = sup{⟨x^{∗}, h_{x}⟩|x^{∗} ∈ ∂f(x)}.

R. Y. He informed us that, with suitable subdifferentials and via Ekeland’s Variational Principle, he obtains [12] the result of Theorem 3.3 for general Banach spaces.

Corollary 3.4. Let X be a reflexive Banach space and f a continuous convex function. Suppose that

sup_{x∈∂S} inf_{h∈X,∥h∥=1} d^{+}f(x)(h) < 0. (3.5)

Then an error bound for f holds.

Proof. We need only show the local version: (ii) of Theorem 3.1 holds. Take δ_{0} > 0 such that for each x ∈ ∂S there exists h_{x} ∈ X with ∥h_{x}∥ = 1 satisfying d^{+}f(x)(h_{x}) < −δ_{0}. Since d^{+}f(·)(h_{x}) is upper semicontinuous (see [7]), there exists r > 0 such that

d^{+}f(·)(h_{x}) < −δ_{0} on B(x, r).

By the continuity of f, for ε := \frac{rδ_{0}}{2} , there exists r_{1} ∈ (0, \frac{r}{2}) such that

f(·) = f(·) − f(x) < ε on B(x, r_{1}). (3.6)

Let y ∈ B(x, r_{1}) \ S. Then, it follows from Lemma 2.1 that

f(y + \frac{r}{2}h_{x}) − f(y) ⩽ −\frac{r}{2}δ_{0}.

It follows from (3.6) that f(y + \frac{r}{2}h_{x}) < 0 < f(y), and hence f(y + t_{y}h_{x}) = 0 for some t_{y} ∈ (0, \frac{r}{2}). Again by Lemma 2.1, f(y + t_{y}h_{x}) − f(y) ⩽ −t_{y}δ_{0}, and so

f(y) ⩾ δ_{0}t_{y} = δ_{0}∥y − (y + t_{y}h_{y})∥ ⩾ δ_{0}dist(y, S).

Therefore, for each y ∈ B(x, r_{1}),

dist(y, S) ⩽ \frac{1}{δ_{0}} [f(y)]_{+}.

Remark. For the case X = R^{n}, the equivalence of (i) and (iii) in Theorem 3.1 is due to Lewis and Pang [16] (also see Klatte and Li [15]), while the other parts of Theorem 3.1 are new even for the finite dimension case. Since it is not always easy to compute N_{S}^{1}(x) and inf{d^{+}f(x)(h)|h ∈ N_{S}^{1}(x)}, it is sometimes more convenient to check an error bound for f by using (v) of Theorem 3.1 and Theorem 3.3. We will take this advantage in section 4 in the proof of an extension of Hoffman’s error bound result to the setting of normed spaces (our proof is quite different from the approach of Hoffman [14] and that of others [3, 10, 15]). It may be of interest to note that (3.3) in Theorem 3.3 is a weaker condition than (ACQ9) in [15] (the condition first considered in [16]):

inf_{x∈∂S} inf_{x^{∗}∈∂f(x)} ∥x^{∗}∥ > 0.

For example, let X = R and f(x) = |x| for each x ∈ X. Then S = {0}, and

0 = inf_{x∈∂S} inf_{x^{∗}∈∂f(x)} ∥x^{∗}∥ < inf_{x∈X\S} inf_{x^{∗}∈∂f(x)} ∥x^{∗}∥ = 1.

However (3.5) in Corollary 3.4 is equivalent to (AQC9) in Klatte and Li [15]. In what follows, we give a proof of this equivalence. Since d^{+}f(x)(h) = sup{⟨x^{∗}, h⟩|x^{∗} ∈ ∂f(x)}, it is clear that (3.5) in Corollary 3.4 implies (ACQ9) in [15]. Conversely, suppose that (ACQ9) holds. Then there exists δ > 0 such that for each x ∈ ∂S, δB(X^{∗}) ⋂ ∂f(x) = ∅. As in (3.4) it follows that inf_{h∈X,∥h∥=1} d^{+}f(x)(h) ⩽ −δ for each

x ∈ ∂S.

Theorem 2.7, Corollary 2.8 and (iii) of Theorem 3.1 all concern with the condition (3.2) for points in ∂_{N}S. By the definitions, it is obvious that ∂_{N}S ⊂ ∂S. The following proposition further explains the relationship between ∂_{N}S and ∂S.

Proposition 3.5. Let X be a reflexive Banach space and f a continuous convex function. Then \overline{∂_{N}S} = ∂S. In addition, if f also satisfies the Slater condition, ∂_{N}S = ∂S.

Proof. For x ∈ ∂S and ε > 0, pick a point y ∈ X \ S and a point y_{0} ∈ S such that

0 < ∥y − x∥ < \frac{ε}{2} and dist(y, S) = ∥y − y_{0}∥.

Then it is easy to verify that y_{0} ∈ ∂_{N}S; also ∥y − y_{0}∥ = dist(y, S) ⩽ ∥y − x∥ and so

∥y_{0} − x∥ ⩽ ∥y − y_{0}∥ + ∥y − x∥ < ε.

This shows that x ∈ \overline{∂_{N}S}, and hence that

\overline{∂_{N}S} = ∂S.

If f satisfies the Slater condition, S is a closed convex set with a nonempty interior. By the Separation Theorem, for each x ∈ ∂S, there is x^{∗} ∈ X^{∗} with x^{∗} ≠ 0 such that

⟨x^{∗}, x⟩ = sup{⟨x^{∗}, y⟩|y ∈ S}. (3.7)

By the reflexivity of X, there is h ∈ X with ∥h∥ = 1 such that ⟨x^{∗}, h⟩ = ∥x^{∗}∥. By (3.7), for any y ∈ S, we have

∥x^{∗}∥ = ⟨x^{∗}, h⟩ ⩽ ⟨x^{∗}, x + h − y⟩ ⩽ ∥x^{∗}∥∥x + h − y∥,

and so

∥x + h − x∥ = 1 ⩽ ∥x + h − y∥.

This shows that dist(x + h, S) = 1. Hence h ∈ N_{S}^{1}(x) and so x ∈ ∂_{N}S. Therefore, ∂_{N}S = ∂S.

If the reflexivity of X in the Proposition 3.5 is dropped, ∂_{N}S may be empty even though f is a continuous convex function satisfying the Slater condition.

Example 3.6. Let X be a non-reflexive Banach space. Then, by the well-known James theorem, there exists x^{∗} ∈ X^{∗} with x^{∗} ≠ 0 such that for each h ∈ X with ∥h∥ = 1,

⟨x^{∗}, h⟩ < ∥x^{∗}∥. (3.8)

It is clear that x^{∗} satisfies the Slater condition. Next we show that ∂_{N}S_{∗} = ∅, where S_{∗} = {x ∈ X|⟨x^{∗}, x⟩ ⩽ 0}. Indeed, if there exists x_{0} ∈ ∂_{N}S_{∗}, then ⟨x^{∗}, x_{0}⟩ = 0, and for some h_{0} ∈ X with ∥h_{0}∥ = 1 and some t_{0} > 0, one has

dist(x_{0} + t_{0}h_{0}, S_{∗}) = t_{0}.

This and (3.8) imply that 0 < ⟨x^{∗}, h_{0}⟩ < ∥x^{∗}∥. By the definition of ∥x^{∗}∥, there are h_{1} ∈ X with ∥h_{1}∥ = 1 and 0 < r < 1 such that ⟨x^{∗}, rh_{1}⟩ = ⟨x^{∗}, h_{0}⟩. It follows from ⟨x^{∗}, x_{0}⟩ = 0 that

⟨x^{∗}, x_{0} + t_{0}h_{0} − t_{0}rh_{1}⟩ = 0.

This implies that

dist(x_{0} + t_{0}h_{0}, S_{∗}) ⩽ ∥x_{0} + t_{0}h_{0} − (x_{0} + t_{0}h_{0} − t_{0}rh_{1})∥ = rt_{0},

contradicting dist(x_{0} + t_{0}h_{0}, S_{∗}) = t_{0}.

4. Application to linear inequality system. Let X be a normed space and X^{∗} denote the dual space of X; let x_{1}^{∗}, ⋯, x_{n}^{∗} ∈ X^{∗}, c_{1}, ⋯, c_{n} ∈ R and S = {x ∈ X|⟨x_{i}^{∗}, x⟩−c_{i} ⩽ 0, i = 1, ⋯, n}. Define f(x) = max{⟨x_{i}^{∗}, x⟩−c_{i}|i = 1, ⋯, n} for each x ∈ X. It is clear that S = {x ∈ X|f(x) ⩽ 0}. Assuming that S ≠ ∅, the fundamental result of Hoffman [13] asserts that if X = R^{n} then there exists a constant τ > 0 such that dist(x, S) ⩽ τ[f(x)]_{+} for each x ∈ X. This Lipschitz error bound constant τ is related to the convergence rate of algorithms appearing in some applications. Several authors considered the constants of this type; see Mangsarian and Shiau [24], Bergthaller and Singer [2], Guler, Hoffman and Rothblum [10], Burke and Tseng [3] and references therein. In this section, we will explicitly give a new Lipschitz error bound constant, which is better than the previous ones in some examples. We first introduce some notations. Let I denote the set {1, ⋯, n} and for each i ∈ I, g_{i} denotes the affine function defined by g_{i}(x) = ⟨x_{i}^{∗}, x⟩ − c_{i}. For each x ∈ X, let I(x) denote the set of active indexes at x, that is, I(x) = {i ∈ I|g_{i}(x) = f(x)}. We recall from [7] that

∂f(x) = { ∑_{i∈I(x)} t_{i}x_{i}^{∗}|t_{i} ⩾ 0 and ∑_{i∈I(x)} t_{i} = 1}. (4.1)

We make the following definitions.

Definition 4.1. A nonempty subset D of I is said to be

(i) full if

(4.2) span{x_{i}^{∗}|i ∈ D} = span{x_{i}^{∗}|i ∈ I}

(ii) regular if 0 ∉ co{x_{i}^{∗}|i ∈ D}, that is, τ_{D} > 0 where

τ_{D} := inf{∥ ∑_{i∈D} t_{i}x_{i}^{∗}∥|t_{i} ⩾ 0 and ∑_{i∈D} t_{i} = 1} (4.3)

Definition 4.2. A nonempty subset D of I is called

(i) a peak-set in I if there exists x_{D} ∈ X such that

g_{k}(x_{D}) < g_{i}(x_{D}) = f(x_{D}) (4.4)

for all k ∈ I \ D and all i ∈ D. (ii) a positive peak-set in I if there exists x_{D} satisfying (4.4) such that f(x_{D}) > 0. (iii) a normal set in I if it is full and a positive peak-set.

Let R(I) denote the family of all full and regular subsets of I, and let N (I) denote the family of all normal subsets of I. Define

μ := inf{τ_{D}|D ∈ N (I)} (4.5)

and

ν := inf{τ_{D}|D ∈ R(I)} (4.6)

where τ_{D} is defined by (4.3). R(I) can be easily identified. It is also of no difficulty to identify N (I) and hence μ is a computable constant. It is easy to see that a subset D of I is in N (I) if and only if (4.2) holds and there exists a solution x_{D} of the linear equation system

⟨x_{i}^{∗}, x⟩ − c_{i} = ⟨x_{j}^{∗}, x⟩ − c_{j}, i, j ∈ D (4.7)

such that for each k ∈ I \ D and i ∈ D,

⟨x_{k}^{∗}, x_{D}⟩ − c_{k} < ⟨x_{i}^{∗}, x_{D}⟩ − c_{i} and 0 < ⟨x_{i}^{∗}, x_{D}⟩ − c_{i}. (4.8)

For a subset D of I, if (4.2) holds then for each j ∈ D, dim(span{x_{i}^{∗}|i ∈ I}) differs to dim(span{x_{i}^{∗} − x_{j}^{∗}|i ∈ D}) at most by 1, and so the solution set of (4.7) is either z + ⋂_{i∈I} ker(x_{i}^{∗}) for some z ∈ X or z + Re + ⋂_{i∈I} ker(x_{i}^{∗}) for some z ∈ X and e ∈

X \ ⋂_{i∈I} ker(x_{i}^{∗}), where ker(x_{i}^{∗}) = {x ∈ X|⟨x_{i}^{∗}, x⟩ = 0}. Thus, it is not difficult to

check whether or not a subset of I is normal. Note that N (I) depends on the system {g_{i}|i ∈ I} while R(I) depends only on {x_{i}^{∗}|i ∈ I} (not depend on the constants c_{i}). Note that ν > 0 because I is a finite set (so is R(I)). The main result in this section is to show that \frac{1}{μ} and \frac{1}{ν} are Lipschitz error bound constants (for the system S = {x ∈ X|f(x) ⩽ 0}).

Lemma 4.3. N (I) ⊂ R(I) and so μ ⩾ ν > 0.

Proof. By Definitions 4.1 and 4.2, it suffices to show that for each D ∈ N (I), 0 ∉ co{x_{i}^{∗}|i ∈ D}. Take x_{D} satisfying (4.4). Then I(x_{D}) = D and x_{D} is not a minimizer of f as S is assumed nonempty. It follows from [7] and (4.1) that 0 ∉ ∂f(x_{D}) = co{x_{i}^{∗}|i ∈ D}.

Theorem 4.4. Let X be a normed space and x_{1}^{∗}, ⋯, x_{n}^{∗} ∈ X^{∗}. Let S, f, g_{i} and x_{i}^{∗}, ⋯, x_{n}^{∗} ∈ X^{∗} as above in this section. Let δ, μ and ν be as in (3.3), (4.5) and (4.6), respectively. Then 0 < ν ⩽ μ ⩽ δ and for each x ∈ X,

dist(x, S) ⩽ \frac{1}{δ}[f(x)]_{+} ⩽ \frac{1}{ν} [f(x)]_{+} ⩽ \frac{1}{μ}[f(x)]_{+}.

The Lipschitz error bound constants \frac{1}{μ} and \frac{1}{ν} given in Theorem 4.4 can be practically computed. The following example shows that the constant \frac{1}{μ} in Theorem 4.4 is better than previous Lipschitz bound constants in some cases.

Pick X = R, x_{1}^{∗} = 1, x_{2}^{∗} = \frac{1}{2}, x_{3}^{∗} = \frac{1}{3}, c_{1} = 3, c_{2} = 1, c_{3} = 2 and f(x) = max\{x − 3, \frac{1}{2}x − 1, \frac{1}{3}x − 2\} for each x ∈ R, that is,

f(x) = \{ \begin{matrix}\frac{1}{3}x − 2, & x ⩽ −6, \\ \frac{1}{2}x − 1, & −6 ⩽ x ⩽ 4, \\ x − 3, & 4 ⩽ x. \end{matrix}

Hence S = {x ∈ R : f(x) ⩽ 0} = (−∞, 2] ≠ ∅. In this case, I = {1, 2, 3} and N (I) consists of three sets: \{1\}, \{2\} and \{1, 2\}. It is clear that μ = \frac{1}{2} and ν = \frac{1}{3}. It is easy to verify that, in the case, Lipschitz error bound constants in Ref.[3,10] are all 3. This shows that in this case, the Lipschitz constant \frac{1}{μ} = 2 in Theorem 4.4 is better. In fact, one can easily see that 2 is the best Lipschitz error bound constant in this case.

The proof of this theorem is based on its finite dimension version:

Lemma 4.5. Assume that X is finite dimensional and that dim(X)=dim(span{x_{i}^{∗} |1 ⩽ i ⩽ n}). Then Theorem 4.4 holds.

Proof. In view of Theorem 3.3 and Lemma 4.3, we need only prove that μ ⩽ δ. To do this, let x ∈ X \ S and x^{∗} ∈ ∂f(x). We have to show that μ ⩽ ∥x^{∗}∥. By (4.1), we can express x^{∗} as x^{∗} = ∑_{i∈I(x)} t_{i}x_{i}^{∗} for some t_{i} ⩾ 0 such that ∑_{i∈I(x)} t_{i} = 1.

We will find a normal set D ⊂ I containing I(x). Granting this, (4.3) implies that

τ_{D} ⩽ ∥ ∑_{i∈I(x)} t_{i}x_{i}^{∗}∥ (by taking t_{i} = 0 for each i ∈ D \ I(x)); hence μ ⩽ τ_{D} ⩽ ∥x^{∗}∥ as

required. Therefore it remains to find D with the stated properties. Since x is fixed, we write α > 0 for the constant f(x). Define the polyhetral sets A and B by

A = {y ∈ X|g_{i}(y) ⩽ α ∀i ∈ I} and B = {y ∈ A|g_{i}(y) = α ∀i ∈ I(x)}.

Note that B is an extreme subset of A. Moreover A contains no lines. For otherwise, there exists z ≠ 0 such that ⟨x_{i}^{∗}, z⟩ = 0 for all i ∈ I, contradicting the assumption that dim(X) = dim(span{x_{i}^{∗}|i ∈ I}). By Corollary 18.5.3 in [28], B must have at least one extreme point, say e. Then e is also an extreme point of A. Since e ∈ B ⊂ A, it is easy to verify that I(x) ⊂ I(e) and f(e) = f(x) = α. By Definition 4.2 and the definitions of A and B, it is clear that I(e) is a positive peak-set in I. Finally, we show that I(e) is full. Suppose to the contrary that dim(span{x_{i}^{∗}|i ∈ I(e)}) < dim(X). Then there exists z ∈ X \ {0} such that ⟨x_{i}^{∗}, z⟩ = 0 for each i ∈ I(e). Take ε > 0 small enough such that g_{i}(e ± εz) < 0 for each i ∈ I \ I(e). Then e ± εz ∈ B. This contradicts to the fact that e is an extreme point of B. Therefore, letting D = I(e), we see that D is a normal subset of I containing I(x), and the proof of Lemma 4.5 is completed.

Proof of Theorem 4.4. Let X_{0} = ⋂_{i=1}^{n} ker(x_{i}^{∗}). Then X/X_{0} is finite dimensional.

For each x ∈ X, let [x] denote the equivalent class containing x in X/X_{0}, that is,

[x] = x + X_{0}. Define x̂_{i}^{∗} ∈ (X/X_{0})^{∗} such that ⟨x̂_{i}^{∗}, [x]⟩ = ⟨x_{i}^{∗}, x⟩ for each x ∈ X and i ∈ I. It is clear that

(X/X_{0})^{∗} = span{x̂_{1}^{∗}, ⋯, x̂_{n}^{∗}}.

Let ĝ_{i}([x]) := ⟨x̂_{i}^{∗}, [x]⟩ − c_{i} and f̂([x]) = max{⟨x̂_{i}^{∗}, [x]⟩ − c_{i}|i ∈ I} for each [x] ∈ X/X_{0}. Let Ŝ = {[x] ∈ X/X_{0} : f̂([x]) ⩽ 0}. It is clear that Ŝ = {[x] : x ∈ S}. Hence dist(x, S) = dist([x], Ŝ) for each x ∈ X. Note that for each subset D of I, the norm of ∑_{i∈D} t_{i}x̂_{i}^{∗} is equal to the norm of ∑_{i∈D} t_{i}x_{i}^{∗} for any t_{i} ∈ R and i ∈ D. Moreover,

D is of the properties defined in Definitions 4.1and 4.2 with respect to the system {g_{i}(x) ⩽ 0, i ∈ I} if and only if D has the corresponding properties with respect to {ĝ_{i}^{∗}([x]) ⩽ 0, i ∈ I}. Therefore the constants μ, ν remain unchanged regardless whether with respect to {g_{i}} or {ĝ_{i}}. Therefore Theorem 4.4 follows from Lemma 4.5.

5. Error bound for a quadratic function on R^{n}. Consider a general quadratic function on R^{n}

f(x) = x^{⊥}Qx + b^{⊥}x + c,

where Q is a n × n symmetric matrix, b ∈ R^{n} and c ∈ R; x^{⊥} denotes the transpose of x. Since we do not assume f being of convexity, Q is not necessarily positive semidefinite. Recall that for a symmetric matrix Q, there exist an inversible matrix A, integer numbers k and m with 0 ⩽ k ⩽ m ⩽ n such that

A^{⊥}QA = ( \begin{matrix}I_{k} & 0 & 0 \\ 0 & −I_{m−k} & 0 \\ 0 & 0 & 0 \end{matrix} ) ,

where I_{k} and I_{m−k} are the k × k unit matrix and the (m − k) × (m − k) unit matrix, respectively. Define g(x) = f(Ax) for x ∈ R^{n}. Then

g(x) = ∑_{i=1}^{k} x_{i}^{2} − ∑_{i=k+1}^{m} x_{i}^{2} + ∑_{i=1}^{n} c_{i}x_{i} + c

= ∑_{i=1}^{k}(x_{i} + \frac{c_{i}}{2} )^{2} − ∑_{i=k+1}^{m}(x_{i} − \frac{c_{i}}{2} )^{2} + ∑_{i=m+1}^{n} c_{i}x_{i} + r,

where r = − ∑_{i=1}^{k} \frac{c_{i}^{2}}{4} + ∑_{i=k+1}^{m} \frac{c_{i}^{2}}{4} + c. Define

ϕ(x) = ∑_{i=1}^{k} x_{i}^{2} − ∑_{i=k+1}^{m} x_{i}^{2} + ∑_{i=m+1}^{n} c_{i}x_{i} + r, x = (x_{1}, ⋯, x_{n}) ∈ R^{n}. (5.1)

It is easy to verify that an error bound for g holds if and only if an error bound for ϕ holds. Notice also that S_{f} = AS_{g}, where S_{f} = {x ∈ X|f(x) ⩽ 0} and S_{g} = {x ∈ X|g(x) ⩽ 0}. It is clear that

∥A^{−1}∥^{−1}dist(A^{−1}x, S_{g}) ⩽ dist(x, S_{f}) ⩽ ∥A∥dist(A^{−1}x, S_{g}).

This implies that an error bound for f holds if and only if an error bound for g holds, and so if and only if an error bound for ϕ holds. In the remainder, we only consider an error for a quadratic function ϕ expressed in the ”normal” form (5.1). Clearly, for such a quadratic function ϕ, exactly one of the following six cases will happen ((C1) is the case that ϕ has linear terms where (C2-C6) are to deal with the remaining cases).

(C1) There exists i ∈ N such that m < i ⩽ n and c_{i} ≠ 0.

(C2) k < m, r ≠ 0 and c_{i} = 0 for all m < i ⩽ n.

(C3) 0 = k < m, r = 0 and c_{i} = 0 for all m < i ⩽ n.

(C4) 0 ≠ k < m, r = 0 and c_{i} = 0 for all m < i ⩽ n.

(C5) k = m, r ⩾ 0 and c_{i} = 0 for all m < i ⩽ n.

(C6) k = m, r < 0 and c_{i} = 0 for all m < i ⩽ n.

Theorem 5.1. Let ϕ be a quadratic function expressed in the form (5.1). Then any one of (C1), (C2), (C3) and (C6) implies that an error bound for ϕ holds, and any one of (C4) and (C5) implies that there is no error bounds for ϕ.

Proof. The case 1: (C1) is true. Without loss of generality, we can assume that c_{n} ≠ 0. Let h = (0, ⋯, 0, −sgn(c_{n})). Then ∥h∥ = 1. Notice that for each x = (x_{1}, ⋯, x_{n}) ∈ R^{n},

▽ϕ(x) = (2x_{1}, ⋯, 2x_{k}, −2x_{k+1}, ⋯, −2x_{m}, c_{m+1}, ⋯, c_{n}).

For each x ∈ R^{n} \ S,

\underline{d}^{+}ϕ(x)(h) = ⟨▽ϕ(x), h⟩ = −|c_{n}|.

Hence an error bound for ϕ holds by Theorem 2.5. The case 2: (C2) is true. Then

ϕ(x) = ∑_{i=1}^{k} x_{i}^{2} − ∑_{i=k+1}^{m} x_{i}^{2} + r.

This case is subdivided into three subcases.

(C2)_{1}: k = 0 and r < 0. Then S = R^{n}, and the result is trivial. (C2)_{2}: k ≠ 0 and r < 0. For each x ∈ R^{n} \ S, one has

∑_{i=1}^{k} x_{i}^{2} > ∑_{i=k+1}^{m} x_{i}^{2} + |r| ⩾ |r|.

Let

h_{x} = (−x_{1}, ⋯, −x_{k}, 0, ⋯, 0)/(∑_{i=1}^{k} x_{i}^{2})^{\frac{1}{2}} .

Then ∥h_{x}∥ = 1 and

d̄^{+}ϕ(x)(h_{x}) = ⟨▽ϕ(x), h_{x}⟩ = −2(∑_{i=1}^{k} x_{i}^{2})^{\frac{1}{2}} ⩽ −2|r|^{\frac{1}{2}} .

By Theorem 2.5, an error bound for ϕ holds.

(C2)_{3}: r > 0. For each x ∈ R^{n} \ S with ∑_{i=k+1}^{m} x_{i}^{2} ⩽ \frac{r}{2}, one has

ϕ(x) ⩾ ∑_{i=1}^{k} x_{i}^{2} + \frac{r}{2}. (5.2)

Pick a point y = (y_{1}, ⋯, y_{n}) ∈ R^{n} such that y_{i} = 0 for 1 ⩽ i ⩽ k, ∑_{i=k+1}^{m} x_{i}^{2} = r and

y_{i} = x_{i} for m < i ⩽ n. Then ϕ(y) = 0, and so

dist(x, S) ⩽ ∥x − y∥ ⩽ (∑_{i=1}^{k} x_{i}^{2})^{\frac{1}{2}} + 2r^{\frac{1}{2}} . (5.3)

Notice that there is a positive constant τ_{r} such that for t ⩾ 0,

\frac{t^{\frac{1}{2}} + 2r^{\frac{1}{2}}}{t + \frac{r}{2}} ⩽ τ_{r}.

It follows from (5.2) and (5.3) that for each x ∈ R^{n} \ S with ∑_{i=k+1}^{m} x_{i}^{2} < \frac{r}{2},

dist(x, S) ⩽ τ_{r}ϕ(x).

16 Kung Fu Ng and Xi Yin Zheng

Next consider those x in R^{n} \ S with ∑_{i=k+1}^{m} x_{i}^{2} > \frac{r}{2}, let

h_{x} = (0, ⋯, 0, x_{k+1}, ⋯, x_{m}, 0, ⋯, 0)/( ∑_{i=k+1}^{m} x_{i}^{2})^{\frac{1}{2}} .

Then ∥h_{x}∥ = 1 and for t ⩾ 0,

\underline{d}^{+}ϕ(x + th_{x})(h_{x}) = ⟨▽ϕ(x + th_{x}), h_{x}⟩ = −2 [( ∑_{i=k+1}^{m} x_{i}^{2})^{\frac{1}{2}} + t] ⩽ −(2r)^{\frac{1}{2}} .

Let

t_{x} = (∑_{i=1}^{k} x_{i}^{2} + r)^{\frac{1}{2}} − ( ∑_{i=k+1}^{m} x_{i}^{2})^{\frac{1}{2}} .

Then ϕ(x + t_{x}h_{x}) = 0 and t_{x} > 0 because x ∉ S. By Lemma 2.1, one has

−ϕ(x) = ϕ(x + t_{x}h_{x}) − ϕ(x) ⩽ −t_{x}(2r)^{\frac{1}{2}} .

It follows that

dist(x, S) ⩽ ∥x − (x + t_{x}h_{x}∥ = t_{x} ⩽ \frac{ϕ(x)}{(2r)^{\frac{1}{2}}} .

Therefore, letting τ = max\{τ_{r}, \frac{1}{(2r)^{\frac{1}{2}}} \}, we have shown that if (C2)_{3} is true then

dist(x, S) ⩽ τϕ(x) for all x ∈ R^{n} \ S.

The case 3: (C3) is true. Then S = R^{n}, and the result is trivial. The case 4: (C4) is true. Then

ϕ(x) = ∑_{i=1}^{k} x_{i}^{2} − ∑_{i=k+1}^{m} x_{i}^{2}, x ∈ R^{n}.

For t > 0, let x_{t} = (t, 0, …, 0). Then ϕ(x_{t}) = t^{2}. It is clear from dist(x_{t}, S) = dist(x_{t}, ∂S) that

dist(x_{t}, S) = inf{∥x_{t} − x∥|x ∈ R^{n}, ϕ(x) = 0}
= inf\{((x_{1} − t)^{2} + ∑_{i=2}^{n} x_{i}^{2})^{\frac{1}{2}} |x ∈ R^{n}, ∑_{i=1}^{k} x_{i}^{2} = ∑_{i=k+1}^{m} x_{i}^{2}\}
= inf\{[(x_{1} − t)^{2} + x_{1}^{2} + 2 ∑_{i=2}^{k} x_{i}^{2} + ∑_{i=m+1}^{n} x_{i}^{2}]^{\frac{1}{2}} |x_{i} ∈ R for each i\}
= inf\{[(x_{1} − t)^{2} + x_{1}^{2}]^{\frac{1}{2}} |x_{1} ∈ R\}
= \frac{t}{\sqrt{2}}.

Therefore,

lim_{t→0^{+}} \frac{dist(x_{t}, S)}{ϕ(x_{t})} = lim_{t→0^{+}} \frac{1}{\sqrt{2}t} = +∞.

This shows that there is no error bounds for ϕ.

The case 5: (C5) is true. If r > 0, S = ∅. We do not consider this trivial case as

stated at the beginning. If r = 0, then ϕ(x) = ∑_{i=1}^{k} x_{i}^{2} and S = {0}. For t > 0, let

x_{t} = (t, 0, ⋯, 0). Then

lim_{t→0^{+}} \frac{dist(x_{t}, S)}{ϕ(x_{t})} = lim_{t→0^{+}} \frac{t}{t^{2}} = +∞.

This implies that there are no error bounds for ϕ.

The case 6: (C6) is true. Then ϕ(x) = ∑_{i=1}^{k} x_{i}^{2} − |r|. It follows as the part (C2)_{2} of the

case 2 that an error bound for ϕ holds.

Notes added in revision. After the submission of this paper, the authors further carried out, in a follow-up paper [25], a detailed analysis on the issue of error bounds with fractional exponents. The Luo-Sturm inequality for quadratic functions (recently established in [21])

dist(x, S) ⩽ τ(|ϕ(x)| + |ϕ(x)|^{\frac{1}{2}} ).

is sharpened: we show that either the first term or the second term at the right hand side of the above Luo-Sturm inequality can be dropped. The approach of [25] is based on analysis of eigenvalues.

REFERENCES

[1] A. Auslender and J. P. Crouzeix, Global regularity theorems, Math. Oper. Res., 13 (1988), pp.243–253.

[2] C. Bergthaller and I. Singer, The distance to a polyhedron, Linear Algebra and its Applications 169 (1992), pp.111–129.

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

[4] W. L. Chan, L. R. Huang, and K. F. Ng, On generalized second-order derivatives and Taylor expansions in nonsmooth optimization, SIAM J. Control Optim., 32 (1994), pp.591–611.

[5] C. C. Chou, K. F. Ng and J. S. Pang, Minimizing and stationary sequences of constrained optimization problems, SIAM J. Control Optim., 36 (1998), pp.1908–1936.

[6] R. Cominetti and R. Correa, A generalized second-order derivative in nonsmooth optimization, SIAM J. Control Optim., 28 (1990), pp.789–809.

[7] F. H. Clarke, Optimization and Nonsmooth Analysis, John Wiley, New York (1983).

[8] S. Deng, Computable error bounds for convex inequality systems in reflexive Banach spaces, SIAM J. Optim., 7 (1997), pp.274–279.

[9] S. Deng, Global error bounds for convex inequality systems in Banach spaces, SIAM J. Control Optim., 36 (1998), pp.1240–1249.

[10] O. Guler, A. J. Hoffman and U. G. Rothblum, Approximations to solutions to systems of linear inequalities, SIAM Journal on Matrix Analysis and Applications 16 (1995), pp.688– [11] A. Hamel, Remarks to equivalent formulation of Ekeland’s variational principle, Optimization

31 (1994), pp.233-238.

[12] Y. R. He, Private Communication.

[13] L. R. Huang, K. F. Ng and J. P. Penot, On minimizing and critical sequences in nonsmooth optimization, SIAM J. Optim (in press).

[14] A. J. Hoffman, On approximate solutions of systems of linear inequalities, J. Res. Nat. Bur. Standards, 49 (1952), pp.263–265.

[15] D. Klatte and W. Li, Asymptotic constraint qualifications and error bounds for convex inequalities, Math. Programming 84 (1999), pp.137–160.

[16] 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, pp.75–100.

[17] W. Li, Error bounds for piecewise convex quadratic programs and applications, SIAM J. Control Optim., 33 (1995), pp.1510–1529.

[18] W. Li, Abadie’s constraint qualification, metric regularity, and error bounds for differentiable convex inequalities, SIAM J. Optim., 7 (1997), pp.966–978.

[19] X. D. Luo and Z. Q. Luo, Extensions of Hoffman’s error bound to polynomial systems, SIAM J. Optim., 4 (1994), pp.383–392.

[20] Z. Q. Luo and J. S. Pang, Error bounds for analytic systems and their applications, Math. Programming, 67 (1994), pp.1–28.

[21] Z. Q. Luo and J. F. Sturm, Error bounds for quadratic systems, Preprint.

[22] O. L. Mangasarian, A condition number for differentiable convex inequalities, Math. Oper. Res., 10 (1985), pp.175–179.

[23] O. L. Mangasarian and T. H. Shiau, Error bounds for monotone linear complementarity problems, Math. Programming, 36 (1986), pp.81–89.

[24] O. L. Mangasarian and T. H. Shau, A variable-complexity norm maximization problem, SIAM J. Alg. Discrete Methods 7 (1986), pp.455–461.

[25] K. F. Ng and X. Y. Zheng, Global error bounds with fractional exponents, Math. Programming (to appear).

[26] J. S. Pang, Error bounds in Mathematical programming, Math. Programming Ser. B, 79 (1997), pp.299–332.

[27] S. M. Robinson, An application of error bounds for convex programming in a linear space, SIAM J. Control 13 (1975), pp.271–273.

[28] R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton (1970).