Global Error Bounds with Fractional Exponents^{∗}

Kung Fu Ng^{†} and Xi Yin Zheng^{‡}

July 22, 2000

Abstract Using the partial order induced by a proper weakly lower semicontinuous function on a reflexive Banach space X we give a sufficient condition for f to have error bounds with fractional exponents. Application is given to identify the set of such exponents for quadratic functions.

Key words. error bound, lower semicontinuous function, convex function, quadratic function, reflexive Banach space.

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

1 Introduction.

Let X be a normed space, f : X → R ⋃{+∞} a proper function, that is, dom(f) := {x ∈ X|f(x) < +∞} ≠ ∅, and let S = {x ∈ X|f(x) ≤ 0}. We always assume S ≠ ∅. For γ > 0, we say that f has an error bound with the exponent γ if there is a positive constant τ such that for each x ∈ X,

dist (x, s^{∗}) ≤ τ[f(x)]_{+}^{γ},

∗This research was supported by a direct grant (CUHK) and an Earmarked grant from the Research Grant Council of Hong Kong. Research of the second author was also supported by ABSF of Yunnan Province, P. R. China.

†Department of Mathematics, The Chinese University of Hong Kong, Shatin, New Territory, Hong Kong (kfngmath.cuhk.hk).

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

where dist (x, S) = inf{∥x − y∥|y ∈ S} and [f(x)]_{+} = max{f(x), 0}. The research on error bounds 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 recent surveys [1], [5] and references therein. However, most of the previous error bound results are with the exponent γ = 1. Luo and Luo [2], Luo and Pang [3] and Pang [5] were concerned with error bounds with fractional exponents. In this note, we further develop the techniques used in [4] (which deals the case of γ = 1) and prove a general existence result of fractional error bounds for lower semicontinuous functions. Differing from all earlier approach in the investigation of error bound theory, our proof is based on the consideration of the partial order induced by “Bishop-Phelps cone”.

After the completion of the first draft of the present paper, Professor J.S. Pang kindly informed us of the recent paper Luo and Sturm [L-S] which closely relates to our consideration here. We thank both Professor J.S. Pang and Professor Tom Luo for valuable advice subsequently given to us. Indeed the problem discussed in our section 3 is more restrictive than that in [L-S] where the general theme is on an inequality system in ℝ^{n} defined by finitely many continuous functions (with/without linear constraints). Theorem 3.1 of [L-S] is of particular relevance in the context of the setting of our section 3: that theorem of Luo and Sturm established for a single quadratic function that

dist (x, S) ≤ τ(|f(x)| + |f(x)|^{1/2}),  (L-S)

(where S := {x|f(x) = 0}, while S for the present paper is defined by S = {x|f(x) ≤ 0}). It turns out, from our results in section 3, that either the first or the second term on the right hand side in the above (L-S) inequality can be dropped and, moreover, one can identify exactly when which of these two alternatives will happen.

2 Main Results.

First, we need to make some preliminaries. Let X be a nonempty set. Recall that a partial order “ ⪯ ” in X is a reflexive, transitive and antisymmetric binary relation in X. For a subset A of X, a point a ∈ A is called a minimal element of A (with respect to ⪯) if a = x whenever x ∈ A and x ⪯ a. In the case that X is a topological space, we say that a partial order ⪯ in X is closed if S_{x} = {y ∈ X|y ⪯ x} is a closed subset of X for each x ∈ X.

Lemma 2.1 Let X be a topological space equipped with a closed partial order ⪯. Suppose that A is a nonempty compact subset of X. Then, for each a ∈ A, A has a minimal element a_{0} with a_{0} ⪯ a.

Proof. Let Σ be the family of all totally ordered subsets of A. For each a ∈ A, let Σ_{a} = {D ∈ Σ|x ⪯ a for each x ∈ D}. By Zorn’s Lemma, Σ_{a} has a minimal element with respect to the set inclusion. Let D_{0} ∈ Σ_{a} be such a minimal element. Then, the family {S_{x}|x ∈ D_{0}} has the finite intersection property (because D_{0} is a totally ordered subset of A). It follows from the compactness of A and the closedness of ⪯ that there exists a_{0} ∈ A such that a_{0} ∈ ⋂_{x∈D_{0}} S_{x}, that is, a_{0} ⪯ x for all x ∈ D_{0} ( in particular, a_{0} ⪯ a). This and the fact that D_{0} is a minimal element of Σ_{a} imply that a_{0} is a minimal element of A.

Theorem 2.2 Let X be a reflexive Banach space and f : X → R ⋃{+∞} a proper weakly lower semicontinuous function; let τ > 0 and γ > 0. Suppose that for each x ∈ dom(f)\S, there exists a sequence {x_{n}} in X such that x_{n} → x and for sufficiently large n,

0 < ∥x − x_{n}∥ ≤ τ[f^{γ}(x) − f^{γ}(x_{n})].

Then, for each x ∈ X,

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

Proof. Define a binary relation “ ⪯ ” in X as follows: for x, y ∈ X, x ⪯ y if and only if ∥x − y∥ ≤ τ([f(y)]_{+}^{γ} − [f(x)]_{+}^{γ}). It is easy to verify that ⪯ is a partial order in X (this partial order was used in [6, 7] for special case when f is a continuous linear functional). Since f is weakly lower semicontinuous, ⪯ is closed with respect to the weak topology of X. For any x ∈ dom(f) \ S and any r ∈ (0, dist (x, S)), it is clear that B(x, r) ⋂ S = ∅, that is, for any y ∈ B(x, r), f(y) > 0, where B(x, r) = {y ∈ X|∥y − x∥ ≤ r}. By the reflexivity of X, B(x, r) is weakly compact. By Lemma 2.1, there exists x_{0} ∈ B(x, r) such that x_{0} ⪯ x and x_{0} is a minimal element of B(x, r). We claim that ∥x_{0} − x∥ = r. Indeed, if this is not the case, then ∥x_{0} − x∥ < r, implying x_{0} ∉ S; also x_{0} ∈ dom(f) because x ∈ dom(f) and x_{0} ⪯ x. By the supposition, there exists y_{0} ∈ X such that

0 < ∥x_{0} − y_{0}∥ < r − ∥x − x_{0}∥ and ∥x_{0} − y_{0}∥ ≤ τ[f^{γ}(x_{0}) − f^{γ}(y_{0})].

It follows that x_{0} ≠ y_{0}, y_{0} ∈ B(x, r) and y_{0} ⪯ x_{0}, contradicting the minimality of x_{0} in B(x, r). Hence,

r = ∥x − x_{0}∥ ≤ τ[f^{γ}(x) − f^{γ}(x_{0})] < τf^{γ}(x).

Letting r → dist (x, S), we have

dist (x, S) ≤ τf^{γ}(x).

Corollary 2.3 Let X be a finite dimensional normed space and F : X → R ⋃{+∞} a proper lower semicontinuous function; let τ > 0 and γ > 0. Suppose that for each x ∈ dom(f) \ S, there exists a sequence {x_{n}} in X such that, for each n large enough,

0 < ∥x − x_{n}∥ ≤ τ[f^{γ}(x) − f^{γ}(x_{n})].

Then, for each x ∈ X,

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

The above corollary is an immediate consequence of Theorem 2.2, and the following corollary also follows from Theorem 2.2 because, for convex functions, the lower semicontinuity and the weak lower semicontinuity coincide.

Corollary 2.4 Let X be a reflexive Banach space and f : X → R ⋃{+∞} a proper lower semicontinuous convex function; let τ > 0 and γ > 0. Suppose that, for each x ∈ dom(f) \ S, there exists a sequence {x_{n}} such that, for each sufficiently large n,

0 < ∥x − x_{n}∥ ≤ τ[f^{γ}(x) − f^{γ}(x_{n})].

Then, for each x ∈ X,

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

For a proper lower semicontinuous convex function f : X → R ⋃{+∞}, let f^{∗} : X^{∗} → R ⋃{+∞} denote its conjugate function, that is, for each x^{∗} ∈ X^{∗},

f^{∗}(x^{∗}) = sup{⟨x^{∗}, x⟩ − f(x)|x ∈ X},

where X^{∗} is the dual space of X. In order to solve some convex mathematical programming problems, one often consider their conjugate problems. Thus, it is of importance to study error bounds for conjugate functions.

Theorem 2.5 Let X be a normed space and f : X → R ⋃{+∞} a proper lower semicontinuous convex function; let τ > 0 and γ > 0. Suppose that S^{∗} = {x^{∗} ∈ X^{∗}|f^{∗}(x^{∗}) ≤ 0} ≠ ∅ and that, for each x^{∗} ∈ dom(f^{∗}) \ S^{∗}, there exists a sequence {x_{n}^{∗}} in X^{∗} such that for sufficiently large n,

0 < ∥x^{∗} − x_{n}^{∗}∥ ≤ τ([f^{∗}(x^{∗})]^{γ} − [f^{∗}(x_{n}^{∗})]^{γ}).

Then, for each x^{∗} ∈ X^{∗},

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

Proof. Recall that every conjugate function is weak^{∗} lower semicontinuous and that every bounded weak^{∗} closed subset of X^{∗} is weak^{∗} compact. To prove Theorem 2.5, it suffices to repeat the argument of the proof of Theorem 2.2 to the weak^{∗} topology of X^{∗} in place of the weak topology of X.

Let f : X → R ⋃{+∞} and h ∈ X with ∥h∥ = 1. We say that f is directionally continuous in h at x ∈ X if lim_{t→0^{+}} f(x + th) = f(x). Clearly, for each h ∈ X with ∥h∥ = 1, f is directionally continuous in h at x if f is continuous at x.

Theorem 2.6 Let X be a reflexive Banach space and f : X → R ⋃{+∞} a proper weakly lower semicontinuous function; let δ > 0 and γ > 0. Suppose that for each x ∈ dom(f)\S, there exists h_{x} ∈ X with ∥h_{x}∥ = 1 such that f is directionally continuous in h_{x} at x and \underline{d}^{+}f(x)(h_{x}) ≤ −δf^{1−γ}(x), where

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

Then f has error bounds with the exponent γ.

Proof. For each x ∈ dom(f) \ S, f(x) > 0. Since f is directionally continuous in h_{x} at x, lim_{t→0^{+}}[f(x + th_{x}) − f(x)] = 0, and so 0 < f(x + th_{x}) < +∞ for sufficiently small t > 0. Hence, for sufficiently small t > 0,

f^{γ}(x + th_{x}) − f^{γ}(x) = γf^{γ−1}(x)(f(x + th_{x}) − f(x)) + o(f(x + th_{x}) − f(x)),

and so

\frac{f^{γ}(x + th_{x}) − f^{γ}(x)}{t} = [γf^{γ−1}(x) + \frac{o(f(x + th_{x}) − f(x))}{f(x + th_{x}) − f(x)}] \frac{f(x + th_{x}) − f(x)}{t}.

The second term in the above square braket converges to 0 by the directional continuity and it follows that

lim inf_{t→0^{+}} \frac{f^{γ}(x + th_{x}) − f^{γ}(x)}{t} = γf^{γ−1}(x)\underline{d}^{+}f(x)(h_{x}) ≤ −γδ < −\frac{γδ}{2} .

Hence there exists a sequence {t_{n}} in R^{+} \ {0} such that t_{n} → 0 and for each n,

\frac{f^{γ}(x + t_{n}h_{x}) − f^{γ}(x)}{t_{n}} ≤ −\frac{γδ}{2} .

Writing x_{n} for x + t_{n}h_{x}, one has

0 < ∥x − x_{n}∥ = t_{n} ≤ \frac{2}{γδ} [f^{γ}(x) − f^{γ}(x_{n})].

It follows from Theorem 2.2 that for each x ∈ X,

dist (x, S) ≤ \frac{2}{γδ} [f(x)]_{+}^{γ}.

For a proper function, the lower semicontinuity is weaker than the weak lower semicontinuity. In view of this and Theorem 2.6, the following problem is natural.

Problem. Is Theorem 2.6 true if f is only assumed lower semicontinuous?

The following corollaries provide affirmative answer of the above problem when either X is finite dimensional or f is convex, the former of which is immediate from Theorem 2.6.

Corollary 2.7 Let X be a finite dimensional normed space and f : X → R ⋃{+∞} a proper lower semicontinuous function, and let δ > 0 and γ > 0. Suppose that for each x ∈ dom(f) \ S, there exists h_{x} ∈ X with ∥h_{x}∥ = 1 such that f is directionally continuous in h_{x} at x and \underline{d}^{+}f(x)(h_{x}) ≤ −δf^{1−γ}(x). Then f has error bounds with the exponent γ.

Corollary 2.8 Let X be a reflexive Banach space and f : X → R ⋃{+∞} a proper lower semicontinuous convex function; let δ > 0 and γ > 0. Suppose that for each x ∈ dom(f) \ S, there exists h_{x} ∈ X with ∥h_{x}∥ = 1 such that \underline{d}^{+}f(x)(h_{x}) ≤ −δf^{1−γ}(x). Then f has error bounds with the exponent γ.

Proof. By Theorem 2.6 and the convexity of f, it suffices to show that f is directionally continuous in h_{x} at each x ∈ dom(f)\S. Since \underline{d}^{+}f(x)(h_{x}) ≤ −δf^{1−γ}(x) < 0, there exists t_{0} > 0 such that \frac{f(x+t_{0}h_{x})−f(x)}{t_{0}} < 0. Hence x + t_{0}h_{x} ∈ dom(f). By the convexity of f, for each t ∈ [0, t_{0}],

f(x + th_{x}) = f[(1 − \frac{t}{t_{0}} )x + \frac{t}{t_{0}} (x + t_{0}h_{x})] ≤ (1 − \frac{t}{t_{0}} )f(x) + \frac{t}{t_{0}} f(x + t_{0}h_{x}).

It follows that lim sup_{t→0^{+}} f(x + th_{x}) ≤ f(x). This and the lower semicontinuity of f imply that f is directionally continuous in h_{x} at x.

3 Applications to quadratic functions on R^{n}.

For convenience, we use the following notation. For f : X → R ⋃{+∞}, let E(f) = {γ > 0|f has an error bound with the exponent γ}. Then, E(f) is an interval if E(f) ≠ ∅ (Indeed, for any γ_{1}, γ_{2} ∈ E(f) with γ_{1} ≤ γ_{2}, there exist τ_{1} > 0 and τ_{2} > 0 such that for each x ∈ X \ S, dist (x, S) ≤ τ_{i}f^{γ_{i}}(x), i = 1, 2, and so

dist (x, S) ≤ max{τ_{1}, τ_{2}}min{f^{γ_{1}}(x), f^{γ_{2}}(x)}.

Since min{a^{γ_{1}}, a^{γ_{2}}} ≤ a^{γ} for any a > 0 and any γ ∈ [γ_{1}, γ_{2}], it follows that

dist (x, S) ≤ max{τ_{1}, τ_{2}}f^{γ}(x),

for all x ∈ X \ S). Consider a general quadratic function on R^{n}

f(x) = x^{T} Qx + b^{T} x + c, x ∈ R^{n},  (1)

where Q is a n × n symmetric matrix, b ∈ R^{n} and c ∈ R; x^{T} denotes the transpose of x. Let ker Q = {x ∈ R^{n}|f(x) = 0} and R(Q) = {Q(x)|x ∈ R^{n}}. Then ker Q ⊥ R(Q) and R^{n} = ker Q + R(Q). Hence the equation

2Qx = −b

has a solution if b ⊥ ker Q (i.e. b ∈ R(Q)). In what follows, let θ denote a solution of the equation 2Qx = −b under the case that b ⊥ ker Q.

The following result identifies the set E(f) for each of the possible cases.

Global Error Bounds with Fractional Exponents 8

Theorem 3.1 Let f be a quadratic function of the form (1). When b ⊥ ker Q, we have: (A1). If Q has both positive and negative eigenvalues and f(θ) = 0, E(f) = \{\frac{1}{2}\}. (A2). If Q has both positive and negative eigenvalues and f(θ) ≠ 0, E(f) = [\frac{1}{2}, 1]. (A3). If Q has positive eigenvalues and has no negative eigenvalues, and f(θ) = 0, E(f) =

\{\frac{1}{2}\}. (A4). If Q has positive eigenvalues and has no negative eigenvalues, and f(θ) < 0, E(f) =

[\frac{1}{2}, 1]. (A5). If Q has no negative eigenvalues and f(θ) > 0, E(f) = ∅. (A6). If Q has no positive eigenvalues and f(θ) ≤ 0, S = R^{n}. (A7). If Q has no positive eigenvalues and has negative eigenvalues, and f(θ) > 0, E(f) =

(0, 1]. When b is not vertical to ker Q, we have: (B1). If Q has no negative eigenvalues, E(f) = {1}. (B2). If Q has negative eigenvalues, E(f) = [\frac{1}{2}, 1].

To prove Theorem 3.1, we first make some notational arrangements. Let b_{0} be the projection of b to ker Q. Then b − b_{0} ⊥ ker Q. Hence the equation 2Qx = −(b − b_{0}) has a solution. Let θ be a solution of this equation (in particular, if b ⊥ ker Q, b_{0} = 0 and θ is a solution of the equation 2Qx = −b). Therefore,

f(x) = x^{T} Qx + b^{T} x + c = x^{T} Qx − 2θ^{T} Qx + b_{0}^{T} x + c
= (x − θ)^{T} Q(x − θ) + b_{0}^{T} (x − θ) + f(θ)  (2)

Since we are considering error bounds for f, without loss of generality we can assume that

f(x) = x^{T} Qx + b_{0}^{T} x + r, x ∈ R^{N},

where r is the value at θ of the given function in (2). Let X_{1} = {x ∈ R^{n}|Qx = λx for some λ > 0}, X_{2} = {x ∈ R^{n}|Qx = −λx for some λ > 0} and X_{3} = ker Q. Then

X_{i} ⊥ X_{j} (i ≠ j, i, j = 1, 2, 3), QX_{i} = X_{i} (i = 1, 2), R(Q) = X_{1} + X_{2} and R^{n} = X_{1} + X_{2} + X_{3}. Hence for each x ∈ R^{n} there exist x_{i} ∈ X_{i} (i = 1, 2, 3) such that x = x_{1} + x_{2} + x_{3} (in fact, x_{i} is the projection of x to X_{i} (i = 1, 2, 3)). For each x = x_{1} + x_{2} + x_{3} ∈ R^{n} (x_{i} ∈ X_{i}, i = 1, 2, 3), let

∥x∥_{e} = (x_{1}^{T} Qx_{1} − x_{2}^{T} Qx_{2} + ∥x_{3}∥^{2})^{\frac{1}{2}} .

Then ∥ · ∥_{e} is an equivalent norm on R^{n}. Thus, we only need to prove that Theorem 3.1 holds with respect to the dist ance induced by ∥ · ∥_{e}. It is easy to verify that for any x = x_{1} + x_{2} + x_{3} ∈ R^{n} (x_{i} ∈ X_{i}, i = 1, 2, 3),

f(x) = ∥x_{1}∥_{e}^{2} − ∥x_{2}∥_{e}^{2} + b_{0}^{T} x_{3} + r.  (3)

Lemma 3.2 Let Q have both positive and negative eigenvalues, and let b ⊥ ker Q. Then E(f) ⊂ [\frac{1}{2}, +∞). Moreover E(f) ⊂ \{\frac{1}{2}\} if f(θ) = 0 and E(f) ⊂ [\frac{1}{2}, 1] if f(θ) < 0.

Proof. By (3), f(x) = ∥x_{1}∥_{e}^{2} − ∥x_{2}∥_{e}^{2} + r for x = x_{1} + x_{2} + x_{3} ∈ R^{n} (x_{i} ∈ X_{i}, i = 1, 2, 3). Pick α > 0 and h ∈ X_{1} with ∥h∥ = 1 such that Qh = αh, and let X′_{1} = {x_{1} ∈ X_{1}|x_{1} ⊥ h}. Then X_{1} = Rh + X′_{1} and QX′_{1} = X′_{1}. For t > |r|^{\frac{1}{2}} , f(th) = t^{2} + r > 0 and

dist (th, S) = dist (th, ∂S)
= inf\{[∥x_{1} − th∥_{e}^{2} + ∥x_{2}∥_{e}^{2} + ∥x_{3}∥^{2}]^{\frac{1}{2}} | ∥x_{1}∥_{e}^{2} − ∥x_{2}∥_{e}^{2} + r = 0,
x_{i} ∈ X_{i}, i = 1, 2, 3}
= inf\{[∥x_{1} − th∥_{e}^{2} + ∥x_{1}∥_{e}^{2} + r]^{\frac{1}{2}} | ∥x_{1}∥_{e}^{2} + r ≥ 0, x_{1} ∈ X_{1}\}
= inf\{[(λ − t)^{2} + λ^{2} + 2∥x′_{1}∥_{e}^{2} + r]^{\frac{1}{2}} | λ^{2} + ∥x′_{1}∥_{e}^{2} + r ≥ 0,
λ ∈ R, x′_{1} ∈ X′_{1}}  (4)

Let g(λ, x′_{1}) = (λ − t)^{2} + λ^{2} + 2∥x′_{1}∥_{e}^{2} + r, (λ, x′_{1}) ∈ R × X′_{1}. Then the system

\frac{∂g}{∂λ} = 4λ − 2t = 0 and \frac{∂g}{∂x′_{1}} = 4x_{1}^{′^{T}} Q = 0  (5)

has a unique solution λ = \frac{t}{2} and x′_{1} = 0. Hence, for the case when r = 0, one has dist (th, S) = \frac{t}{\sqrt{2}} and so \frac{dist (th,S)}{\sqrt{f(th)}} = \frac{1}{\sqrt{2}} for all t > 0, implying that E(f) ⊂ \{\frac{1}{2}\}. For any

r ∈ R, it is easy to verify from (4) and (5) that dist (th, S) = (\frac{t^{2}}{2} + r)^{\frac{1}{2}} for t > 0 large enough, and so lim_{t→+∞} \frac{dist (th,S)}{\sqrt{f(th)}} = \frac{1}{\sqrt{2}} implying that E(f) ⊂ [\frac{1}{2}, +∞). Finally suppose that r < 0. Then the solution (\frac{t}{2}, 0) of (5) is not in the set \{(λ, x′_{1}) ∈ R×X′_{1}|λ^{2}+∥x′_{1}∥_{e}^{2}+r ≥ 0\} for t > |r|^{\frac{1}{2}} near enough to |r|^{\frac{1}{2}} . By (4) and (5), for t > |r|^{\frac{1}{2}} near enough to |r|^{\frac{1}{2}} ,

dist (th, S) = inf\{[(λ − t)^{2} + λ^{2} + 2∥x′_{1}∥_{e}^{2} − |r|]^{\frac{1}{2}} | λ^{2} + ∥x′_{1}∥_{e}^{2} − |r| = 0,
λ ∈ R, x′_{1} ∈ X′_{1}}
= inf\{[(λ − t)^{2} − λ^{2} + |r|]^{\frac{1}{2}} | λ^{2} ≤ |r|, λ ∈ R\} = t − |r|^{\frac{1}{2}} .

Hence lim_{t→\sqrt{|r|}^{+}} \frac{dist (th,S)}{f(th)} = \frac{1}{2\sqrt{|r|}}. This implies that E(f) must be disjoint from (1, +∞).

Combining with an earlier assertion, E(f) ⊂ [\frac{1}{2}, 1] for all r < 0.

The proof of Theorem 3.1. (A1): In this case, by (3), for any x = x_{1} + x_{2} + x_{3} ∈ R^{n} \ S (x_{i} ∈ X_{i}, i = 1, 2, 3), f(x) = ∥x_{1}∥_{e}^{2} − ∥x_{2}∥_{e}^{2} > 0. Pick h_{x} = \frac{−x_{1}}{∥x_{1}∥_{e}}. Then

df(x)(h_{x}) = −2∥x_{1}∥_{e} ≤ −2f^{\frac{1}{2}} (x).

By Corollary 2.7 and Lemma 3.2, E(f) = \{\frac{1}{2}\}. (A2): We subdivide it into the two cases: (A)_{1} is for the case r < 0 and (A)_{2} is for the case r > 0. (A2)_{1}: r < 0. In view of Lemma 3.2, we need only show that if σ ∈ [\frac{1}{2}, 1] then σ ∈ E(f). For any x = x_{1} + x_{2} + x_{3} ∈ R^{n} \ S (x_{i} ∈ X_{i}, i = 1, 2, 3), by (3) ∥x_{1}∥_{e}^{2} > ∥x_{2}∥_{e}^{2} + |r| ≥ |r|. Pick h_{x} = \frac{−x_{1}}{∥x_{1}∥_{e}}. Then,

df(x)(h_{x}) = −2∥x_{1}∥_{e} ≤ −2|r|^{\frac{2σ−1}{2}} f^{1−σ}(x).

By Corollary 2.7, it follows that σ ∈ E(f). (A2)_{2}: r > 0. Let σ ∈ [\frac{1}{2}, 1]. For any x = x_{1} + x_{2} + x_{3} ∈ R^{n} \ S with ∥x_{2}∥_{e} ≤ \frac{\sqrt{r}}{2},

f(x) = ∥x_{1}∥_{e}^{2} − ∥x_{2}∥_{e}^{2} + r ≥ ∥x_{1}∥_{e}^{2} + \frac{3}{4}r.

Pick x′_{2} ∈ X_{2} with ∥x′_{2}∥_{e}^{2} = r. Then f(x′_{2} + x_{3}) = 0. Hence

dist (x, S) ≤ ∥x_{1} + x_{2} + x_{3} − (x′_{2} + x_{3})∥_{e} = ∥x_{1} + (x_{2} − x′_{2})∥_{e}
= [∥x_{1}∥_{e}^{2} + ∥x_{2} − x′_{2}∥_{e}^{2}]^{\frac{1}{2}} ≤ (∥x_{1}∥_{e}^{2} + 3r)^{\frac{1}{2}} .

Therefore,

\frac{dist (x, S)}{f^{σ}(x)} ≤ \frac{(∥x_{1}∥_{e}^{2} + 3r)^{\frac{1}{2}}}{(∥x_{1}∥_{e}^{2} + \frac{3}{4}r)^{σ}} ≤ τ_{1},

where τ_{1} > 0 is a constant (which exists because σ ≥ \frac{1}{2}), and so

dist (x, S) ≤ τ_{1}f^{σ}(x)

is valid for all x ∈ R^{n}\S with ∥x_{2}∥_{e} ≤ \frac{\sqrt{r}}{2}. Next we consider those x = x_{1}+x_{2}+x_{3} ∈ R^{n}\S with ∥x_{2}∥_{e} > \frac{\sqrt{r}}{2}. Below we subdivide into two subcases.

a). x_{1} = 0. Pick h_{x} = \frac{x_{2}}{∥x_{2}∥_{e}}. Then for each t > 0 with f(x + th_{x}) > 0,

df^{σ}(x + th_{x})(h_{x}) = σf^{σ−1}(x + th_{x})∇f(x + th_{x})(h_{x})
= −2σ \frac{∥x_{2}∥_{e} + t}{[−(∥x_{2}∥_{e} + t)^{2} + r]^{1−σ}} ≤ −σr^{σ− \frac{1}{2}} ≤ −\frac{1}{τ_{2}} ,

where τ_{2} > 0 is a constant. It follows from the Mean-Value Theorem that there exist t_{0} > 0 and α ∈ (0, t_{0}) such that f(x + th_{x}) > 0 for each t ∈ (0, t_{0}), f(x + t_{0}h_{x}) = 0 and

−f^{σ}(x) = f^{σ}(x + t_{0}h_{x}) − f^{σ}(x) = t_{0}df^{σ}(x + αh_{x})(h_{x}) ≤ −\frac{t_{0}}{τ_{2}} .

Hence

dist (x, S) ≤ ∥x − (x + t_{0}h_{x})∥_{e} = t_{0} ≤ τ_{2}f^{σ}(x),

is valid for all x = x_{1} + x_{2} + x_{3} ∈ R^{n} \ S with x_{1} = 0 and ∥x_{2}∥_{e} > \frac{\sqrt{r}}{2}.

b). x_{1} ≠ 0. Pick h_{x} = \frac{1}{\sqrt{2}}(\frac{−x_{1}}{∥x_{1}∥_{e}} + \frac{x_{2}}{∥x_{2}∥_{e}}). Then, for any t ∈ (0, \sqrt{2}∥x_{1}∥_{e}] with f(x+th_{x}) > 0,

df^{σ}(x + th_{x})(h_{x}) = −2σ \frac{∥x_{1}∥_{e} − \frac{t}{\sqrt{2}} + ∥x_{2}∥_{e} + \frac{t}{\sqrt{2}}}{[(∥x_{1}∥_{e} − \frac{t}{\sqrt{2}})^{2} − (∥x_{2}∥_{e} + \frac{t}{\sqrt{2}})^{2} + r]^{1−σ}} · \frac{1}{\sqrt{2}}
≤ −2σ \frac{∥x_{1}∥_{e} − \frac{t}{\sqrt{2}} + \frac{\sqrt{r}}{2}}{[(∥x_{1}∥_{e} − \frac{t}{\sqrt{2}})^{2} + r]^{1−σ}} ≤ −\frac{1}{τ_{3}} ,

where τ_{3} > 0 is a constant (which exists because 1 ≥ 2(1 − σ)). If there exists t′ ∈ (0, \sqrt{2}∥x_{1}∥_{e}] such that f(x + t′h_{x}) = 0 and f(x + th_{x}) > 0 for all t ∈ (0, t′), then there exists α ∈ (0, t′) satisfying

−f^{σ}(x) = f^{σ}(x + t′h_{x}) − f^{σ}(x) = t′df^{σ}(x + αh_{x})(h_{x}) ≤ −\frac{t′}{τ_{3}}

and so

dist (x, S) ≤ ∥x − (x + t′h_{x})∥_{e} = t′ ≤ τ_{3}f^{σ}(x).

If f(x + th_{x}) > 0 for each t ∈ (0, \sqrt{2}∥x_{1}∥_{e}], then there exists β ∈ (0, \sqrt{2}∥x_{1}∥_{e}) such that

f^{σ}(x + \sqrt{2}∥x_{1}∥_{e}h_{x}) − f^{σ}(x) = \sqrt{2}∥x_{1}∥_{e}df^{σ}(x + βh_{x})(h_{x}) ≤ −\frac{\sqrt{2}∥x_{1}∥_{e}}{τ_{3}} .

According to a) above (applied to x + \sqrt{2}∥x_{1}∥_{e}h_{x} in place of x),

dist (x + \sqrt{2}∥x_{1}∥_{e}h_{x}, S) ≤ τ_{2}f^{σ}(x + \sqrt{2}∥x_{1}∥_{e}h_{x}).

Hence

dist (x, S) ≤ \sqrt{2}∥x_{1}∥_{e} + dist (x + \sqrt{2}∥x_{1}∥_{e}h_{x}, S)
≤ τ_{3}[f^{σ}(x) − f^{σ}(x + \sqrt{2}∥x_{1}∥_{e}h_{x})] + τ_{2}f^{σ}(x + \sqrt{2}∥x_{1}∥_{e}h_{x})
≤ max{τ_{2}, τ_{3}}f^{σ}(x).

Let τ = max\{τ_{1}, τ_{2}, τ_{3}\}. Then, for any σ ∈ [\frac{1}{2}, 1] and any x ∈ R^{n}\S, we have dist (x, S) ≤ τf^{σ}(x), showing that σ ∈ E(f) and hence that [\frac{1}{2}, 1] ⊂ E(f). In view of Lemma 3.2, it remains to prove that E(f) ⋂(1, +∞) = ∅. Pick α > 0 and h ∈ X_{2} with ∥h∥_{e} = 1 such that Qh = −αh. Let X′_{2} = {x′_{2} ∈ X_{2}| x′_{2} ⊥ h}. Then QX′_{2} = X′_{2} and X_{2} = Rh + X′_{2}. For any t ∈ (0, \sqrt{r}), f(th) = −t^{2} + r > 0 and

dist (th, S) = inf\{[∥x_{1}∥_{e}^{2} + ∥x_{2} − th∥_{e}^{2} + ∥x_{3}∥^{2}]^{\frac{1}{2}} | ∥x_{1}∥_{e}^{2} − ∥x_{2}∥_{e}^{2} + r = 0,
x_{i} ∈ X_{i}, i = 1, 2, 3}
= inf\{[∥x_{2}∥_{e}^{2} − r + ∥x_{2} − th∥_{e}^{2}]^{\frac{1}{2}} | ∥x_{2}∥_{e}^{2} ≥ r, x_{2} ∈ X_{2}\}
= inf\{[λ^{2} + (λ − t)^{2} − r + 2∥x′_{2}∥_{e}^{2}]^{\frac{1}{2}} | λ^{2} + ∥x′_{2}∥_{e}^{2} ≥ r,
λ ∈ R, x′_{2} ∈ X′_{2}}
= inf\{[λ^{2} + (λ − t)^{2} − r + 2∥x′_{2}∥_{e}^{2}]^{\frac{1}{2}} | λ^{2} + ∥x′_{2}∥_{e}^{2} = r,
λ ∈ R, x′_{2} ∈ X′_{2}}
= inf\{[(λ − t)^{2} − λ^{2} + r]^{\frac{1}{2}} | λ^{2} ≤ r, λ ∈ R\} = \sqrt{r} − t.

Hence lim_{t→\sqrt{r}^{−}} \frac{dist (th,S)}{f(th)} = \frac{1}{2\sqrt{r}}. This implies that E(f) ⋂(1, +∞) = ∅.

(A3): For any x = x_{1} + x_{2} + x_{3} ∈ R^{n} \ S (x_{i} ∈ X_{i}, i = 1, 2, 3), f(x) = ∥x_{1}∥_{e}^{2} > 0 and dist (x, S) = ∥x_{1}∥_{e} (because S = {x_{2} + x_{3}| x_{i} ∈ X_{i}, i = 1, 2} in this case). Therefore, E(f) = \{\frac{1}{2}\}.

(A4): For any x = x_{1} + x_{2} + x_{3} ∈ R^{n} \ S (x_{i} ∈ X_{i}, i = 1, 2, 3), f(x) = ∥x_{1}∥_{e}^{2} − |r| > 0. Hence ∥x_{1}∥_{e}^{2σ−1} ≥ |r|^{\frac{2σ−1}{2}} and ∥x_{1}∥_{e}^{2(1−σ)} ≥ f^{1−σ}(x) whenever σ ∈ [\frac{1}{2}, 1]. Let h_{x} = \frac{−x_{1}}{∥x_{1}∥_{e}}. Then,

df(x)(h_{x}) = −2∥x_{1}∥_{e} ≤ −2|r|^{\frac{2σ−1}{2}} f^{1−σ}(x).

By Corollary 2.7, σ ∈ E(f) and [\frac{1}{2}, 1] ⊂ E(f). Noticing that S = \{x_{1} + x_{2} + x_{3}| ∥x_{1}∥_{e} ≤ \sqrt{|r|}, x_{i} ∈ X_{i}, i = 1, 2, 3\},

lim_{∥x_{1}∥_{e}→∞^{x_{1}∈X_{1}}} \frac{dist (x_{1}, S)}{f^{\frac{1}{2}} (x_{1})} = 1 and lim_{∥x_{1}∥_{e}→\sqrt{|r|}^{+}^{x_{1}∈X_{1}}} \frac{dist (x_{1}, S)}{f(x_{1})} = \frac{1}{2\sqrt{|r|}}.

It follows that E(f) ⊂ [\frac{1}{2}, 1]. Hence E(f) = [\frac{1}{2}, 1].

(A5) and (A6) are trivial.

(A7). In this case, S = {x_{1} + x_{2} + x_{3} ∈ R^{n}| ∥x_{2}∥_{e}^{2} ≥ |r|, x_{i} ∈ X_{i}, i = 1, 2, 3}. Hence dist (x, S) = \sqrt{|r|} − ∥x_{2}∥_{e}, and so for σ ∈ (0, 1],

\frac{dist (x, S)}{f^{σ}(x)} = \frac{\sqrt{|r|} − ∥x_{2}∥_{e}}{(|r| − ∥x_{2}∥_{e}^{2})^{σ}} = \frac{(\sqrt{|r|} − ∥x_{2}∥_{e})^{1−σ}}{(\sqrt{|r|} + ∥x_{2}∥_{e})^{σ}} ≤ |r|^{\frac{1−2σ}{2}} .

It follows that σ ∈ E(f) and hence that (0, 1] ⊂ E(f). Since

lim_{∥x_{2}∥_{e}→\sqrt{|r|}^{−}^{x_{2}∈X_{2}}} \frac{dist (x_{2}, S)}{f(x_{2})} = \frac{1}{2\sqrt{|r|}},

E(f) is disjoint from (0, +∞). Consequently E(f) = (0, 1]. For the remainder of our proof, we assume that b is not vertical to ker Q, that is, b_{0} ∈ X_{3} \ \{0\}. Pick h = \frac{−b_{0}}{∥b_{0}∥}, Then for each x ∈ R^{n}, df(x)(h) = 2x^{T} Qh + b_{0}^{T} h = −∥b_{0}∥. By Corollary 2.7, it follows that 1 ∈ E(f).

(B1): In this case, for each x = x_{1} + x_{2} + x_{3} ∈ R^{n} (x_{i} ∈ X_{i}, i = 1, 2, 3), f(x) = ∥x_{1}∥_{e}^{2} + b_{0}^{T} x_{3} + r. For each t > 0, let x_{t} = (t + t_{0})b_{0}, where t_{0} = \frac{−r}{∥b_{0}∥^{2}} . Then f(x_{t}) = t∥b_{0}∥^{2} > 0 and

dist (x_{t}, S) = inf\{[∥x_{1}∥_{e}^{2} + ∥x_{2}∥_{e}^{2} + ∥x_{3} − x_{t}∥^{2}]^{\frac{1}{2}} | ∥x_{1}∥_{e}^{2} + b_{0}^{T} x_{3} + r = 0,
x_{i} ∈ X_{i}, i = 1, 2, 3}
= inf\{[−b_{0}^{T} x_{3} − r + ∥x_{3} − x_{t}∥^{2}]^{\frac{1}{2}} | b_{0}^{T} x_{3} + r ≤ 0, x_{3} ∈ X_{3}\}
= inf\{[−b_{0}^{T} y_{3} + ∥y_{3} − tb_{0}∥^{2}]^{\frac{1}{2}} | b_{0}^{T} y_{3} ≤ 0, y_{3} ∈ X_{3}\}
= inf{[∥y_{3} − tb_{0}∥| b_{0}^{T} y_{3} = 0, y_{3} ∈ X_{3}} = t∥b_{0}∥,

where the third equality holds because X_{3} is a linear subspace of R^{n} containing b_{0}. Hence, for each t > 0, \frac{dist (x_{t},S)}{f(x_{t})} = \frac{1}{∥b_{0}∥}. Therefore, E(f) ⊂ \{1\}. Combining an earlier assertion, E(f) = {1}.

(B2): For any x = x_{1} + x_{2} + x_{3} ∈ R^{n} \ S (x_{i} ∈ X_{i}, i = 1, 2, 3), ∥x_{2}∥_{e}^{2} < ∥x_{1}∥_{e}^{2} + b_{0}^{T} x_{3} + r. Let

y_{x} = \{ \begin{matrix}x_{1} + \frac{(∥x_{1}∥_{e}^{2}+b_{0}^{T} x_{3}+r)^{\frac{1}{2}}}{∥x_{2}∥_{e}} x_{2} + x_{3} & x_{2} ≠ 0 \\ x_{1} + (∥x_{1}∥_{e}^{2} + b_{0}^{T} x_{3} + r)^{\frac{1}{2}} x′_{2} + x_{3} & x_{2} = 0 \end{matrix}

where x′_{2} ∈ X_{2} with ∥x′_{2}∥_{e} = 1. Then f(y_{x}) = 0. Hence

dist (x, S) ≤ ∥x − y_{x}∥_{e} = (∥x_{1}∥_{e}^{2} + b_{0}^{T} x_{3} + r)^{\frac{1}{2}} − ∥x_{2}∥_{e} ≤ f^{\frac{1}{2}} (x)

showing that \frac{1}{2} ∈ E(f). Since 1 ∈ E(f), as noted earlier it follows that [\frac{1}{2}, 1] ⊂ E(f). For each t > 0 and x_{t} as in the proof of (B1), f(x_{t}) = t∥b_{0}∥^{2} and

dist (x_{t}, S) = inf\{[∥x_{1}∥_{e}^{2} + ∥x_{2}∥_{e}^{2} + ∥x_{3} − x_{t}∥^{2}]^{\frac{1}{2}} | ∥x_{1}∥_{e}^{2} − ∥x_{2}∥_{e}^{2} + b_{0}^{T} x_{3} + r = 0,

x_{i} ∈ X_{i}, i = 1, 2, 3}

= inf\{[2∥x_{1}∥_{e}^{2} + b_{0}^{T} y_{3} + ∥y_{3} − tb_{0}∥^{2}]^{\frac{1}{2}} | ∥x_{1}∥_{e}^{2} + b_{0}^{T} y_{3} ≥ 0,
x_{1} ∈ X_{1}, y_{3} ∈ X_{3}}

It is easy to verify that dist (x_{t}, S) = (t − \frac{1}{4})^{\frac{1}{2}} ∥b_{0}∥ for t > 0 large enough and that dist (x_{t}, S) = t∥b_{0}∥ for t > 0 small enough. Hence

lim_{t→+∞} \frac{dist (x_{t}, S)}{f^{\frac{1}{2}} (x_{t})} = 1 and lim_{t→0^{+}} \frac{dist (x_{t}, S)}{f(x_{t})} = \frac{1}{∥b_{0}∥}.

It follows that E(f) ⊂ [\frac{1}{2}, 1], and hence that E(f) = [\frac{1}{2}, 1].

The following result was kindly pointed out to us by Professor Tom Luo when he commented on the connection of our work to his joint paper [L-S] with J. F. Sturm.

Corollary 3.3 Let s^{∗} denote the zero set of a quadratic function f on R^{n} to R:

s^{∗} = {x|f(x) = 0}.

We suppose that s^{∗} ≠ ∅. Then there exists some constant τ > 0 such that for all x in ℝ^{n},

dist (x, s^{∗}) ≤ τϕ(x)  (6)

where ϕ is either the absolute function |f| or its square root function |f|^{1/2} .

Proof. Note first that dist (x, s^{∗}) = dist (x, S) as the latter is the same as the distance of x to the topological boundary of S. The same holds also when S is replaced by the set {x| − f(x) ≤ 0}. If b is not vertical to ker Q then, by Theorem 3.1, 1 ∈ E(f) ∩ E(−f) and (6) is seen to hold with ϕ(x) = |f|. If f satisfies (A3) then 1/2 ∈ E(f) and f ≥ 0 and so (6) is seen to hold with ϕ(x) = |f(x)|^{1/2}. If f satisfies (A4), equivalently if −f satisfies (A7), then 1 ∈ E(f) ∩ E(−f) and so (6) holds with ϕ(x) = |f(x)|. Similar argument applies to the case when f satisfies (A7). For each of (A5) and (A6), the result in this corollary holds trivially. Finally, (A1) implies that E(±f) = {1/2} and (A2) implies that E(±f) = [1/2, 1], therefore Corollary 3.3 is also verified in each of these cases.

Corollary 3.3 is a refinement of [L-S, Theorem 3.1] where the function on the right hand side of (6) was replaced by the sum {|f(x)| + |f(x)|^{1/2}}. On the other hand, the general theme of [L-S] is broader than the scope of our present work: for instance the constrained system (of a single quadratic function with linear constraints) was addressed in [L-S]. We end the paper with the following corollary the proof of which is as in the proof of the preceding corollary.

Corollary 3.4 Let f be a quadratic function of the form (1) with the zero set s^{∗} ≠ ∅, ℝ^{n}. Let e(f) denote the set of all γ > 0 for each of which there exists τ > 0 such that

dist (x, s^{∗}) ≤ τ|f(x)|^{γ}, for all x ∈ R^{n}.

When b ⊥ ker Q, we have:

Global Error Bounds with Fractional Exponents 16

(C1) If f(θ) = 0 then e(f) = \{\frac{1}{2}\}. (C2) If f(θ) ≠ 0 then λf(θ) < 0 for some eigenvalue λ of Q and e(f) = [\frac{1}{2}, 1]. When b is not vertical to ker Q, we have: (D1) If the eigenvalues of Q are of the same sign, e(f) = {1}. (D2) If some eigenvalues of Q are of opposite signs, e(f) = [\frac{1}{2}, 1].

References

[1] 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.

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

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

[4] K. F. Ng and X. Y. Zheng, Error bounds for continuous functions (submitted).

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

[6] B. Peleg, On a theorem of Arrow, Barankin, and Blackwell, SIAM J. Control Optim., 28 (1990), pp. 395–401.

[7] R. R. Phelps, Support cones in Banach spaces and their applications, Advances in Math., 13 (1974), pp. 1–19.

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