The Least Hoffman’s Error Bound for Linear Inequality System ^{∗}

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

Abstract

Let E be a normed space, a_{1}^{∗}, ⋯, a_{m}^{∗} ∈ E^{∗}, c_{1}, ⋯, c_{m} ∈ R and S = {x ∈ E|⟨a_{i}^{∗}, x⟩ − c_{i} ≤ 0, 1 ≤ i ≤ m} ≠ ∅. Let τ_{∗} = inf{τ ≥ 0 : dist(x, S) ≤ τ max{[⟨a_{i}^{∗}, x⟩ − c_{i}]_{+} : i = 1, ⋯, m} ∀x ∈ X}. We give some exact formulas for τ_{∗}.

1. Introduction

Let E be a normed space and E^{∗} the dual space of E. Let a_{1}^{∗}, ⋯, a_{m}^{∗} ∈ E^{∗}, c_{1}, ⋯, c_{m} ∈ R and S denote the solution set of the following inequality system

⟨a_{i}^{∗}, x⟩ ≤ c_{i}, i = 1, ⋯, m.  (1)

Assuming that S is nonempty, the fundamental result of Hoffman [4] asserts that if E = R^{n} then there exists a constant τ > 0 such that

dist(x, S) ≤ τ[ϕ(x)]_{+}, ∀x ∈ E,  (2)

where ϕ(x) := max{⟨a_{i}^{∗}, x⟩ − c_{i} : i = 1, ⋯, m}. A coefficient τ satisfying (2) is called a Lipschitz bound of the sysytem (1). Let τ_{∗} denote the infimum of all Lipschitz bounds; namely

τ_{∗} = sup \{\frac{dist(x, S)}{[ϕ(x)]_{+}} : x ∈ E \ S\} .

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

†Department of Mathematics, The Chinese University of Hong Kong, Shatin, NT, Hong Kong

‡Department of Mathematics, The Chinese University of Hong Kong, Shatin, NT, Hong Kong

Since (1) has a Lipschitz error bound, τ_{∗} does exist of course (see also Theorem 2.2 in Burke and Ferris [2]), but the interest remains in expressing τ_{∗} in a simple way. We show in Theorem 2.3 that

τ_{∗} = \frac{1}{min\{γ_{D} : D ∈ W(I)\}}

where W(I) is a certain (finite) family of subsets of I and γ_{D} is defined by

γ_{D} = min{∥ ∑_{i∈D} α_{i}a_{i}^{∗}∥ : α_{i} ≥ 0, ∑_{i∈D} α_{i} = 1}.

Note that the subprogramme of computing γ_{D} is a convex minimization problem over a simplex. In particuler if E is finite dimensional with the Euclidean norm then that is a quadratic minimization problem while if E is finite dimensional with the l_{1}- or the l_{∞}-norm then that is simply a linear programming problem. Consequently τ_{∗} is given as a finitely computable object.

Lipschitz bounds are related to the convergence rate of algorithms appearing in many applications. Several authors considered the bounds, seeing Mangasarian and Shiau [9], Bergthaller and Singer [1], Li [8], Guler, Hoffman and Rothblum [4], Burke and Tseng [3] and references therein. Guler, Hoffman and Rothblum [4] (Theorem 3.2 with the maximum norm in R^{m}) proved that

τ_{1} := sup{∑_{i=1}^{m} λ_{i} : (λ_{1}, ⋯, λ_{m}) is an extreme point of σ(a_{1}^{∗}, ⋯, a_{m}^{∗})}  (3)

is an Lipschitz error bound, where

σ(a_{1}^{∗}, ⋯, a_{m}^{∗}) := {(λ_{1}, ⋯, λ_{m}) ∈ R_{+}^{m} : ∥ ∑_{i=1}^{m} λ_{i}a_{i}^{∗}∥ ≤ 1}.

Let

J := {D ⊂ I : {a_{i}^{∗} : i ∈ D} is linearly independent}.

Burke and Tseng [3] (Theorem 8), in the case when their cone K = R_{−}^{m} and X = R^{n}, proved that

τ_{2} := max{∑_{i∈D} λ_{i} : λ_{i} ≥ 0, ∥ ∑_{i∈D} λ_{i}a_{i}^{∗}∥ = 1, D ∈ J }.  (4)

is a Lipschitz error bound. As noted in Burke and Tseng [3], τ_{1} = τ_{2}. Let

Ĵ = {D ∈ J : there exists x ∈ S such that ⟨a_{i}^{∗}, x⟩ = c_{i} ∀i ∈ D}.

Bergthaller and Singer [1] (Theorem 1.3) proved that

τ_{3} := max{∑_{i∈D} λ_{i} : λ_{i} ≥ 0, ∥ ∑_{i∈D} λ_{i}a_{i}^{∗}∥ = 1, D ∈ Ĵ}  (5)

is also a Lipschitz error bound. Since Ĵ ⊂ J, τ_{2} ≤ τ_{3}.

Take E = R, a_{1}^{∗} = 1, a_{2}^{∗} = \frac{1}{2}, a_{3}^{∗} = \frac{1}{3}, a_{4}^{∗} = \frac{1}{4}, c_{1} = 3, c_{2} = 1, c_{3} = \frac{2}{3} and c_{4} = 1. Then

ϕ(x) = max\{a_{i}^{∗}x − c_{i} : 1 ≤ i ≤ 4\} = \{ \begin{matrix}\frac{1}{4}x − 1, & x ≤ −4, \\ \frac{1}{3}x − \frac{2}{3}, & −4 ≤ x ≤ 2, \\ \frac{1}{2}x − 1, & 2 ≤ x ≤ 4, \\ x − 3, & 4 ≤ x. \end{matrix}

Then S = {x ∈ R : ϕ(x) ≤ 0} = (−∞, 2]. In this case, J = {{i} : 1 ≤ i ≤ 4}, Ĵ = {{2}, {3}}. It is easy to verify that τ_{1} = τ_{2} = 4 < τ_{3} = 3 while 2 obtained by Theorems 2.2 and 2.3 is the least Lipschitz error bound. This shows that in general τ_{3} (a fortiori, τ_{1} and τ_{2}) is not the least Lipschitz error bound of the inequality system (1).

2. Main Results

Throughout this paper, let E denote a normed space, a_{1}^{∗}, ⋯, a_{m}^{∗} ∈ E^{∗} and c_{1}, ⋯, c_{m} ∈ R; let

S := {x ∈ E : ⟨a_{i}^{∗}, x⟩ ≤ c_{i}, i = 1, ⋯, m}.

We always assume that ∅ ≠ S ≠ E. Let I = {1, ⋯, m} and

ϕ(x) = max{⟨a_{i}^{∗}, x⟩ − c_{i} : i ∈ I} ∀x ∈ E.

Then S = {x ∈ E : ϕ(x) ≤ 0}. We use M(I) to denote the family of all subsets D of I suth that {a_{i}^{∗} : i ∈ D} is a maximal linearly independent subset of {a_{i}^{∗} : i ∈ I}.

Definition 2.1. We say that a subset D of I has property (W) if the following conditions hold.

(i) D ∈ M(I). (ii) Given a solution s_{D} of the linear equation system

⟨a_{i}^{∗}, x⟩ − c_{i} = 0 ∀i ∈ D  (6)

and a solution e_{D} of the linear equation system

⟨a_{i}^{∗}, x⟩ = 1 ∀i ∈ D,  (7)

one has ⟨a_{j}^{∗}, s_{D}⟩−c_{j} ≤ 0 for each j ∈ I \D and the strict inequality ⟨a_{j}^{∗}, s_{D}⟩−c_{j} < 0 holds whenever ⟨a_{j}^{∗}, e_{D}⟩ > 1 and j ∈ I \ D.

Let W(I) denote the family of all subsets of I with property (W). For each D ∈ W(I), let

τ_{D} := dist(e_{D}, C_{D})  (8)

where C_{D} := {x ∈ E : ⟨a_{i}^{∗}, x⟩ ≤ 0, i ∈ D}. Note from (i) of Definition 2.1 that both (6) and (7) have solutions and that ⋂_{i∈D} ker(a_{i}^{∗}) = ⋂_{i∈I} ker(a_{i}^{∗}). Therefore, for another

solution s′_{D} of the linear equation system (6), ⟨a_{i}^{∗}, s′_{D}⟩ = ⟨a_{i}^{∗}, s_{D}⟩ for each i ∈ I. In fact, the solution set of the linear equation system (6) is a linear variety parallelled to ⋂_{i∈I} ker(a_{i}^{∗}). Similar remarks hold for e_{D} and (7). Hence, to verify (ii) one need

only to do so for any one particular pair of solutions s_{D}, e_{D} of (6), (7) and hence W(I) is well defined; moreover τ_{D} does not depend on the particular choice of e_{D}.

Throughout, let τ_{∗} denote the least Lipschitz error bound for the inequality system (1), that is,

τ_{∗} = inf{τ > 0 : dist(x, S) ≤ τ[ϕ(x)]_{+}, ∀x ∈ E}.

Theorem 2.1. τ_{∗} = max{τ_{D} : D ∈ W(I)}.

The proof of this result is based on geometrically intuitive arguments but is rather intricate to verify in details. We postpone the proof to the next section.

Theorem 2.2. For each D ∈ W(I), let

τ̄_{D} = max{∑_{i∈D} λ_{i} : λ_{i} ≥ 0, ∥ ∑_{i∈D} λ_{i}a_{i}^{∗}∥ = 1}.

Then τ̄_{D} = τ_{D} for each D ∈ W(I) and hence

τ_{∗} = max{τ̄_{D} : D ∈ W(I)}.

Proof. By [1, Theorem 1.1], for each D ∈ W(I)

τ_{D} = dist(e_{D}, C_{D}) = max{∑_{i∈D} λ_{i}⟨a_{i}^{∗}, e_{D}⟩ : λ_{i} ≥ 0, ∥ ∑_{i∈D} λ_{i}a_{i}^{∗}∥ = 1}.

Since ⟨a_{i}^{∗}, e_{D}⟩ = 1 for each i ∈ D, it follows that

τ_{D} = max{∑_{i∈D} λ_{i} : λ_{i} ≥ 0, ∥ ∑_{i∈D} λ_{i}a_{i}^{∗}∥ = 1} = τ̄_{D}.

By Theorem 2.1, one has that τ_{∗} = max{τ̄_{D} : D ∈ W(I)}.

Theorem 2.3. For each D ∈ W(I), let

γ_{D} := min{∥ ∑_{i∈D} α_{i}a_{i}^{∗}∥ : α_{i} ≥ 0, ∑_{i∈D} α_{i} = 1}.

Then τ̄_{D} = \frac{1}{γ_{D}} for each D ∈ W(I) and hence

τ_{∗} = 1/ min{γ_{D} : D ∈ W(I)}.

Proof. Pick (α′_{i})_{i∈D} ∈ R_{+}^{|D|} with ∑_{i∈D} α′_{i} = 1 such that γ_{D} = ∥ ∑_{i∈D} α′_{i}a_{i}^{∗}∥, where

|D| denotes the number of elements in D. Then ∥ ∑_{i∈D} \frac{α′_{i}}{γ_{D}} a_{i}^{∗}∥ = 1 and hence

τ̄_{D} ≥ ∑_{i∈D} \frac{α′_{i}}{γ_{D}} = \frac{1}{γ_{D}} .  (9)

For each (λ_{i})_{i∈D} ∈ R_{+}^{|D|} with ∥ ∑_{i∈D} λ_{i}a_{i}^{∗}∥ = 1, let η_{k} = _{\frac{λ_{k}}{∑_{i∈D} λ_{i}}} for each k ∈ D. Then

∑_{k∈D} η_{k} = 1. Therefore,

γ_{D} ≤ ∥ ∑_{k∈D} η_{k}a_{k}^{∗}∥ = \frac{1}{∑_{i∈D} λ_{i}} ∥ ∑_{k∈D} λ_{k}a_{k}^{∗}∥ = \frac{1}{∑_{i∈D} λ_{i}} ,

that is, \frac{1}{γ_{D}} ≥ ∑_{i∈D} λ_{i}. It follows from the definition of τ̄_{D} that \frac{1}{γ_{D}} ≥ τ̄_{D}. This and (9)

imply that τ̄_{D} = \frac{1}{γ_{D}}. The proof is completed.

Let τ_{4} := max{dist(e_{D}, C_{D}) : D ∈ M(I)},

τ_{5} := max{∑_{i∈D} λ_{i} : λ_{i} ≥ 0, ∥ ∑_{i∈D} λ_{i}a_{i}^{∗}∥ = 1, D ∈ M(I)}

and

τ_{6} := 1/ min{∥ ∑_{i∈D} α_{i}a_{i}^{∗}∥ : α_{i} ≥ 0, ∑_{i∈D} α_{i} = 1, D ∈ M(I)}.

Since W(I) ⊂ M(J), Theorems 2.1, 2.2 and 2.3 imply the following result.

Corollary 2.1 Each of τ_{4}, τ_{5} and τ_{6} is a Lipschitz error bound of (1).

In general the constants in Corollary 2.1 are not necessarily the sharpest but, on the other hand, they do have an advantage that they only depend on a_{i}^{∗}’s (not on c_{i}’s).

The following theorem is taken from Theorem 10 of [10].

Theorem B. Let g_{i} : R^{n} → R be a continuous convex function for i = 1, ⋯, m and S = {x ∈ R^{n} : g_{i}(x) ≤ 0, i = 1, ⋯, m}. Let

τ_{∗} := inf{τ ≥ 0 : dist(x, S) ≤ τ max{[g_{i}(x)]_{+} : i = 1, ⋯, m} ∀x ∈ R^{n}}.

Suppose that Abadie’s CQ holds for S at each feasible piont x (i.e., N(x, S) =

{ ∑_{i∈I(x)} λ_{i}v^{i} : λ_{i} ≥ 0, v^{i} ∈ ∂g_{i}(x), i ∈ I(x)}, where I(x) = {1 ≤ i ≤ m : g_{i}(x) ≥

g_{j}(x), 1 ≤ j ≤ m}). Then

τ_{∗} = 1/ inf{sup{v^{T} ∑_{j∈I(x)} λ_{j}v^{j} : v ∈ ∂g_{i}(x), i ∈ I(x)} : λ_{j} ≥ 0,
∥ ∑_{j∈I(x)} λ_{j}v^{j}∥ = 1, v^{j} ∈ ∂g_{j}(x), j ∈ I(x), x ∈ ∂S},  (10)

where ∂S denotes the boundary of S.

In the case when each g_{i}(x) = a_{i}^{∗}^{T} x−c_{i} with a_{i}^{∗} ∈ R^{n} and c_{i} ∈ R for i = 1, ⋯, m, where a_{i}^{∗}^{T} denotes the transpose of a_{i}^{∗}, ∂g_{i}(x) = {a_{i}^{∗}} and (10) reads

τ_{∗} = 1/ inf{max{a_{i}^{∗}^{T} ∑_{j∈I(x)} λ_{j}a_{j}^{∗} : i ∈ I(x)} : λ_{j} ≥ 0,
∥ ∑_{j∈I(x)} λ_{j}a_{j}^{∗}∥ = 1, j ∈ I(x), x ∈ ∂S}.  (11)

On the other hand, Theorem 2.2 and Theorem 2.3 imply that

τ_{∗} = sup{∑_{i∈D} λ_{i} : λ_{i} ≥ 0, ∥ ∑_{i∈D} λ_{i}a_{i}^{∗}∥ = 1, D ∈ W(I)}  (12)
= 1/ min{∥ ∑_{i∈D} α_{i}a_{i}^{∗}∥ : α_{i} ≥ 0, ∑_{i∈D} α_{i} = 1, D ∈ W(I)}.  (13)

Though (11), (12) and (13) give the same constant τ_{∗}, (12) and (13) appear to be simpler: first, W(I) is a finite family; secondly, by the defintion of W(I), one has that for each D ∈ W(I) there exists s_{D} ∈ ∂S such that D ⊂ I(s_{D}). Moreover, Theorem 2.2 and 2.3 are valid in the general setting of normed spaces (finite or infinite dimensions) while the formulation of (10) and (11) requires the inner product structure. We conclude this section with a summary giving steps to determine the least error bound τ_{∗}. Step 1. Determine M(I) (e.g., one can determine M(I) by using Gram-Schmidt process when E is of an inner product structure). Step 2. Find all elements in M(I) with the property (W). Let D ∈ M(I). To determine whether or not D ∈ W(I), one only need to complete the following procedures 1) and 2).

1) Solve two linear equation systems:

(I) ⟨a_{i}^{∗}, x⟩ − c_{i} = 0, i ∈ D

and (II) ⟨a_{i}^{∗}, x⟩ = 1, i ∈ D

(both (I) and (II) can be solved as {a_{i}^{∗} : i ∈ D} is linearly independent).

2) Pick an arbitrary pair (s_{D}, e_{D}) such that s_{D} and e_{D} are solutions of (I) and (II) respectively. Calculate α_{j} = ⟨a_{j}^{∗}, s_{D}⟩ − c_{j} and β_{j} = ⟨a_{j}^{∗}, e_{D}⟩ for each j ∈ I \ D. If α_{j} ≤ 0 for each j ∈ I \ D and α_{j} < 0 when j ∈ I \ D with β_{j} > 1 then D ∈ W(I); otherwise D ∉ W(I). [This criterion does not depend on the particular choice of the pair.] Step 3. Calculate τ̄_{D} or γ_{D} for each D ∈ W(I). Step 4. Calculate τ_{∗} by virtue of Theorems 2.2 or 2.3. Remark. Computational works involving in Steps 1 and 2 can be very large (cf. [6, page 207]).

3. Proof of Theorem 2.1

The proof is divided into several steps which will be presented as lemmas. For convenience we first set out notations (that will be used throughout this section). For a subset Y of E, let ext(Y) and ∂(Y) respectively denote the extreme point set and the topological boundary of Y. For each x ∈ E, let

I(x) := {i ∈ I : ⟨a_{i}^{∗}, x⟩ − c_{i} = ϕ(x)},

where ϕ and I are as in the beginning of section 2. For each t ∈ R, let S_{t} := {x ∈ E : ϕ(x) ≤ t} (and hence S = S_{0}). Let

Z_{+} := {(x, r) ∈ E × R : ⟨a_{i}^{∗}, x⟩ − r ≤ c_{i}, i ∈ I}.

Then Z_{+} is a polyhedron in E × R and so the extreme point set ext(Z_{+}) is a finite set. Let

β := inf{r > 0 : there exists x ∈ E × R such that (x, r) ∈ ext(Z_{+})}.

Then β > 0.

Lemma 3.1. Suppose that E^{∗} = span{a_{i}^{∗} : i ∈ I}. Then there exist finitely many subsets I_{1}, ⋯, I_{p} of I and {s_{1}, ⋯, s_{p}, e_{1}, ⋯, e_{p}} ⊂ E such that the following properties are satisfied.

(i) E^{∗} = span{a_{i}^{∗} : i ∈ I_{j}}, ∀j ∈ P. (ii) ⟨a_{i}^{∗}, s_{j}⟩ − c_{i} = 0 and ⟨a_{i}^{∗}, e_{j}⟩ = 1 ∀i ∈ I_{j} and ∀j ∈ P. (iii) I(s_{j} + te_{j}) = I_{j} ∀t ∈ (0, β) and ∀j ∈ P. (iv) ext(S_{t}) = {s_{j} + te_{j} : j ∈ P } ∀t ∈ (0, β).

(P appearing in the above (i)–(iv) denotes the set {1, ⋯, p}.)

Proof. Let t ∈ (0, β) and u ∈ ext(S_{t}). Clearly it suffices to show that

(a) E^{∗} = span{a_{i}^{∗} : i ∈ I(u)} and that there exist s_{u}, e_{u} ∈ E with the following properties.

(b) ⟨a_{i}^{∗}, s_{u}⟩ − c_{i} = 0 and ⟨a_{i}^{∗}, e_{u}⟩ = 1 ∀i ∈ I(u).

(c) ⟨a_{i}^{∗}, s_{u} + t′e_{u}⟩ − c_{i} < t′ ∀t′ ∈ (0, β) and ∀i ∈ I \ I(u).

(d) s_{u} + t′e_{u} ∈ ext(S_{t′}) ∀t′ ∈ (0, β). To show (a), suppose to the contrary that E^{∗} ≠ span{a_{i}^{∗} : i ∈ I(u)}. Then there exists x_{0} ∈ E \ {0} such that ⟨a_{i}^{∗}, x_{0}⟩ = 0 for all i ∈ I(u). Noting that ⟨a_{i}^{∗}, u⟩ − c_{i} < ϕ(u) = t (as u ∈ ext(S_{t}) ⊂ ∂(S_{t})) for each i ∈ I \ I(u), it follows that there exists ε > 0 small enough such that ⟨a_{i}^{∗}, u ± εx_{0}⟩ − c_{i} ≤ t for all i ∈ I, that is, u ± εx_{0} ∈ S_{t}, contradicting u ∈ ext(S_{t}). Therefore, (a) holds. Thus there exists a subset D of I(u) such that {a_{i}^{∗} : i ∈ D} is a basis of E^{∗}. This implies that there exists a unique pair (s_{u}, e_{u}) ∈ E × E such that

⟨a_{i}^{∗}, s_{u}⟩ − c_{i} = 0 and ⟨a_{i}^{∗}, e_{u}⟩ = 1 ∀i ∈ D.  (14)

Hence ⟨a_{i}^{∗}, s_{u} + te_{u}⟩ − c_{i} = t = ϕ(u) = ⟨a_{i}^{∗}, u⟩ − c_{i} ∀i ∈ D.

Since {a_{i}^{∗} : i ∈ D} is a basis of E^{∗}, it follows that u = s_{u} + te_{u}. For each i ∈ I, let π_{i} denote the hyperplane {(x, r) ∈ E × R : ⟨a_{i}^{∗}, x⟩ − r = c_{i}}. Then ⋂_{i∈D} π_{i} is a line

in E × R. It follows from (14) that

(s_{u}, 0) + R(e_{u}, 1) = ⋂_{i∈D} π_{i},  (15)

where R(e_{u}, 1) consists of all t(e_{u}, 1) with t ∈ R. We claim that

(s_{u}, 0) + R(e_{u}, 1) = ⋂_{i∈I(u)} π_{i}.  (16)

Indeed if that (16) is not true, then (15) implies that there exists i′ ∈ I(u) \ D such that (s_{u}, 0) + R(e_{u}, 1) is not a subset of π_{i′}. It follows from u = s_{u} + te_{u} that ((s_{u}, 0) + R(e_{u}, 1)) ∩ π_{i′} = {(u, t)}, that is, ( ⋂_{i∈D} π_{i}) ∩ π_{i′} = {(u, t)}. Noting

that ( ⋂_{i∈D} π_{i}) ∩ π_{i′} ∩ Z_{+} is an extreme subset of Z_{+}, it follows that (u, t) ∈ ext(Z_{+}),

contradicting t ∈ (0, β) and the definition of β. This shows that (16) holds and hence (b) holds. To prove (c), suppose to the contrary that there exists i_{0} ∈ I \ I(u) and t_{0} ∈ (0, β) such that

⟨a_{i_{0}}^{∗}, s_{u} + t_{0}e_{u}⟩ − c_{i_{0}} ≥ t_{0}.  (17)

Note that ⟨a_{i}^{∗}, s_{u}+te_{u}⟩−c_{i} < ϕ(u) = t (i.e., ⟨a_{i}^{∗}, s_{u}+te_{u}⟩−t < c_{i}) for each i ∈ I\I(u). Consequently, it holds that for each i ∈ I \ I(u), r_{i} > 0 where

r_{i} := sup{r > 0 : ⟨a_{i}^{∗}, s_{u} + [(1 − λ)t + λt_{0}]e_{u}⟩ − (1 − λ)t − λt_{0} < c_{i}, ∀λ ∈ [0, r]}.

Note that r_{i_{0}} ≤ 1 thanks to (17). Take j ∈ I \ I(u) such that r_{j} = min{r_{i} : i ∈ I \ I(u)}. Then r_{j} ∈ (0, 1] and

⟨a_{i}^{∗}, s_{u} + [(1 − r_{j})t + r_{j}t_{0}]e_{u}⟩ − (1 − r_{j})t − r_{j}t_{0} ≤ c_{i}, ∀i ∈ I \ I(u);

moreover, the equality holds if i = j. This and (b) imply that

(s_{u} + [(1 − r_{j})t + r_{j}t_{0}]e_{u}, (1 − r_{j})t + r_{j}t_{0}) ∈ ( ⋂_{i∈I(u)} π_{i}) ∩ π_{j} ∩ Z_{+}.

Note that

(s_{u} + [(1 − r_{j})t + r_{j}t_{0}]e_{u}, (1 − r_{j})t + r_{j}t_{0}) ∉ ext(Z_{+})

(by the definition of β and 0 < (1 − r_{j})t + r_{j}t_{0} < β) and that ( ⋂_{i∈I(u)} π_{i}) ∩ π_{j} ∩ Z_{+}

is an extreme subset of Z_{+}. Therefore ( ⋂_{i∈I(u)} π_{i}) ∩ π_{j} must be a line containing the

point (s_{u} + [(1 − r_{j})t + r_{j}t_{0}]e_{u}, (1 − r_{j})t + r_{j}t_{0}). This and (16) imply that

(s_{u}, 0) + R(e_{u}, 1) = ( ⋂_{i∈I(u)} π_{i}) ∩ π_{j}.

Thus (u, t) = (s_{u} + te_{u}, t) ∈ π_{j}, that is, ⟨a_{j}^{∗}, u⟩ − c_{j} = t = ϕ(u), contradicting j ∈ I \ I(u). It remains to show (d). By virtue of (a) and (b), one has that

⋂_{i∈I(u)}{x ∈ E : ⟨a_{i}^{∗}, x⟩ − c_{i} = t′} = {s_{u} + t′e_{u}}, ∀t′ ∈ (0, β);

it follows from (c) that s_{u} + t′e_{u} ∈ S_{t′} and consequently that s_{u} + t′e_{u} ∈ ext(S_{t′}) for each t′ ∈ (0, β). This shows that (d) holds. The proof is completed.

Lemma 3.2. Suppose that E^{∗} = span{a_{i}^{∗} : i ∈ I}. Let subsets I_{1}, ⋯, I_{p} of I and {s_{1}, ⋯, s_{p}, e_{1}, ⋯, e_{p}} ⊂ E be such that (i)–(iv) of Lemma 3.1 hold. Let P := {1, ⋯, p} and for each j ∈ P,

C_{j} := {x ∈ E : ⟨a_{i}^{∗}, x⟩ ≤ 0, ∀i ∈ I_{j}}.

Then τ_{∗} = max{dist(e_{j}, C_{j}) : j ∈ P }.

Proof. For each t ∈ R and j ∈ P, define S_{t}(j) by

S_{t}(j) := {x ∈ E : ⟨a_{i}^{∗}, x⟩ − c_{i} ≤ t, ∀i ∈ I_{j}}.

By (i) and (ii) of Lemma 3.1 it is easy to verify that S_{t}(j) = s_{j} + te_{j} + C_{j} and S ⊂ S_{0}(j) = s_{j} + C_{j} for each t ∈ R and each j ∈ P. Take δ ∈ (0, β). Then

dist(s_{j} + δe_{j}, s_{j} + C_{j}) ≤ dist(s_{j} + δe_{j}, S) ≤ τ_{∗}ϕ(s_{j} + δe_{j}) = τ_{∗}δ, ∀j ∈ P (18)

where the last equality is due to (ii) and (iii) of Lemma 3.1. Making use of the fact that C_{j} = δC_{j}, (18) implies that

δdist(e_{j}, C_{j}) = dist(s_{j} + δe_{j}, s_{j} + C_{j}) ≤ τ_{∗}δ.

Therefore,

τ∗ ≥ max{dist(e_{j}, C_{j}) : j ∈ P }.  (19)

Let z ∈ E with ϕ(z) > 0. Take a sequence {ε_{k}} in (0, min{ϕ(z), β}) convergent to 0. By (iii) of Lemma 3.1 there exists r_{k} > 0 such that for each j ∈ P, the inequality

⟨a_{i}^{∗}, ·⟩ − c_{i} < ϕ(·), ∀i ∈ I \ I_{j}  (20)

holds on the ball B(s_{j} +ε_{k}e_{j}, r_{k}) with center s_{j} +ε_{k}e_{j} and radius r_{k}. Pick a sequence {t_{k}} convergent to 0 with each t_{k} ∈ (ε_{k}, min{ϕ(z), β}) such that

(t_{k} − ε_{k})∥e_{j}∥ < \frac{r_{k}}{2} , ∀j ∈ P.

We claim that

dist(s_{j} + t_{k}e_{j}, S_{ε_{k}}) = dist(s_{j} + t_{k}e_{j}, S_{ε_{k}}(j)), ∀j ∈ P.  (21)

In fact, pick s_{kj} ∈ S_{ε_{k}}(j) such that

dist(s_{j} + t_{k}e_{j}, S_{ε_{k}}(j)) = ∥s_{j} + t_{k}e_{j} − s_{kj}∥.

To verify (21), we need show that s_{kj} ∈ S_{ε_{k}} (noting S_{ε_{k}} ⊂ S_{ε_{k}}(j)), and equivalently that ⟨a_{i}^{∗}, s_{kj}⟩−c_{i} ≤ ε_{k} for each i ∈ I \I_{j}, which clearly follows from (20) provided we can show that s_{kj} belongs to B(s_{j} + ε_{k}e_{j}, r_{k}). This later condition is indeed satisfied as

∥s_{j} + t_{k}e_{j} − s_{kj}∥ ≤ dist(s_{j} + t_{k}e_{j}, S_{ε_{k}}) ≤ ∥s_{j} + t_{k}e_{j} − (s_{j} + ε_{k}e_{j})∥

(the last inequality holds as s_{j} + ε_{k}e_{j} ∈ S_{ε_{k}}), and so

∥s_{j} + ε_{k}e_{j} − s_{kj}∥ ≤ ∥s_{j} + ε_{k}e_{j} − (s_{j} + t_{k}e_{j})∥ + ∥s_{j} + t_{k}e_{j} − s_{kj}∥
≤ 2∥s_{j} + t_{k}e_{j} − (s_{j} + ε_{k}e_{j})∥ = 2(t_{k} − ε_{k})∥e_{j}∥ < r_{k}.

Therefore (21) holds. Take x_{k} ∈ ∂(S_{ε_{k}}) be such that dist(z, S_{ε_{k}}) = ∥z − x_{k}∥; then ϕ(x_{k}) = ε_{k}. Define z_{k} by

z_{k} = \frac{t_{k} − ε_{k}}{ϕ(z) − ε_{k}} z + (1 − \frac{t_{k} − ε_{k}}{ϕ(z) − ε_{k}})x_{k}.

Then

ϕ(z_{k}) ≤ \frac{t_{k} − ε_{k}}{ϕ(z) − ε_{k}} ϕ(z) + (1 − \frac{t_{k} − ε_{k}}{ϕ(z) − ε_{k}})ϕ(x_{k}) = t_{k},

showing that z_{k} ∈ S_{t_{k}}; moreover

dist(z_{k}, S_{ε_{k}}) = ∥z_{k} − x_{k}∥ = \frac{t_{k} − ε_{k}}{ϕ(z) − ε_{k}} dist(z, S_{ε_{k}}).  (22)

We claim that

dist(z_{k}, S_{ε_{k}}) ≤ max{dist(s_{j} + t_{k}e_{j}, S_{ε_{k}}) : j ∈ P }.  (23)

Note that S_{t_{k}} is a polyhedron in E containing no lines; hence by [11, Theorem 18.5] one has that S_{t_{k}} = co(ext(S_{t_{k}})) + Rec(S_{t_{k}}), where Rec(S_{t_{k}}) denotes the recession cone of S_{t_{k}}. It is easy to verify that

Rec(S_{t_{k}}) ⊂ ⋂_{i∈I}{x ∈ E : ⟨a_{i}^{∗}, x⟩ ≤ 0},

and hence that

S_{ε_{k}} + Rec(S_{t_{k}}) ⊂ S_{ε_{k}}.  (24)

Pick x′ ∈ co(ext(S_{t_{k}})) and y′ ∈ rec(S_{t_{k}}) such that z_{k} = x′ + y′. By the convexity of S_{ε_{k}},

dist(x′, S_{ε_{k}}) ≤ max{dist(e, S_{ε_{k}}) : e ∈ ext(S_{t_{k}})}.

Noting that dist(z_{k}, S_{ε_{k}}) = dist(x′, S_{ε_{k}} − y′), (24) and y′ ∈ Rec(S_{t_{k}}) imply that dist(z_{k}, S_{ε_{k}}) ≤ dist(x′, S_{ε_{k}}). Therefore,

dist(z_{k}, S_{ε_{k}}) ≤ max{dist(e, S_{ε_{k}}) : e ∈ ext(S_{t_{k}})}

and (23) is seen to hold by virtue of (iv) of Lemma 3.1. Recalling that S_{ε_{k}}(j) = s_{j} + ε_{k}e_{j} + C_{j} and making use of (21), one has that

dist(s_{j} + t_{k}e_{j}, S_{ε_{k}}) = dist(s_{j} + t_{k}e_{j}, S_{ε_{k}}(j))
= dist(s_{j} + t_{k}e_{j}, s_{j} + ε_{k}e_{j} + C_{j})
= dist((t_{k} − ε_{k})e_{j}, C_{j})
= (t_{k} − ε_{k})dist(e_{j}, C_{j})

(the last equality holds as C_{j} is a cone and t_{k} − ε_{k} > 0). It follows from (22) and (23) that

dist(z, S_{ε_{k}}) ≤ (ϕ(z) − ε_{k}) max{dist(e_{j}, C_{j}) : j ∈ P }.  (25)

By Hoffman’s error bound result, there exists a constant τ ∈ (0, +∞) such that

dist(x_{k}, S) ≤ τϕ(x_{k}) = τε_{k}, ∀k.

Noting that

dist(z, S) ≤ ∥z − x_{k}∥ + dist(x_{k}, S)
= dist(z, S_{ε_{k}}) + dist(x_{k}, S),

it follows from S ⊂ S_{ε_{k}} that dist(z, S) = lim_{k→∞} dist(z, S_{ε_{k}}). Thus passing to the limits in (25) gives

dist(z, S) ≤ max{dist(e_{j}, C_{j}) : j ∈ P }ϕ(z).

This shows that τ_{∗} ≤ max{dist(e_{j}, C_{j}) : j ∈ P }. Combining this with (19), the proof is completed.

Lemma 3.3. Suppose that E^{∗} = span{a_{i}^{∗} : i ∈ I}. Then Theorem 2.1 holds. Proof. Let P, I_{j}, s_{j} and e_{j} (j ∈ P) be as in Lemma 3.1. For each j ∈ P, by

[1, Corollary 1.1] there exists a subset D′ of I_{j} such that {a_{i}^{∗} : i ∈ D′} is linearly independent and

dist(e_{j}, C_{j}) = dist(e_{j}, C_{D′}),  (26)

where C_{D′} := {x ∈ E : ⟨a_{i}^{∗}, x⟩ ≤ 0, ∀i ∈ D′}. Pick D ⊂ I_{j} such that D′ ⊂ D and {a_{i}^{∗} : i ∈ D} is a basis of E^{∗}. Since C_{j} ⊂ C_{D} ⊂ C_{D′},

dist(e_{j}, C_{j}) ≥ dist(e_{j}, C_{D}) ≥ dist(e_{j}, C_{D′}).

It follows from (26) that dist(e_{j}, C_{j}) = dist(e_{j}, C_{D}). By (ii) and (iii) of Lemma 3.1, it is easy to verify that D ∈ W(I) and dist(e_{j}, C_{D}) = dist(e_{D}, C_{D}) because e_{j} is clearly a solution of the following linear equation system

⟨a_{i}^{∗}, x⟩ = 1, ∀i ∈ D.

Therefore Lemma 3.2 implies that τ_{∗} ≤ max{dist(e_{D}, C_{D}) : D ∈ W(I)}. To prove the converse inequality, let D ∈ W(I) and t_{D} := min \{\frac{⟨a_{i}^{∗},s_{D}⟩−c_{i}}{1−⟨a_{i}^{∗},e_{D}⟩} : i ∈ I_{D}\}, where I_{D} := {i ∈ I \ D : ⟨a_{i}^{∗}, e_{D}⟩ > 1} and the minimum is understood as +∞ if I_{D} = ∅. From Definition 2.1 it is easy to verify that t_{D} > 0 and ϕ(s_{D} + te_{D}) = t for each t ∈ [0, t_{D}). Given t_{0} ∈ (0, t_{D}), it follows from the definition of τ_{∗} that

dist(s_{D} + t_{0}e_{D}, S) ≤ τ_{∗}t_{0}.  (27)

Let S_{D} := {x ∈ E : ⟨a_{i}, x⟩ − c_{i} ≤ 0, ∀i ∈ D}. Then S ⊂ S_{D} and hence

dist(s_{D} + t_{0}e_{D}, S_{D}) ≤ dist(s_{D} + t_{0}e_{D}, S).

Note that S_{D} = s_{D} + C_{D}. Hence

dist(s_{D} + t_{0}e_{D}, s_{D} + C_{D}) ≤ dist(s_{D} + t_{0}e_{D}, S),

that is, t_{0}dist(e_{D}, C_{D}) ≤ dist(s_{D} +t_{0}e_{D}, S). It follows from (27) that dist(e_{D}, C_{D}) ≤ τ_{∗}. This completes the proof.

The Proof of Theorem 2.1. Let E_{0} = ⋂_{i∈I}{x ∈ E : ⟨a_{i}^{∗}, x⟩ = 0}. Then E/E_{0}

is finite dimensional. For each x ∈ E, let [x] denote the equivalence class containing x in E/E_{0}, that is, [x] = x + E_{0}. Define â_{i}^{∗} ∈ (E/E_{0})^{∗} such that ⟨â_{i}^{∗}, [x]⟩ = ⟨a_{i}^{∗}, x⟩ for each x ∈ E and i ∈ I. It is clear that

(E/E_{0})^{∗} = span{â_{i}^{∗} : i ∈ I}.

Let ϕ̂([x]) = max{⟨â_{i}^{∗}, [x]⟩ − c_{i} : i ∈ I} for each [x] ∈ E/E_{0} and Ŝ = {[x] ∈ E/E_{0} : ϕ̂([x]) ≤ 0}. It is easy to verify that a subset D of I has the property (W) with respect to {a_{i}^{∗} : i ∈ I} if and only if it has the property (W) with respect to {â_{i}^{∗} : i ∈ I}. We equip E/E_{0} with the norm ∥| · ∥|: ∥|[x]∥| = inf{∥y∥ : y ∈ [x]} ∀x ∈ E. Noting that Ŝ = {[x] : x ∈ S} and E_{0}+S = S, one has that dist(x, S) = dist([x], Ŝ) for each x ∈ E. These and Lemma 3.3 imply that Theorem 2.1 holds.

References

1. C. Bergthaller and I. Singer, The distance to a polyhedron, Linear Algebra and its Applications 169 (1992) 111-129.

2. J. V. Burke and M. C. Ferris, Weak sharp minima in mathematical programming, SIAM J. Control and Optim., 31 (1993) 1340-1359.

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

4. 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) 688-696.

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

6. D. Klatte and G. Thiere, Error bounds for solutions of linear equations and inequalities, Mathematical Methods of Operations Research, 41 (1995) 191-214.

7. A. S. Lewis and J. S. Pang, Error bounds for convex inequality systems, in J.P. Couzeix, ed., Proceedings of the fifth Symposium on Generalized Convexity, Luminy-Marseille 1996.

8. W. Li, The sharp lipschitz constants for feasible and optimal solutions of a perturbed linear program, Linear Algebra and its Applications 187 (1993) 15-40.

9. O. L. Mangasarian and T. H. Shiau, A variable-complexity norm maximization problem, SIAM J. Alg. Discrete Methods 7 (1986) 455-461.

10. J. S. Pang, Error bounds in mathtematical programming, Mathematical Programming 79 (1997) 299-332.

11. R. T. Rockafellar, Convex Analysis, Princeton University Press, Princeton, NJ, 1970.

12. D.W. Walkup and R.J.B. Wets, A Lipschitzian characterization of convex polyhedra, Proceedings of the American Mathematical Society 20 (1969) 167-173.