Error Bounds for Some Convex Functions and Distance Composite Functions^{∗}

Kung Fu Ng^{†}and Wei Hong Yang^{‡}

Abstract. In this paper we study error bounds for function φ(x) = dist(Ax + b, K), where A is a continuous linear operator from a Banach space X into another Banach space Y, b ∈ Y and K ⊂ Y is a closed set. Assuming that A is of closed range Im(A), φ is shown to have a Lipschitz error bound (Υ-error bound) if and only if {Im(A) + b, K} is linearly regular (regular). Next we identify exactly when convex function g = \sqrt{ζ} − l has error bounds (of various types), where ζ is a quadratic function satisfying ζ ≥ 0 and l is an affine function on ℝ^{n}. As an application, we study the existence of various error bounds for the function φ : x ↦ dist(Ax + b, K) in supplementing the results reported in an earlier paper [?] for the standard second-order cone K in ℝ^{n}. Key words. abstract linear inequality system, error bound, regular, linearly regular, Robinson-Ursescu Theorem, Second-order cone AMS Subject Classifications. 90C31,90C25,49J52

1 Introduction and Notations

In generalizing the well-known fundamental result of Hoffman [?], Burke and Tseng studied in [?] the following convex set inclusion problem

Ax + b ∈ C  (1.1)

and derived general conditions ensuring that (??) has a Lipschitz error bound in the sense that there exists a constant τ > 0 such that

dist(x, S) ≤ τdist(Ax + b, C) ∀x ∈ X.  (1.2)

Here A is a continuous linear operator from a Banach space X (or a normed vector space) into another Banach space Y, b is an element of Y, C is a closed convex cone (or, more generally, a closed convex set) in Y, dist(y, C) denotes the distance from y to C while dist(x, S) has a similar meaning and, S denotes the solution set of (??):

S = {x ∈ X : Ax + b ∈ C}.  (1.3)

The results and the methods of [?] are mainly in terms of the (Fenchel) duality. In Section 3 of this paper, we will give conditions under which (??) has a Lipschitz error bound for any closed set K instead of C. Our conditions are in terms of b and the image Im(A) of A. In fact, we deal with not only the Lipschitz case but also what we call the Υ-error bounds (such as the Hölder error bounds, that is, error bounds with fractional exponents).

∗This research was supported by an Earmarked Grant from the Research Grant Council of Hong Kong

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

‡Department of Mathematics, Fudan University, Shanghai, P. R. China (whyang@fudan.edu.cn)

When Y = ℝ^{n}, in addition to the most important cone ℝ_{+}^{n}, there is another interesting and important cone K, consisting of all vectors x = (x_{1}, ⋯, x_{n}) ∈ ℝ^{n} such that

\sqrt{∑_{i=1}^{n−1} x_{i}^{2}} ≤ x_{n}.  (1.4)

This cone is the simplest second-order cone in ℝ^{n}, and it can be used to represent several common convex constraints in mathematical programming. There are several names for K: the standard second-order cone, ice-cream cone and Lorentz cone. See [?, ?] for further information. Many researchers have studied error bounds for second-order cone programming, see [?, ?, ?]. In [?], the authors gave a partial list for (??) with C = K to have a Lipschitz error bound. Luo and Sturm consider a Cartesian product of Secondorder cones in [?]. However their study in this connection was focused at the issue of requiring (??) to hold for x in a bounded set. In Section 5, we consider the global issue and give a complete list: by clarifying exactly when (??) with C = K has a Lipschitz error bound, or error bounds of other types. Our analysis is based on Section 4, where we study error bounds for function g of the form

g(x) = \sqrt{ζ(x)} − l(x) ∀x ∈ ℝ^{n},  (1.5)

where l is an affine function, ζ is a quadratic function on ℝ^{n} such that

ζ(y) ≥ 0 ∀y ∈ ℝ^{n}.  (1.6)

We thank Professor J.-S. Pang for helpful comments and valuable suggestions. We also thank the two referees whose suggestions have led many improvements on presentation and shortened proofs of many results. One referee points out that, for the convex case, one can use notions of recession cones/functions and apply some known error bound results such as Deng’s Theorem ([?, Theorem 2.3], see also a recent book by Zălinescu [?] especially Section 3.10 ) to provide different proofs of Theorem ?? and parts of Theorem ??.

2 Definitions and Preliminary Results

We use X, Y, Z ⋯ to denote Banach, normed or metric spaces. For a set K, int(K) and bd(K) denote the (topological) interior and the boundary of K respectively. Let B(x, r) denote the closed ball with center x and radius r. For a map T from X into Y, let Ker(T) and Im(T) denote the kernel and the image of T respectively. A linear operator from ℝ^{m} to ℝ^{n} is identified with matrix of order n × m. Thus the transpose Q^{T} of an n × m matrix Q is regarded as an adjoint operator from ℝ^{n} to ℝ^{m}. We use x, y, z … for vectors, m, n, k … for natural numbers and α, β, γ ⋯ for scalars. An element y in ℝ^{n} is represented as y = (y_{1}, ⋯, y_{n}). It is also identified with the “column” vector when it involves matrix calculations. For a scalar-valued function f : X → ℝ, the solution set of f is denoted by S_{f} = \{x ∈ X : f(x) ≤ 0\}. Let \underline{d}^{+}f(x)(h) denote the lower Dini-directional derivative of f at x along the direction h:

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

For a real number α, let α_{+} denote the number max{α, 0}. Let ϱ : ℝ^{n} → ℝ be defined by

ϱ(y) = \sqrt{∑_{i=1}^{n−1} y_{i}^{2}} − y_{n} ∀y ∈ ℝ^{n}.  (2.2)

Thus K = S_{ϱ}. The following lemma will be useful to us. Part (iii) is shown by Lewis and Pang [?] while other parts can be proved with ease: (i) holds because t ↦ t^{2} is strictly convex, (iv) follows from (i), and (ii) can be proved by the fact that {αs : α ≥ 0} is the normal cone of K at point u. We omit the details.

Lemma 2.1. Let K be defined by (??). Then we have the following:

(i) Let s, t ∈ K\{0}. Suppose that s is not a multiple of t. Then the open line-segment (t, s) is contained in int(K).

(ii) Let u = (u_{1}, ⋯, u_{n−1}, u_{n}) ∈ bd(K)\{0}, and s = (u_{1}, ⋯, u_{n−1}, −u_{n}). Then, for any h ∈ ℝ^{n}, ⟨s, h⟩ < 0 if and only if u + αh ∈ int(K) for some α > 0.

(iii) \frac{[ϱ(y)]_{+}}{\sqrt{2}} ≤ dist(y, K) ≤ [ϱ(y)]_{+} ∀y ∈ ℝ^{n}.

(iv) Suppose that L is a linear variety (a translate of a vector subspace) in ℝ^{n}. If 0 ∉ L and L ∩ int(K) = ∅, then L ∩ K is either empty or a singleton.

A function Υ : (0, +∞) → (0, +∞) is called an admissible function if Υ is nondecreasing and lim_{t→0} Υ(t) = 0. The set of all admissible functions is denoted by Γ.

Definition 2.1. Let Z be a metric space, and let Υ ∈ Γ. A lower semicontinuous function f : Z → (−∞, +∞] is said to have

(a) a Υ-error bound if

dist(x, S_{f}) ≤ Υ([f(x)]_{+}) ∀x ∈ Z.  (2.3)

(b) a Lipschitz error bound if there exists τ > 0 such that

dist(x, S_{f}) ≤ τ[f(x)]_{+} ∀x ∈ Z.  (2.4)

(c) a Hölder error bound with exponent γ ∈ (0, 1) if there exists τ > 0 such that

dist(x, S_{f}) ≤ τ[f(x)]_{+}^{γ} ∀x ∈ Z.  (2.5)

(d) a Robinson-Ursescu type error bound if there exist α, β > 0, γ ∈ (0, 1] and x̄ ∈ S_{f} such that

dist(x, S_{f}) ≤ (αdist(x, x̄) + β)[f(x)]_{+}^{γ} ∀x ∈ Z.  (2.6)

Remark 2.1. Let X, Y be normed spaces. If ĝ : X × Y → ℝ is defined by ĝ(x, y) := g(x), then g satisfies one of the conditions ((a), (b), (c) or (d)) if and only if ĝ satisfies the corresponding one (when X × Y is endowed with a usual norm, of type p for example ∥(x, y)∥ = (∥x∥^{p} + ∥y∥^{p})^{\frac{1}{p}} with p ≥ 1, or the box norm). Similarly, if A : X → Y is a homeomorphic linear operator and h = g ∘ A, then g satisfies one of the conditions ((a), (b), (c) or (d)) if and only if h satisfies the corresponding one.

Remark 2.2. Definition (a) is related to the notion of well-conditioned functions (see [?, Section 3.4] and the references therein); more precisely, f has a Υ-error bound for some Υ ∈ Γ if and only if f_{+} := max{f, 0} is well-conditioned. Definition (d) is inspired by Robinson-Ursescu Theorem (see [?, Theorem 9.48]). For a convex function f, if there exists x_{0} such that f(x_{0}) < 0, then f has a Robinson-Ursescu type error bound for γ = 1. Indeed, define set-valued function F : ℝ^{n} → 2^{ℝ} by F (x) = f(x)+[0, +∞). Then 0 belongs to the interior of the range of F and x_{0} ∈ F^{−1}(0) = S_{f}. By [?, Theorem 9.48], there exist α, β > 0 such that

dist(x, S_{f}) ≤ (α∥x − x_{0}∥ + β)[f(x)]_{+} ∀x ∈ ℝ^{n}.  (2.7)

The following proposition provides a concrete example of function f which has a Robinson-Ursescu type error bound but does not have a Υ-error bound for any Υ ∈ Γ; this function will be useful for our study in Section 4.

Proposition 2.1. Let m be a natural number such that m ≥ 2. Let η, ν ≥ 0 and let f : ℝ^{m} → ℝ be defined by

f(u_{1}, ⋯, u_{m}) = \sqrt{∑_{i=1}^{m} u_{i}^{2} + η} − u_{1} − ν.  (2.8)

Suppose that S_{f} is nonempty. Then, there exists a sequence {z^{k}} ⊂ ℝ^{m} such that

lim_{k→∞} f(z^{k}) = 0 and inf_{k} dist(z^{k}, S_{f}) > 0.  (2.9)

Consequently, for any Υ ∈ Γ, f does not have a Υ-error bound (a fortiori, f has neither a Lipschitz error bound nor a Hölder error bound).

Proof. Suppose that ν = 0. Since S_{f} ≠ ∅, one has that η = 0 and S_{f} = ℝ_{+} × {0}. For each k ∈ ℕ, let z^{k} be the vector in ℝ^{m} whose first two coordinates are k, 1 respectively and other coordinates are zero. Then {z^{k}} has the property stated in (??) because lim_{k→∞} f(z^{k}) = lim_{k→∞} \sqrt{k^{2} + 1} − k = 0 while dist(z^{k}, S_{f}) = 1 for each k ∈ ℕ.

Next we consider the case when ν > 0. For k large enough such that 2kν + ν^{2} − η > 0, let ξ_{k} := \sqrt{2kν + ν^{2} − η}. Then ξ_{k} → ∞ as k → +∞. Define sequences \{y^{k}\} and \{z^{k}\} in ℝ^{m} by y^{k} = (k, ξ_{k}, 0, ⋯, 0) and z^{k} = (k, ξ_{k} + 1, 0, ⋯, 0). Then {y^{k}} ⊂ bd(S_{f}), and {z^{k}} ⊂ ℝ^{m}\S_{f} has the desired property (??). In fact, it is easy to verify that f(y^{k}) = 0 and

f(z^{k}) = \sqrt{k^{2} + (2kν + ν^{2} − η + 2ξ_{k} + 1) + η} − k − ν
= \sqrt{(k + ν)^{2} + 2ξ_{k} + 1} − (k + ν)
= \frac{2ξ_{k} + 1}{\sqrt{(k + ν)^{2} + 2ξ_{k} + 1} + (k + ν)}
≤ \frac{2ξ_{k} + 1}{k + ν},

which implies that

0 ≤ lim_{k→∞} f(z^{k}) ≤ lim_{k→∞} \frac{2\sqrt{2kν + ν^{2} − η} + 1}{k + ν} = 0.

Observe that f is differentiable on ℝ^{m} if η > 0 and is differentiable on ℝ^{m}\{0} if η = 0. Moreover, ▽f(y^{k}) = (−\frac{ν}{k+ν} , \frac{ξ_{k}}{k+ν} , 0, ⋯, 0). Let L_{k} denote the tangent hyperplane of S_{f} at y^{k}. Then z^{k} and S_{f} lie in the opposite sides of L_{k} as ⟨z^{k} −y^{k}, ▽f(y^{k})⟩ = \frac{ξ_{k}}{k+ν} > 0. Hence

dist(z^{k}, S_{f}) ≥ dist(z^{k}, L_{k}) = ⟨\frac{▽f(y^{k})}{∥ ▽ f(y^{k})∥}, z^{k} − y^{k}⟩
= \frac{ξ_{k}}{\sqrt{ξ_{k}^{2} + ν^{2}}} → 1 as k → ∞.

Thus the second relation of (??) is seen to hold. To prove the last assertion, we assume for contradiction that there exists Υ ∈ Γ such that (??) holds. Then

0 < inf_{k} dist(z^{k}, S_{f}) ≤ lim_{k→∞} Υ(f(z^{k})) = 0,

which is a contradiction. This completes the proof.

Theorem 2.1. Let f : ℝ^{m} → ℝ be defined by (??). Suppose that η, ν ≥ 0 and S_{f} ≠ ∅. Then there exist α, β > 0, γ ∈ (0, 1] and x̄ ∈ S_{f} such that

dist(z, S_{f}) ≤ (α∥z − x̄∥ + β)[f(z)]_{+}^{γ} ∀z ∈ ℝ^{m}.  (2.10)

Proof. If ν > 0, then there exists x̄ such that f(x̄) < 0. It follows from (??) that (??) holds with γ = 1.

If ν = 0, then η = 0 and S_{f} = ℝ_{+} × {0} as noted before. Next we prove that

dist(z, S_{f}) ≤ (∥z∥ + 1)[f(z)]+^{\frac{1}{2}} ∀z ∈ ℝ^{m}.  (2.11)

Let z = (z_{1}, z_{2}, ⋯, z_{m}) ∈ ℝ^{m}. If z_{1} ≤ 0, then dist(z, S_{f}) = ∥z∥ and f(z) ≥ ∥z∥. Thus,

dist(z, S_{f}) ≤ 2∥z∥ ≤ (∥z∥ + 1)∥z∥^{\frac{1}{2}} ≤ (∥z∥ + 1)[f(z)]+^{\frac{1}{2}}.

If z_{1} > 0, then dist(z, S_{f}) = \sqrt{∑_{i=2}^{m} z_{i}^{2}}. Thus,

f(z) = \sqrt{∑_{i=1}^{m} z_{i}^{2}} − z_{1} = \frac{∑_{i=2}^{m} z_{i}^{2}}{\sqrt{∑_{i=1}^{m} z_{i}^{2}} + z_{1}} > \frac{d^{2}(z, S_{f})}{2∥z∥} ≥ \frac{d^{2}(z, S_{f})}{(1 + ∥z∥)^{2}} .

Therefore (??) holds.

We shall also need the following elementary fact.

Lemma 2.2. For η > 0, let ω : ℝ^{n} → ℝ^{n} be defined by ω(z) = \frac{z}{\sqrt{∥z∥^{2}+η}}. Then ω is

homeomorphic from ℝ^{n} onto the open unit ball.

Definition 2.2. (cf. [?, ?]) A pair {C_{1}, C_{2}} of closed sets in a metric space Z is said to be

(a) regular if for any sequence {x^{k}} in Z, it holds that

max{dist(x^{k}, C_{1}), dist(x^{k}, C_{2})} → 0 ⇒ dist(x^{k}, C_{1} ∩ C_{2}) → 0;  (2.12)

(b) linearly regular if there exists κ > 0 such that

dist(x, C_{1} ∩ C_{2}) ≤ κ max{dist(x, C_{1}), dist(z, C_{2})} ∀x ∈ Z.  (2.13)

3 Regularity and Error Bounds

Throughout this section, let A be a continuous linear operator from a Banach space X into a Banach space Y. For b ∈ Y, let T : X → Y be defined by T x = Ax + b for each x ∈ X. Let us begin with the following elementary result.

Lemma 3.1. Assume that Im(A) is closed. Let C be a nonempty subset of X such that

C + Ker(A) = C.  (3.1)

Then there exists α > 0 such that

αdist(x, C) ≤ dist(T x, T C) ≤ ∥A∥dist(x, C) ∀x ∈ X.  (3.2)

Proof. The second inequality of (??) is obvious. Let x̂ and Ĉ be the images of x and C by the natural quotient map of X onto X/Ker(A), which is endowed with the quotient norm. Let A^{−1} : Im(A) → X/Ker(A) denote the natural homeomorphism defined by A^{−1}(Ax) = x̂. By (??), it follows that

dist(x, C) = dist(x̂, Ĉ) = dist(A^{−1}(Ax), A^{−1}(AC))
≤ ∥A^{−1}∥dist(Ax, AC) = ∥A^{−1}∥dist(T x, T C) ∀x ∈ X.  (3.3)

This proves the first inequality of (??) with α := \frac{1}{∥A^{−1}∥}.

Let K be a closed set in Y. Let ψ : Im(T) → ℝ be defined by

ψ(y) = dist(y, K) ∀y ∈ Im(T),  (3.4)

and let φ : X → ℝ be defined by

φ = ψ ∘ T, i.e., φ(x) = ψ(T (x)) ∀x ∈ X.  (3.5)

Then S_{ψ} = Im(T) ∩ K = T (S_{φ}).

The following blanket assumptions will be assumed in what follows:

Im(A) is closed (hence Im(T)=Im(A)+b is also closed), and Im(T) ∩ K ≠ ∅. (3.6)

Theorem 3.1. Let ψ, φ be defined by (??), (??), and suppose that (??) holds. Then the following assertions are valid.

(a) There exists α > 0 such that

αdist(x, S_{φ}) ≤ dist(T x, S_{ψ}) ≤ ∥A∥dist(x, S_{φ}) ∀x ∈ X.  (3.7)

Consequently φ has an error bound of any type ((a), (b), (c) or (d) in Definition ??) if and only if ψ has the corresponding one.

(b) The following statements are equivalent: (i) φ has a Lipschitz error bound. (ii) ψ has a Lipschitz error bound. (iii) There exists k > 0 such that

dist(y, Im(T) ∩ K) ≤ kdist(y, K) ∀y ∈ Im(T).  (3.8)

(iv) {Im(T), K} is linearly regular.

(c) The following statements are equivalent: (i) φ has a Υ-error bound for some Υ ∈ Γ. (ii) ψ has a Υ-error bound for some Υ ∈ Γ. (iii) For any sequence {y^{k}} ⊂ Im(T),

lim_{k→∞} ψ(y^{k}) = 0 ⇒ lim_{k→∞} dist(y^{k}, S_{ψ}) = 0.  (3.9)

(iv) {Im(T), K} is regular. Proof. It is routine to verify that (??) is satified by C := S_{φ}. Since S_{ψ} = T C, by Lemma ??, it follows that (??) holds with α = \frac{1}{∥A^{−1}∥}. Next suppose that φ has a Robinson-Ursescu type error bound: there exists α, β > 0, γ ∈ (0, 1] and x̄ ∈ S_{φ} such that

dist(x, S_{φ}) ≤ (α∥x − x̄∥ + β)[φ(x)]_{+}^{γ} ∀x ∈ X.  (3.10)

For any y ∈ Im(T), there exist x, x^{k} ∈ X such that T x = T x^{k} = y and

∥x̄ − x^{k}∥ ≤ dist(x̄, x + Ker(A)) + \frac{1}{k}.  (3.11)

By (??), (??) and (??), one has that

dist(y, S_{ψ}) = dist(T x^{k}, S_{ψ}) ≤ ∥A∥dist(x^{k}, S_{φ})
≤ ∥A∥(α∥x^{k} − x̄∥ + β)[φ(x^{k})]_{+}^{γ}
≤ ∥A∥(α · dist(x̄, x + Ker(A)) + \frac{α}{k} + β)[ψ(y)]_{+}^{γ}
≤ ∥A∥(α∥A^{−1}∥dist(T x̄, y) + \frac{α}{k} + β)[ψ(y)]_{+}^{γ},  (3.12)

where (??) holds by Lemma ??. Note that T x̄ ∈ S_{ψ}. Letting k → ∞, we prove that ψ has a Robinson-Ursescu type error bound. The converse of this implication can be proved directly as well as for other parts of (a) regarding (a), (b) and (c) of Definition ??.

In particular, (i) ⇔ (ii) holds in (b) and in (c). By S_{ψ} = Im(T) ∩ K, (iii) ⇔ (iv) holds in (c) thanks to [?, Theorem 3.1 (a)]. Similarly, [?, Theorem 3.1 (b)] implies that (iii) ⇔ (iv) holds in (b). Since (iii) is simply a re-statement of (ii), (b) is proved. Finally, by [?, Corollary 3.1] (applied to the function ψ defined on the metric space Im(T)), one has (ii) ⇔ (iii) in (c); thus (c) is also proved.

4 Error Bounds for Convex Function g = \sqrt{ζ} − l

This section is devoted to study the error bound issues for a function g defined by

g(x) = \sqrt{ζ(x)} − l(x) ∀x ∈ ℝ^{n},  (4.1)

where l is an affine function and ζ is a quadratic function on ℝ^{n} such that

ζ(·) ≥ 0 on ℝ^{n}.  (4.2)

Note in particular that ζ must be convex. By an appropriate coordinate transform (by an affine map from ℝ^{n} onto itself) if necessary, we assume without loss of generality that ζ takes the form

ζ(x) = ∑_{i=1}^{m} x_{i}^{2} + η ∀x ∈ ℝ^{n},  (4.3)

where η ≥ 0 (because of (??)), and m ≤ n. Note that \sqrt{ζ} is a convex function. Let a ∈ ℝ^{n}, and ν ∈ ℝ be such that

l(x) = ⟨a, x⟩ + ν ∀x ∈ ℝ^{n}.  (4.4)

Throughout this section we make the following blanket assumptions:

S_{g} is nonempty, η ≥ 0 and (??)-(??) hold.  (4.5)

Theorem 4.1. Suppose there exists i_{0} > m such that a_{i_{0}} ≠ 0. Then g has a Lipschitz error bound.

Proof. Let h ∈ ℝ^{n} with \frac{a_{i_{0}}}{|a_{i_{0}}|} at the i_{0}th-coordinate and zero at the other coordinates. Then, for each x ∈ ℝ^{n}, one has that

\underline{d}^{+}g(x)(h) = −⟨a, h⟩ = −|a_{i_{0}}| < 0.

Hence g has a Lipschitz error bound by [?, Theorem 2.5].

In the rest of this section (except in Corollary ??), we further assume that

a_{i} = 0 for each i > m.  (4.6)

The following result implies that the consideration for error bounds for g can be reduced to that for error bounds for a simpler function.

Theorem 4.2. Under the assumptions (??) and (??), there exists a continuous linear operator Q : ℝ^{m} → ℝ^{n} such that

gQ(u) = \sqrt{∑_{i=1}^{m} u_{i}^{2} + η} − ∥a∥u_{1} − ν ∀u ∈ ℝ^{m},  (4.7)

where gQ is interpreted as the composite map.

Proof. Note that g(x) = g(y) if x, y ∈ ℝ^{n} and x_{i} = y_{i} for each i ≤ m. Let M be an orthonormal matrix of order m × m (with m rows and m columns) such that if a ≠ 0, the first column is composed of the first m coordinates of \frac{a}{∥a∥}, namely

m_{i1} = \frac{a_{i}}{∥a∥} ∀i = 1, ⋯, m;  (4.8)

if a = 0, we take M = I_{m×m}, the identity matrix. Let Q denote the matrix of order n×m:

Q = ( \begin{matrix}M \\ O_{(n−m)×m} \end{matrix} ) ,  (4.9)

that is, the first m rows of Q agree with that of M while the other rows are zero. Since (a_{1}, ⋯, a_{m}) is the ∥a∥-multiple of the first column of M and is perpendicular to the other columns, one has that

(a_{1}, ⋯, a_{m})Mu = ∥a∥u_{1} ∀u ∈ ℝ^{m}.

Moreover, by (??) and definition, one has that

ζ(Qu) = ∥Mu∥^{2} + η = (Mu)^{T} (Mu) + η = (u)^{T} u + η ∀u ∈ ℝ^{m}.

It follows that

g(Qu) = \sqrt{ζ(Qu) + η} − ⟨a, Qu⟩ − ν
= \sqrt{∑_{i=1}^{m} u_{i}^{2} + η} − ∥a∥u_{1} − ν ∀u ∈ ℝ^{m},

which verifies (??).

Corollary 4.1. Write g̃ for gQ. Then g̃ has an error bound of any type ((a), (b), (c) or (d) in Definition ??) if and only if g has the corresponding one.

Proof. By assumption (??) and identifying ℝ^{n} with ℝ^{m}×ℝ^{n−m}, we can define g_{1} : ℝ^{m} → ℝ by g_{1}(u) = g(x), where x = (u, v) ∈ ℝ^{n}. Write g̃ for gQ. By (??) and the definition of g_{1}, one has that g̃(u) = g(Qu) = g_{1}(Mu) = g_{1} ∘ M. Hence g̃ has an error bound of any type ((a), (b), (c) or (d) in Definition ??) if and only if g_{1} and so g has the corresponding one, where g_{1} can be replaced by g thanks to Remark ??.

Recall from definition and (??) that

g̃(u) = \sqrt{∥u∥^{2} + η} − ∥a∥u_{1} − ν ∀u ∈ ℝ^{m}.  (4.10)

Moreover, g̃ is convex, differentiable on ℝ^{m} if η > 0 and differentiable on ℝ^{m} \ {0} if η = 0. For any u ∈ ℝ^{m} (for u ≠ 0 if η = 0), one has that

▽g̃(u) = (\frac{u_{1}}{\sqrt{∥u∥^{2} + η}} − ∥a∥, \frac{u_{2}}{\sqrt{∥u∥^{2} + η}} , ⋯, \frac{u_{m}}{\sqrt{∥u∥^{2} + η}})  (4.11)
= \frac{u}{\sqrt{∥u∥^{2} + η}} − (∥a∥, 0, ⋯, 0).  (4.12)

Since S_{g} is assumed to be nonempty, Sg̃ ≠ ∅. The following lemma follows from (??) and the convexity of g̃.

Lemma 4.1. Assume that ∥a∥ < 1 and η > 0. Then ū = \{\frac{∥a∥\sqrt{η}}{\sqrt{1−∥a∥^{2}}} , 0, ⋯, 0\} is the

unique point in ℝ^{m} such that ▽g̃(ū) = 0. Moreover, ū is the unique minimum point of g̃ and,

g̃(ū) = 0 ⇔ \sqrt{(1 − ∥a∥^{2})η} = ν ⇔ Sg̃ = \{ū\}.  (4.13)

Theorem 4.3. Suppose that the assumptions (??), (??) are satisfied. In each of the following cases, g̃ (and so g) has a Lipschitz error bound.

(1) ∥a∥ > 1;

(2) ∥a∥ = 1 and m = 1;

(3) ∥a∥ < 1 and η = 0;

(4) ∥a∥ < 1, η > 0 and g̃(ū) < 0,

where ū is as in the preceding lemma.

Proof. (1): Suppose that ∥a∥ > 1. Let e^{1} = (1, 0, ⋯, 0). By (??), one has that

\underline{d}^{+}g̃(x)(e^{1}) ≤ 1 − ∥a∥ < 0 ∀x ∈ ℝ^{m}.

Then, by [?, Theorem 2.5], g̃ has a Lipschitz error bound.

(2): Suppose that ∥a∥ = 1 and m = 1. Then g̃ is defined on ℝ. If η = 0, then g̃(α) equals −ν for α ≥ 0 and −2α −ν for α < 0. It is trivial to see that g̃ has a Lipschitz error bound. Suppose that η > 0. Since Sg̃ is nonempty, it follows that ν > 0. Let ω := \frac{η−ν^{2}}{2ν}. Then Sg̃ = \{α ∈ ℝ : α ≥ ω\}. Since g̃′(α) = \frac{α}{\sqrt{α^{2}+η}} − 1 and \frac{α}{\sqrt{α^{2}+η}} is a strictly increasing

function, g̃′(α) < \frac{ω}{\sqrt{ω^{2}+η}} − 1 for each α ∉ Sg̃. Then by [?, Theorem 2.5] again, g̃ has a

Lipschitz error bound when η > 0.

(3): Then ν ≥ 0 (as Sg̃ is nonempty), and 0 ∈ Sg̃. Hence u ≠ 0 for each u ∉ Sg̃. For each u ≠ 0, by (??), one has ∥ ▽ g̃(u)∥^{2} = ∥\frac{u}{∥u∥} − ∥a∥e^{1}∥ ≥ dist(∥a∥e^{1}, S(0, 1)) = 1 − ∥a∥, where e^{1} = (1, 0, ⋯, 0) and S(0, 1) denotes the unit sphere (consisting of all unit vectors). Then inf{∥ ▽ g̃(x)∥ : x ∈ ℝ^{m}\Sg̃} ≥ 1 − ∥a∥ > 0. By [?, Theorem 2.5], g̃ has a Lipschitz error bound.

(4): By assumption, there exists a neighborhood V of ū such that V ⊂ Sg̃. By (??) and Lemma ??, ▽g̃(·) is a homeomorphism; since ▽g̃(ū) = 0, it follows that the image of V under ▽g̃(·) must contain a ball B(0, ϵ) in ℝ^{m} with some ϵ > 0 and hence that the image of ℝ^{m}\V is contained in ℝ^{m}\B(0, ϵ). Therefore ∥ ▽ g̃(u)∥ > ϵ for each u ∈ ℝ^{m}\V. Since V ⊂ Sg̃, one has that inf{∥ ▽ g̃(u)∥ : u ∈ ℝ^{m}\Sg̃} ≥ ϵ. Invoking [?, Theorem 2.5], g̃ has a Lipschitz error bound.

Next, we treat the case that g has a Υ-error bound but has neither a Lipschitz error bound nor a Hölder error bound.

Theorem 4.4. Suppose that the assumptions (??), (??) are satisfied. If ∥a∥ < 1, η > 0 and g̃(ū) = 0, where ū is as in Lemma ??, then g has neither Lipschitz error bound nor Hölder error bound, but there exists τ > 0 such that

dist(x, S_{g}) ≤ τ([g(x)]_{+} + [g(x)]+^{\frac{1}{2}}) ∀x ∈ ℝ^{n}.  (4.14)

Proof. To prove (??), we assume without loss of generality that g = g̃. Then the Hessian matrix H(ū) of g̃ at ū is positive definite. Indeed, H(ū) is a diagonal matrix (of zero

elements off the diagonal) with the first diagonal element \frac{(1−∥a∥^{2})^{\frac{3}{2}}}{\sqrt{η}} and other diagonal

elements \sqrt{\frac{1−∥a∥^{2}}{η}}. Take δ > 0 such that 2δ is smaller than the eigenvalues of H(ū). Since ▽g̃(ū) = 0 and g̃(ū) = 0, one has from the Taylor Theorem that

g̃(u) > δ∥u − ū∥^{2} ∀u ∈ W,  (4.15)

for some neighborhood W of ū. This and (??) imply that

dist(u, Sg̃) = ∥u − ū∥ ≤ \frac{1}{\sqrt{δ}} [g̃(u)]^{\frac{1}{2}} ∀u ∈ W.  (4.16)

On the other hand, take r > 0 such that

B(ū, 2r) ⊆ W.  (4.17)

Let V := B(ū, r). Since ∥a∥ < 1 and g̃ is coercive, there exists ξ > 0 such that ξ = inf_{x∈ℝ^{m}\V} g̃(x). Let f(u) := g̃(u) − \frac{ξ}{2} for each u ∈ ℝ^{m}. Then S_{f} ⊂ V. By (??) and Lemma ??, ▽g̃(·) is a homeomorphism; since ▽g̃(ū) = 0, it follows that the image of V under ▽g̃(·) must contain a ball B(0, ϵ) in ℝ^{m} with some ϵ > 0 and hence that the image of ℝ^{m}\V is contained in ℝ^{m}\B(0, ϵ). Thus,

∥ ▽ f(u)∥ = ∥ ▽ g̃(u)∥ > ϵ ∀u ∈ ℝ^{m}\V.

By [?, Theorem 2.5], we have

dist(u, V) ≤ dist(u, S_{f}) ≤ \frac{1}{ϵ}[f(u)]_{+} ≤ \frac{1}{ϵ}g̃(u) ∀u ∈ ℝ^{m}\V.  (4.18)

Now consider those u such that u ∈ ℝ^{m}\W. This and (??) as well as the definition of V imply that ∥u − ū∥ ≤ dist(u, V) + r ≤ 2dist(u, V). It follows from (??) that

dist(u, Sg̃) = ∥u − ū∥ ≤ \frac{2}{ϵ}g̃(u) ∀u ∈ ℝ^{m}\W.

Letting τ = max\{\frac{1}{\sqrt{δ}}, \frac{2}{ϵ}\}, combining the above with (??) we have

dist(u, Sg̃) ≤ τ([g̃(u)]_{+} + [g̃(u)]+^{\frac{1}{2}}) ∀u ∈ ℝ^{m}.  (4.19)

(recall that g̃(·) ≥ 0 on ℝ^{m} so one can write g̃(u) for [g̃(u)]_{+}). Invoking Theorem ??, (??) holds by (??).

Notice that g̃(ū) = 0 < g̃(u) for every u ≠ ū. Assume that there exist γ ∈ (0, 1] and τ > 0 such that ∥u − ū∥ ≤ τ[g̃(u)]^{γ} for every u ∈ ℝ^{m}. For γ = 1, we obtain that 1 ≤ τ ∥u∥^{−1} (g̃(ū + u) − g̃(ū)) for every u ≠ 0. Since ∇g̃(ū) = 0, taking the limit in the preceding inequality for u → 0, we get the contradiction 1 ≤ 0. For γ < 1, we get a contradiction by taking ∥u∥ → ∞ in the inequality 1 ≤ τ ∥u∥^{−1} (g̃(ū + u))^{γ}.

The only remaining case that we have not yet considered is: a_{i} = 0 for each i > m, ∥a∥ = 1 and m ≥ 2.

Theorem 4.5. Suppose that the assumptions (??), (??) are satisfied. If ∥a∥ = 1 and m ≥ 2, then g has a Robinson-Ursescu type error bound but does not have a Υ-error bound for any Υ ∈ Γ. Moreover, S_{g} is unbounded.

Proof. By assumptions, the function g̃ in (??) is seen to be of the same type studied in Proposition ?? and Theorem ??. Thus, Sg̃ is unbounded (seeing the Proof of Proposition ??), and g̃ has a Robinson-Ursescu type error bound but does not have a Υ-error bound for any Υ ∈ Γ. Consequently, by Corollary ??, we prove our assertion.

Corollary 4.2. Let g := \sqrt{ζ} −l, where l is an affine function and ζ is a quadratic function on ℝ^{n} such that ζ(x) ≥ 0 for each x ∈ ℝ^{n}. Suppose that g does not have a Lipschitz error bound and S_{g} is a singleton. Then the conclusions in Theorem ?? hold.

Proof. As already noted, Theorems ?? ,??, ?? and ?? exhaust all possible cases for g. But the cases of Theorems ?? and ?? cannot happen for g (because it does not have the Lipschitz error bound), nor can happen the case of Theorem ?? (because S_{g} is a singleton). Thus, we must be in the situation of Theorem ??.

5 Error Bounds for Inequality System with the Secondorder Cone

It would be convenient for us to summarize our notations that have been used and will continue to be in force throughout the whole section. Let X be a Banach space. Let A : X → ℝ^{n} be a continuous linear operator, b ∈ ℝ^{n}, and let T (x) := Ax + b for every x ∈ X. Let M = Im(A). Then Im(T) = M + b. Let m denote the dimension of M. Let Θ : ℝ^{m} → M + b be the function defined by

Θ(v) = v̂, ∀v ∈ ℝ^{m}, v̂ ∈ M + b such that v̂ = ∑_{i=1}^{m} v_{i}w^{i} + b,  (5.1)

where {w^{i}}_{i=1}^{m} is an orthonormal basis of M. Let ϱ be defined by (??). We use K to denote the second-order cone in ℝ^{n}. Let φ be defined by

φ(x) = dist(Ax + b, K) ∀x ∈ X  (5.2)

and let ψ be defined by

ψ(y) = dist(y, K) ∀y ∈ Im(T).  (5.3)

We assume that S_{φ} is nonempty, or equivalently

[Im(A) + b] ∩ K ≠ ∅.  (5.4)

Noting φ(−x) = dist(Ax − b, −K), it follows from [?, Theorem 5.7, 5.8, 5.9] that the function φ has a Lipschitz error bound if and only if one of the following cases happens:

(1) M ∩ int(K) ≠ ∅;

(2) M ∩ K = {0} and (M + b) ∩ int(K) ≠ ∅;

(3) M ∩ K = {0} and b ∈ M;

(4) {0} ≠ M ∩ K ⊂ bd(K) and dim(M) = 1.

Then there are two remaining cases to exhaust all the possibilities:

(a) {0} ≠ M ∩ K ⊂ bd(K) and dim(M) ≥ 2;

(b) M ∩ K = {0}, (M + b) ∩ int(K) = ∅ and b ∉ M.

These two cases will be studied here (respectively in Theorem ?? and ??). Before we present the two theorems, we need a preparatory lemma.

Lemma 5.1. For any orthonormal basis {w^{i}}_{i=1}^{m}, let Θ : ℝ^{m} → M + b be defined by (??). Let ϱ, φ and ψ be as already defined. Let g : ℝ^{m} → ℝ de defined by g = ϱ ∘ Θ. For any v ∈ ℝ^{m}, v̂ ∈ M + b such that v̂ = ∑_{i=1}^{m} v_{i}w^{i} + b, the following assertions hold:

(i) \frac{g(v)}{\sqrt{2}} ≤ ψ(v̂) ≤ g(v);

(ii) dist(v, S_{g}) = dist(v̂, S_{ψ});

(iii) φ has an error bound of any type ((a), (b), (c) or (d) in Definition ??) if and only if g has the corresponding one;

(iv) g can be expressed in the form (??) with an affine function l and a quadratic function ξ satisfying (??).

Proof. By Lemma ?? (iii), (i) follows directly. It is easy to see that ΘS_{g} = S_{ψ}. This and the isometry of Θ imply (ii). Since (i) and (ii) hold, ψ has an error bound of any type ((a), (b), (c) or (d) in Definition ??) if and only if g has the corresponding one, where ψ can be replaced by φ thanks to Theorem ??. Next we show that (iv) holds. Let e = (0, ⋯, 0, 1). One has that

g(v) = ϱ(Θv) = \sqrt{∥Θ(v)∥^{2} − ⟨Θ(v), e⟩^{2}} − ⟨Θ(v), e⟩ ∀v ∈ ℝ^{m}.  (5.5)

Thus

g(v) = \sqrt{ζ(v)} − l(v) ∀v ∈ ℝ^{m},  (5.6)

where

ζ(v) : = ∥Θ(v)∥^{2} − ⟨Θ(v), e⟩^{2} ∀v ∈ ℝ^{m},  (5.7)
l(v) : = ⟨Θ(v), e⟩ ∀v ∈ ℝ^{m}.

It is easy to see that l is an affine function, ζ is a quadratic function such that ζ(v) ≥ 0 for each v ∈ ℝ^{m}.

Theorem 5.1. Suppose that (??) holds and

{0} ≠ M ∩ K ⊂ bd(K) and dim(M) ≥ 2.  (5.8)

Then φ has a Robinson-Ursescu type error bound but does not have a Υ-error bound for any Υ ∈ Γ.

Proof. Let P_{M} denote the orthogonal projection onto M. We assume without loss of generality that b is perpendicular to M (replace b for b − P_{M}b if necessary). Our proof given below covers the case when b = 0. Let m be the dimension of M; then 2 ≤ m < n. Pick an unit vector e^{1} ∈ M ∩ K, and e^{2}, ⋯, e^{m} ∈ M such that {e^{i} : 1 ≤ i ≤ m} is an orthonormal base of M. By the assumption (??) it follows from Lemma ?? (i) that

M ∩ K = M ∩ bd(K) = {αe^{1} : α ≥ 0};  (5.9)

in particular e^{i}, e^{1} + αe^{i} ∉ K for all α ∈ ℝ and i ≥ 2. Let

e^{1} := (u_{1}, ⋯, u_{n−1}, u_{n}) and s := (u_{1}, ⋯, u_{n−1}, −u_{n}).

By Lemma ?? (ii), it follows that ⟨s, ±e^{i}⟩ ≥ 0; that is ⟨s, e^{i}⟩ = 0 for all i ≥ 2. Denoting the unit vector (0, ⋯, 0, 1) in ℝ^{n} by e, it follows that

⟨e, e^{i}⟩ = ⟨\frac{e^{1} − s}{2u_{n}}, e^{i}⟩ = 0 ∀i ≥ 2.  (5.10)

Let ϱ be defined by (??). Since e^{1} ∈ bd(K), it follows that

0 = ϱ(e^{1}) = \sqrt{1 − ⟨e^{1}, e⟩^{2}} − ⟨e^{1}, e⟩,

which implies that

⟨e^{1}, e⟩ = \frac{\sqrt{2}}{2}.  (5.11)

Each v̂ in M +b uniquely corresponds an element v ∈ ℝ^{m} such that v̂ = ∑_{i=1}^{m} v_{i}e^{i} +b, where

v = (v_{1}, ⋯, v_{m}). Define Θ by (??) with w^{i} := e^{i} for all i, namely

Θ(v) = v̂ = ∑_{i=1}^{m} v_{i}e^{i} + b ∀v = (x_{1}, ⋯, v_{m}) ∈ ℝ^{m}.  (5.12)

Let g be as in Lemma ??. By (??) and since {b, e^{1}, ⋯, e^{m}} is orthogonal, one has that, for each v ∈ ℝ^{m}, v̂ ∈ M + b such v̂ = Θ(v),

g(v) = ϱ(v̂) = \sqrt{(∑_{i=1}^{m} v_{i}^{2} + ∥b∥^{2}) − (∑_{i=1}^{m} v_{i}⟨e^{i}, e⟩ + ⟨b, e⟩)^{2}} − (∑_{i=1}^{m} v_{i}⟨e^{i}, e⟩ + ⟨b, e⟩). (5.13)

By (??) and (??), it follows that

g(v) = \sqrt{(∑_{i=1}^{m} v_{i}^{2} + ∥b∥^{2}) − (\frac{1}{\sqrt{2}}v_{1} + ⟨b, e⟩)^{2}} − (\frac{1}{\sqrt{2}}v_{1} + ⟨b, e⟩)

= \sqrt{\frac{1}{2}v_{1}^{2} + ∑_{i=2}^{m} v_{i}^{2} + ∥b∥^{2} − \sqrt{2}v_{1}⟨b, e⟩ − ⟨b, e⟩^{2}} − \frac{1}{\sqrt{2}}v_{1} − ⟨b, e⟩

= \sqrt{(\frac{1}{\sqrt{2}}v_{1} − ⟨b, e⟩)^{2} + ∑_{i=2}^{m} v_{i}^{2} + η} − (\frac{1}{\sqrt{2}}v_{1} − ⟨b, e⟩) − ν,  (5.14)

where η := ∥b∥^{2} − 2⟨b, e⟩^{2} and ν := 2⟨b, e⟩. By performing a homeomorphic affine transform if necessary, the function g can be deemed to be of the type considered in Theorem ??. Hence the conclusions of that theorem are enjoyed by this g and so by φ thanks to Lemma ?? (iii). Thus φ has a Robinson-Ursescu type error bound but does not have a Υ-error bound for any Υ ∈ Γ.

Theorem 5.2. Suppose that (??) holds,

b ∉ M, M ∩ K = {0} and (M + b) ∩ int(K) = ∅.  (5.15)

Then (M + b) ∩ K is a singleton and the following assertions hold:

(i) There exists τ > 0 such that

dist(x, S_{φ}) ≤ τ([φ(x)]+^{\frac{1}{2}} + [φ(x))]_{+} ∀x ∈ X.  (5.16)

(ii) There exists κ > 0 such that

dist(y, S_{ψ}) ≤ κ([ψ(y)]+^{\frac{1}{2}} + [ψ(y))]_{+} ∀y ∈ M + b,  (5.17)

where ψ is defined by (??).

(iii) φ and ψ have neither a Lipschitz error bound nor a Hölder error bound.

Proof. Let {w^{i}}_{i=1}^{m} be an orthonormal basis of M, let Θ and g be defined as in Lemma ??. Combing that lemma and Theorem ??, the functions φ, ψ and g have the equivalent error bound properties in the sense that one of the functions has an error bound of any type ((a), (b), (c) or (d) in Definition ??) if and only if the other two functions have the corresponding one. On the other hand, by (??) and (??), (M + b) ∩ K is a singleton and so is the set S_{ψ}. Since S_{ψ} = ΘS_{g} and Θ is one-one, S_{g} is also a singleton. In view of Lemma ?? (iv), one can apply Corollary ?? to conclude that g enjoys the conclusions of Theorem ??. With the help of Lemma ??, now it is a routine matter to verify the results. For instance, (??) follows from (??) and Lemma ?? (i), (ii).

References

[1] H. H. Bauschke, Projection Algorithms and Monotone Operators, Ph. D thesis, Simon Fraser University, Department of Mathematics,Burnaby, British Columbia V5A 1S6, Canada, August 1996. Available at http://www.cecm.sfu.ca/preprints/1996pp.html

[2] H. H. Bauschke and J. M. Borwein, On projection algorithms for solving convex feasibility problems, SIAM Rev., 38(1996), pp. 367–426.

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

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

[5] M. Fukushima, Z. Q. Luo, P. Tseng, Smoothing functions for second-order-cone complementarity problems, SIAM J. Optim. 12(2001), pp. 436–460.

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

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

[8] R.B.Holmes, Geometric Functional Analysis and its Applications, Graduate Texts in Mathematics, No.24. Springer-Verlag, New York-Heidelberg, 1975.

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

[10] M. S. Lobo, L. Vandenberghe, S. Boyd, H. Lebret, Applications of secondorder cone programming, Linear Algebra Appl, 284(1998), pp. 193–228.

[11] Z. Q. Luo and J. F. Sturm, Error bounds for quadratic inequality systems, in Frenk et al. (eds): High Performance Optimization, Kluwer Academic Publishers, 2000, pp. 383-404.

[12] Z. Q. Luo and J. F. Sturm, Error Analysis, in Wolkowicz et al. (eds): Handbook of Semidefinite Programming. Theory, algorithms and Applications, Kluwer Academic Publishers, 2000, pp. 163-189.

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

[14] K. F. Ng and X. Y. Zheng, Global weak sharp minima on Banach spaces, SIAM J. Control Optim., 41(2003), pp. 1868-1885.

[15] K. F. Ng and W. H. Yang, Error bounds for abstract linear inequality systems, SIAM J. Optim., 13(2002), pp. 24-43.

[16] K. F. Ng and W. H. Yang, Regularities and their relations to error bounds, Math. Program., Ser. A, 99(2004), pp. 521-538. 10.1007/s10107-003-0464-9.

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

[18] R. T. Rockafellar and R. J.-B. Wets, Variational Analysis, Springer-Verlag, Berlin, 1998.

[19] C. Zălinescu, Convex Analysis in General Vector Spaces, World Scientific, Singapore, 2002.