ON FIRST AND SECOND-ORDER CONDITIONS FOR ERROR BOUNDS^{∗}

L. R. HUANG^{†} AND K. F. NG^{‡}

Abstract. We establish first-order and second-order sufficient conditions ensuring for a proper lower semicontinuous function f on a Banach space X to have an error bound. We also consider similar problems with constraint, namely f is replaced by its restriction to a subset of X. These results are employed to identity exactly when a quadratic function on X has an error bound.

1. Introduction. Let X be a Banach space and f : X → R ∪ {+∞} a proper lower semicontinuous function. Let λ ∈ R with λ ⩾ inf f (:= inf_{x∈X} f(x)). Let L_{f}(x) := {x ∈ X; f(x) ⩽ λ}. Assuming L_{f}(λ) ≠ ∅, we say that f has a (Lipschitz) error bound δ > 0 for L_{f}(λ) if the distance of x to L_{f}(λ) satisfies the inequality:

(1.1)  δd(x, L_{f}(λ)) ⩽ f(x) − λ, ∀x ∉ L_{f}(λ).

Many authors have studied this problem (see [4], [8], [10], [11], [16], [13], [14] and the references therein). In this paper, we study the error bound problem by using the Hadamard directional derivative d_{−}f(x; u) and the second-order directional derivatives. Let 𝔇 denote the set of all x satisfying d_{−}f(x; 0) = 0. We show in Theorem 2.5 that δ > 0 is an error bound for L_{f}(λ) if

(1.2)  sup_{x∈𝔇\L_{f} (λ)} inf_{∥u∥=1} d_{−}f(x; u) ⩽ −δ.

The consideration of the Hadamard derivative instead of the Dini derivative provides not only a better sufficient condition than the one provided in [13] but also a better tool in dealing with the constraint problems (see Theorem 2.6 and Theorem 2.7). If the above first-order sufficient condition (1.2) fails to apply then one may look at second-order conditions. In Section 3, we establish a second-order Taylor expansion (in an inequality form) for lower semicontinuous functions, and this expansion is then applied to provide a second-order sufficient condition for error bounds. This result appears to be new even for C^{2}-functions (see Corollary 3.3). In Section 4, we study quadratic functions f on X and identify exactly when f has a Lipschitz error bound, and our classification is more concise than the corresponding results in [13] given for X = R^{n}.

2. First-order sufficient conditions for the existence of an error bound. Let Z be a complete metric space and S a closed subset of Z. Let f : Z → R ∪ {+∞} be a lower semicontinuous function. Let δ > 0. Define M_{f}(x, δ) by

M_{f}(x, δ) := {y ∈ Z; f(x) ⩾ f(y) + δd(x, y)}.

∗The research was supported by the United College of the Chinese University of Hong Kong, a direct grant (CUHK), and an Earmarked grant from the Research Grant Council of Hong Kong.

†Department of Mathematics, South China Normal University, Guang Zhou, The People′s Republic of China (Email: huanglr@scnu.edu.cn)

‡Department of Mathematics, The Chinese University of Hong Kong, Shatin, N.T., Hong Kong (Email: kfng@math.cuhk.edu.hk)

Let

O_{f}(δ) := {x ∈ Domf; M_{f}(x, δ) = {x}}

When δ = 1, we denote M_{f}(x, 1) by M_{f}(x) and O_{f}(1) by O_{f} for short. The following result is similar to [8] and [13] but we do not assume that S is a level set of f.

Proposition 2.1. Let Z be a complete metric space and S a nonempty closed subset of X. Let f : Z → R ∪ {+∞} be a lower semicontinuous function bounded from below. Suppose that O_{f}(δ) ⊆ S. Then for any x ∈ Domf\S, there exists z ∈ S such that

δd(x, z) ⩽ f(x) − f(z).

Proof. We suppose without loss of generality that δ = 1. Let x ∈ Z\S, and assume that f(x) < +∞. It is sufficient to show that

M_{f}(x) ∩ S ≠ ∅.

Note that M_{f}(x) is closed as f is lower semicontinuous. By Ekeland’s Variational Principle, there exists z ∈ M_{f}(x) such that

(2.1)  f(y) + d(y, z) > f(z), ∀y ∈ M_{f}(x)\{z}.

We will show that z ∈ S (and hence complete the proof). By way of contradiction we assume that z ∉ S. Then, by assumption, z ∉ O_{f} and hence there exists w ∈ M_{f}(z)\{z},

(2.2)  f(z) − f(w) ⩾ d(z, w).

Since w ∈ M_{f}(z) and z ∈ M_{f}(x), we have w ∈ M_{f}(x) and so the inequality (2.1) holds for y = w. But this is impossible since the inequality (2.2) contradicts to (2.1) for y = w . □

In terms of level set L_{f}(λ) of f, we have the following result [13, Lemma 2.3].

Corollary 2.2. Let Z be a complete metric space and f : Z → R ∪ {+∞} a proper lower semicontinuous function. Let δ > 0, λ ∈ R be such that L_{f}(λ) ≠ ∅ and such that for any x ∈ Domf\L_{f}(λ), there exists y ∈ f^{−1}[λ, +∞) with

(2.3)  f(x) − f(y) ⩾ δd(x, y) > 0.

Then one has

f(x) − λ ⩾ δd(x, L_{f}(λ)), ∀x ∈ Z\L_{f}(λ).

Proof. Since f is lower semicontinuous, L_{f}(λ) is closed. Let g be defined by g(x) = max{λ, f(x)}. Then g : Z → [λ, +∞] is lower semicontinuous and L_{g}(λ) = L_{f}(λ). By the assumption (2.3) one has O_{g}(δ) ⊆ L_{g}(λ). It follows from Proposition 2.1 that for any x ∈ Z\L_{g}(λ) there exists y ∈ L_{g}(λ) such that

g(x) − g(y) = g(x) − λ ⩾ δd(x, L_{g}(λ)).

Hence, we have

f(x) − λ ⩾ δd(x, L_{f}(λ)).

□

Throughout X denotes a Banach space and f : X → R ∪ {+∞} is a lower semicontinuous function. Suppose that f is finite at a point x ∈ X. Let u ∈ X. We use d_{−}f(x; u) and D_{−}f(x; u) to denote respectively Hadamard’s and Dini’s lower directional derivatives of f at x in the direction u. They are defined by

d_{−}f(x; u) := lim inf_{u′→u,t↓0} \frac{1}{t}(f(x + tu′) − f(x))

and

D_{−}f(x; u) := lim inf_{t↓0} \frac{1}{t}(f(x + tu) − f(x)).

Thus, d_{−}f ⩽ D_{−}f. Let 𝔇 or 𝔇_{f} denote the set of all x such that d_{−}f(x; 0) > −∞. By the homogeneity of d_{−}f(x; ·) we have

(2.4)  𝔇 = {x ∈ Domf; d_{−}f(x; 0) = 0}.

Lemma 2.3. Let x ∈ X and f(x) be finite. If d_{−}f(x; 0) = −∞, then for any δ > 0, there exists y ∈ X such that

f(x) − f(y) ⩾ δd(x, y) > 0.

Proof. Suppose that d_{−}f(x; 0) = −∞. Then for any δ > 0, it follows from the definition of d_{−}f(x; ·) that there exist a sequence (t_{n}) ↓ 0 and a sequence (u_{n}) → 0 such that

f(x) − f(x + t_{n}u_{n}) > t_{n}δ = \frac{δ}{∥u_{n}∥}d(x, x + t_{n}u_{n}).

Thus, noting \frac{1}{∥u_{n}∥} > 1 for some large n and letting y = x + t_{n}u_{n}, we complete the

proof. □

In terms of Hadamard’s directional derivative, we have the following sufficient condition for f to admit an error bound.

Theorem 2.4. Let S be a closed subset of X. Let θ := inf_{z∈X\S} f(z) and δ > 0. Suppose that θ > −∞ and

(2.5)  sup_{x∈𝔇\S} inf_{∥u∥=1} d_{−}f(x; u) ⩽ −δ.

Then

δd(x, S) ⩽ f(x) − θ, ∀x ∈ X\S.

Proof. Define a function g : X → R ∪ {+∞} by

g(x) := \{ \begin{matrix}f(x), & x ∈ X\S, \\ θ, & x ∈ S. \end{matrix}

Then g ⩾ θ is a lower semicontinuous function with d_{−}f(x; u) = d_{−}g(x; u) for any x ∈ X\S and u ∈ X. Thus, one has 𝔇\S = 𝔇_{g}\S, where 𝔇_{g} := {x ∈ X; d_{−}g(x; 0) > −∞}. Therefore, (2.5) can be rewritten as

(2.6)  sup_{x∈𝔇_{g}\S} inf_{∥u∥=1} d_{−}g(x; u) ⩽ −δ.

Let δ′ ∈ (0, δ) and x ∈ Domg\S. We claim that there exists y ∈ X such that

(2.7)  g(x) − g(y) ⩾ δ′d(x, y) ≠ 0.

If x ∉ 𝔇_{g}, then the claim is certainly true by Lemma 2.3. Thus we may suppose that x ∈ 𝔇_{g}. By (2.6) there exists a unit vector u such that d_{−}g(x; u) < −δ′. Hence, there exist sequences (t_{n}) ↓ 0 and (u_{n}) → u such that

lim_{n→+∞} \frac{1}{t_{n}} (g(x + t_{n}u_{n}) − g(x)) < −δ′,

that is,

lim_{n→+∞} \frac{1}{t_{n} ∥u_{n}∥}(g(x + t_{n}u_{n}) − g(x)) < −δ′.

Taking y = x + t_{n}u_{n} with a sufficiently large n, we have y ≠ x and

g(y) − g(x) < −δ′d(x, y).

Therefore the claim made in (2.7) holds. Consequently, Domg\S ⊂ X\O_{δ′}(g) which ensures (since O_{δ′}(g) ⊂ Domg) that O_{δ′}(g) ⊂ S. Then, we deduce from Proposition 2.1 that

g(x) − θ ⩾ δ′d(x, S), ∀x ∈ X\S.

Since δ′ lying in (0, δ) is arbitrary, we have

g(x) − θ ⩾ δd(x, S), ∀x ∈ X\S.

□

By considering level sets L_{f}(λ) in place of S, we have the following theorem.

Theorem 2.5. Let δ > 0 and let λ ∈ R be such that L_{f}(λ) ≠ ∅. Suppose that

(2.8)  sup_{x∈𝔇\L_{f} (λ)} inf_{∥u∥=1} d_{−}f(x; u) ⩽ −δ.

Then

δd(x, L_{f}(λ)) ⩽ f(x) − λ, ∀x ∈ X\L_{f}(λ).

Proof. Let θ := inf_{x∈X\L_{f} (λ)} f(x). Then θ ⩾ λ. Thus, the result follows from Theorem 2.4. □

Remark 1. In place of (2.8), the sufficient condition established by Ng and Zheng in [13] is that

(2.9)  sup_{x∈X\L_{f} (λ)} inf_{∥u∥=1} D_{−}f(x; u) ⩽ −δ.

Since d_{−}f ⩽ D_{−}f and 𝔇\L_{f}(λ) ⊆ X\L_{f}(λ), it is clear that Theorem 2.5 improves the earlier result. In particular, the consideration of d_{−}f is of importance to us as it provides information above f along “curvilinear tangents” (rather than only linear ones) when we consider constrained problems. This in turn will provide a key argument for our error bound result of quadratic functions studied in Section 4. In the Appendix of this paper, we give an example which is covered by Theorem 2.5 but not by [13, Theorem 2.5].

We now turn to a result for a constrained problem; this result will provide a key step for us to establish a second sufficient condition in theorem 2.7. Let C be a closed subset of X and let x ∈ C. Recall that the contingent cone of C at x is defined by

T_{C}(x) := \{u ∈ X; lim inf_{t↓0} \frac{1}{t}(d_{C}(x + tu)) = 0\}.

Thus, u ∈ T_{C}(x) if and only if there exist sequences (t_{n}) ↓ 0 and (u_{n}) → u such that x + t_{n}u_{n} ∈ C for each n.

Theorem 2.6. Let S and C be closed subsets of X with ∅ ≠ S ⊆ C. Let f : C → R ∪ {+∞} be a proper lower semicontinuous function such that λ := inf_{x∈C\S} f(x) > −∞ and let δ > 0. Suppose that for any x ∈ 𝔇_{f}\S there exists a unit vector u ∈ T_{C}(x) such that d_{−}f(x; u) ⩽ −δ. Then one has δd(x, S) ⩽ (f(x) − λ) for each x ∈ C\S.

Proof. f can be regarded as be defined on X by putting f(x) = +∞ for all x ∈ X\C. Let g be defined by

g(x) := \{ \begin{matrix}f(x), & x ∈ X\S \\ λ, & x ∈ S \end{matrix} .

Thus, g is a lower semicontinuous function on X bounded from below. Since f(x) = g(x) = +∞ for x ∈ X\C,

(2.10)  𝔇_{g}\S = 𝔇_{f}\S.

Let x ∈ 𝔇_{g}\S. By (2.10) and assumption, take a unit vector u ∈ T_{C}(x) such that d_{−}f(x; u) ⩽ −δ. Take sequences (t_{n}) ↓ 0, (u_{n}) → u such that

d_{−}f(x; u) = lim_{n→+∞} \frac{1}{t_{n}} (f(x + t_{n}u_{n}) − f(x)) ⩽ −δ.

By considering subsequences if necessary we can further assume that

x + t_{n}u_{n} ∈ C, ∀n.

Indeed if x + t_{n}u_{n} ∉ C for infinitely many n then f(x + t_{n}u_{n}) = +∞ for such n; this contradicts

lim_{n→∞} \frac{f(x + t_{n}u_{n}) − f(x)}{t_{n}} < +∞.

Noting that x + t_{n}u_{n} ∉ S so f(x + t_{n}u_{n}) = g(x + t_{n}u_{n}) for all large enough n, it follows that

d_{−}g(x; u) ⩽ lim inf_{n→+∞} \frac{1}{t_{n}} (g(x + t_{n}u_{n}) − g(x))
= lim inf_{n→+∞} \frac{1}{t_{n}} (f(x + t_{n}u_{n}) − f(x))
= d_{−}f(x; u) ⩽ −δ.

Thus, one has

sup_{x∈𝔇_{g}\S} inf_{∥u∥=1} d_{−}g(x; u) ⩽ −δ

It follows from Theorem 2.4 that

δd(x, S) ⩽ g(x) − λ = f(x) − λ, ∀x ∈ C\S.

□

Let ε > 0 and
(2.11)  𝔇(ε) := {x ∈ 𝔇\L_{f}(λ); inf_{∥u∥=1} d_{−}f(x; u) ⩾ −ε}.

In terms of 𝔇(ε), the sufficient condition in Theorem 2.5 (ensuring that f has an error bound for L_{f}(λ)) is clearly equivalent to: for some ε > 0,

(2.12)  𝔇(ε) = ∅.

The following result improves Theorem 2.5 by relaxing the condition (2.12).

Theorem 2.7. Let f : X → R ∪ {+∞} be a lower semicontinuous function, and let λ ∈ R be such that X ≠ L_{f}(λ) ≠ ∅. Suppose that there exist ε > 0, υ > λ and an open set Q with

(2.13)  𝔇(ε) ⊆ Q ⊆ X\L_{f}(υ)

and

(2.14)  d_{0} := sup_{x∈Q} d(x, L_{f}(λ)) < +∞.

Then f admits an error bound for L_{f}(λ).

Proof. We may assume that Q is nonempty (see Remark 2 below). Then, if x ∈ Q, d_{0} ⩾ d(x, L_{f}(λ)) > 0. Let Q(s) := {x ∈ X\L_{f}(υ); d(x, L_{f}(λ)) < d_{0} + s}, ∀s > 0 and denote Q by Q(0). Then for any s ⩾ 0, Q(s) is an open subset of X with Q(s) ⊆ X\L_{f}(v) and

sup_{x∈Q(s)} d(x, L_{f}(λ)) ⩽ d_{0} + s < +∞.

Note that

(2.15)  f(x) − λ ⩾ \frac{υ − λ}{d_{0} + s}d(x, L_{f}(λ)), ∀x ∈ Q(s)

because f(x) > υ. Let δ = min\{\frac{ε}{2}, \frac{υ−λ}{2d_{0}}\}. We will show that

(2.16)  f(x) − λ ⩾ δd(x, L_{f}(λ)), ∀x ∈ X\L_{f}(λ).

Since

(2.17)  X\L_{f}(λ) = [L_{f}(υ)\L_{f}(λ)] ∪ [\overline{Q}\L_{f}(λ)] ∪ [X\(\overline{Q} ∪ L_{f}(υ))],

we need only verify (2.16) for x belonging to each of the three sets on the right-hand side of (2.17). Accordingly we divide our proof in three steps.

(I) We first show that

(2.18)  f(x) − λ ⩾ δd(x, L_{f}(λ)), ∀x ∈ L_{f}(υ)\L_{f}(λ).

To do this, let f̄ denote the “restriction” of f to L_{f}(υ); more precisely let f̄ be defined by f̄(x) = f(x) if x ∈ L_{f}(υ) and f̄(x) = +∞ otherwise. Since

f(q) ⩾ f(w), ∀q ∈ X\L_{f}(υ) and w ∈ L_{f}(υ),

d_{−}f(x; u) = d_{−}f̄(x; u) for each x ∈ L_{f}(υ) and u ∈ T_{L_{f} (υ)}(x). Therefore 𝔇f̄ = 𝔇 ∩ L_{f}(υ). Let z ∈ 𝔇∩L_{f}(υ)\L_{f}(λ). By (2.13), z ∉ 𝔇(ε) and so inf_{∥u∥=1} d_{−}f(z; u) < −ε. Then there exist a unit vector u and sequences (t_{n}) ↓ 0, (u_{n}) → u such that

lim_{n→+∞} \frac{f(z + t_{n}u_{n}) − f(z)}{t_{n}} = d_{−}f(z; u) < −ε ⩽ −δ.

Since f(z) ⩽ υ, it follows that for all large n, z + t_{n}u_{n} ∈ L_{f}(υ) and so u ∈ T_{L_{f} (υ)}(z). By Theorem 2.6 (applied to \overline{f}, L_{f}(υ), L_{f}(λ) in place of f, C, S), we have (2.18).

(II) We show next that

(2.19)  f(x) − λ ⩾ δd(x, L_{f}(λ)), ∀x ∈ \overline{Q}\L_{f}(λ).

In fact, let x ∈ \overline{Q}\L_{f}(λ); we may assume that x ∉ L_{f}(υ) (because of (2.18)). Take a sequence (x_{n}) ⊆ Q such that x_{n} → x. Then d(x_{n}, L_{f}(λ)) → d(x, L_{f}(λ)) and so d(x, L_{f}(λ)) ⩽ d_{0}. This implies that

f(x) − λ ⩾ \frac{υ − λ}{d_{0}}d(x, L_{f}(λ)) ⩾ δd(x, L_{f}(λ)),

verifying (2.19).

(III) Let S denote the set \overline{Q} ∪ L_{f}(υ), and define θ := inf_{X\S} f(x). Clearly, θ ⩾ υ. By (2.13), one has that 𝔇(ε) ∩ (𝔇\S) = ∅, that is,

inf_{∥u∥=1} d_{−}f(x; u) < −ε ⩽ −2δ, ∀x ∈ 𝔇\S.

By Theorem 2.4 one has

(2.20)  f(x) − υ ⩾ f(x) − θ ⩾ 2δd(x, S), ∀x ∈ X\S.

By definition of S, X\S can be expressed as S_{1} ∪ S_{2}, where S_{1}, S_{2} are defined by

S_{1} := \{x ∈ X\S; d(x, S) = d(x, \overline{Q})\}

S_{2} := {x ∈ X\S; d(x, S) = d(x, L_{f}(υ))}.

Let x ∈ S_{1}. If x ∈ Q(d_{0}), then by (2.15) one has

(2.21)  f(x) − λ ⩾ \frac{υ − λ}{2d_{0}}d(x, L_{f}(λ)) ⩾ δd(x, L_{f}(λ)).

If x ∉ Q(d_{0}), then one has d(x, L_{f}(λ)) ⩾ 2d_{0} and

(2.22)  d(x, S) = d(x, \overline{Q}) ⩾ d(x, L_{f}(λ)) − d_{0} ⩾ \frac{1}{2}d(x, L_{f}(λ)),

where the first (nonstrict) inequality holds as

d(x, q) + d_{0} ⩾ d(x, q) + d(q, L_{f}(λ)) ⩾ d(x, L_{f}(λ)), ∀q ∈ Q.

Combining (2.20) and (2.22), one has

f(x) − λ ⩾ f(x) − υ ⩾ 2δd(x, S) ⩾ δd(x, L_{f}(λ)).

Combining this with (2.21), we arrive at

(2.23)  f(x) − λ ⩾ δd(x, L_{f}(λ)), ∀x ∈ S_{1}.

Finally, we consider the case when x ∈ S_{2}. Take y_{n} ∈ L_{f}(υ) such that d(x, y_{n}) < d(x, L_{f}(υ)) + \frac{1}{n}; thus,

(2.24)  d(x, L_{f}(λ)) ⩽ d(x, L_{f}(υ)) + d(y_{n}, L_{f}(λ)) + \frac{1}{n}.

We suppose without loss of generality that each y_{n} ∉ L_{f}(λ). Indeed if y_{n} ∈ L_{f}(λ) for infinitely many n then passing to the limits in

d(x, L_{f}(λ)) ≤ d(x, y_{n}) < d(x, L_{f}(υ)) + \frac{1}{n} ≤ d(x, L_{f}(λ)) + \frac{1}{n}

gives that d(x, L_{f}(λ)) = d(x, L_{f}(υ)) and it follows from (2.20) and the fact x ∈ S_{2} that

f(x) − λ > f(x) − υ ⩾ δd(x, S) = δd(x, L_{f}(υ)) = δd(x, L_{f}(λ)).

It remains fo consider the case when each y_{n} ∈ L_{f}(υ)\L_{f}(λ). Noting that d(x, S) = d(x, L_{f}(υ)) as x ∈ S_{2}, it follows from (2.18) and (2.20) that

\begin{aligned}f(x) − λ & ⩾ & f(x) − υ + f(y_{n}) − λ \\ & ⩾ & δ[d(x, L_{f}(υ)) + d(y_{n}, L_{f}(λ))]. \end{aligned}

Combining this with (2.24), we have

(2.25)  f(x) − λ ⩾ δd(x, L_{f}(λ)), ∀x ∈ S_{2}.

Therefore (2.16) is seen to hold by (2.18), (2.19), (2.23) and (2.25). □

Remark 2. If there exists ε > 0 such that 𝔇(ε) = ∅, then there exist υ > λ and a nonempty open set Q satisfying (2.13) and (2.14). Indeed, pick x_{0} ∈ X\L_{f}(λ) and take υ such that f(·) > υ ⩾ λ at x_{0} and hence on a bounded open neighborhood Q of x_{0}. This is possible because f is lower semicontinuous. Therefore Theorem 2.7 extends the result of Theorem 2.5.

Let C_{L_{f} (λ)}(x) denote the cone defined by

C_{L_{f} (λ)}(x) := {u ∈ X; there exists T > 0 such that x + tu ∈ L_{f}(λ), ∀t ∈ (0, T]}.

This may be referred to as the linear cone of L_{f}(λ) at x, in general a rather smaller set than the contingent cone T_{L_{f} (λ)}(x).

Proposition 2.8. Let X be a Banach space, λ ∈ R and f : X → R a C^{1}- function. Suppose there exists x ∈ L_{f}(λ) such that ∇f(x) = 0 and C_{L_{f} (λ)}(x) ≠ X. Then f has no error bound for L_{f}(λ).

Proof. Let x ∈ L_{f}(λ), ∇f(x) = 0 and u ∉ C_{L_{f} (λ)}(x). By definition there exists a sequence (t_{n}) ↓ 0 such that

(2.26)  x + t_{n}u ∉ L_{f}(λ), ∀n.

Take z_{n} ∈ L_{f}(λ) such that

(2.27)  ∥x + t_{n}u − z_{n}∥ ⩽ (1 + \frac{1}{n})d(x + t_{n}u, L_{f}(λ)), ∀n.

By virtue of the Intermediate Value Theorem and by replacing z_{n} with a point in the line-segment (x+t_{n}u, z_{n}) if necessary, we can assume that f(z_{n}) = λ. Note that, since x ∈ L_{f}(λ), the right hand side of (2.27) converges to 0 as n → +∞. Thus, letting t′_{n} = ∥x + t_{n}u − z_{n}∥ , one has t′_{n} → 0. Let v_{n} = \frac{x+t_{n}u−z_{n}}{t′_{n}} . Then x + t_{n}u = z_{n} + t′_{n}v_{n}. For each t′_{n}, by the Mean Value Theorem there exists ξ_{n} lying in the line segment (z_{n} + t′_{n}v_{n}, z_{n}) such that

(2.28)  \frac{f(z_{n} + t′_{n}v_{n}) − f(z_{n})}{t′_{n}} = ∇f(ξ_{n})v_{n} → 0, as n → +∞

because ξ_{n} → x and ∇f(x) = 0. It follows from (2.27) and (2.28) that

lim_{n→+∞} \frac{f(x+t_{n}u)−λ}{d(x+t_{n}u,L_{f} (λ))} = lim_{n→+∞} \frac{t′_{n}}{d(x+t_{n}u,L_{f} (λ))} · \frac{f(z_{n}+t′_{n}v_{n})−f(z_{n})}{t′_{n}}
= lim_{n→+∞} ∇f(ξ_{n})v_{n} = 0.

This implies that f has no error bound for L_{f}(λ). □

3. Second-order directional derivatives and second-order sufficient conditions. In this section we suppose that f : X → R is a Gateaux differentiable function with derivative denoted by ∇f. Recall that the second-order lower directional derivative of f at x in the directions u, v is defined by

(3.1)  d_{−}^{2}f(x; u, v) := lim inf_{t↓0} \frac{f(x + tu + t^{2}v) − f(x) − t∇f(x)u}{t^{2}}.

This second-order directional derivative has been studied by many authors; see [1], [6], [7] and [9]. Note in particular that when f is a C^{2}-function, then

(3.2)  d_{−}^{2}f(x; u, 0) = \frac{1}{2}∇^{2}f(x)(u, u).

The following result may be regarded as a generalization of Taylor expansion. For related results see [2] and [5].

Theorem 3.1. (Inequality form of Taylor expansion) Let f : X → R be lower semicontinuous and Gateaux differentiable. Let x, u ∈ X and T > 0. Then there exists α ∈ [0, T) such that

(3.3)  \frac{f(x + T u) − f(x) − T ∇f(x)u}{T^{2}} ⩽ d_{−}^{2}f(x + αu; u, 0).

Proof. Define ρ := f(x + T u) − f(x) − T ∇f(x)u and h : [0, T] → R by
(3.4)  h(t) := f(x + tu) − t∇f(x)(u) − \frac{t^{2}}{T^{2}} ρ.

Then h is lower semicontinuous on [0, T] and h(T) = h(0). Thus, h attains a minimum at some point α ∈ [0, T) and hence

(3.5)  ∇f(x + αu)u − ∇f(x) − \frac{2α}{T^{2}} ρ = 0

((3.5) holds trivially if α = 0). Therefore,

\frac{h(α+λ)−h(α)}{λ^{2}}

= \frac{f(x+αu+λu)−f(x+αu)−λ∇f(x+αu)u}{λ^{2}} − \frac{ρ}{T^{2}} + \frac{∇f(x+αu)u−∇f(x)u− \frac{2α}{T^{2}} ρ}{λ}
= \frac{f(x+αu+λu)−f(x+αu)−λ∇f(x+αu)u}{λ^{2}} − \frac{ρ}{T^{2}} .

By the minimality of α, it follows that

0 ⩽ lim inf_{λ↓0} \frac{f(x + αu + λu) − f(x + αu) − λ∇f(x + αu)u}{λ^{2}} − \frac{ρ}{T^{2}} ,

that is,

\frac{ρ}{T^{2}} ⩽ d_{−}^{2}f(x + αu; u, 0)

proving (3.3).

We are now ready to present our second-order sufficient condition for f to have an error bound. Recall that 𝔇(ε) is defined by

(3.6)  𝔇(ε) := {x ∈ X\L_{f}(λ); ∥∇f(x)∥ ⩽ ε}  (ε > 0).

Theorem 3.2. Let f : X → R be continuous and Gateaux differentiable. Suppose that L_{f}(λ) ≠ ∅ and that there exist υ > λ and T, δ, ρ > 0 such that the following conditions hold:

(a) 𝔇(ρ) ⊆ X\L_{f}(υ).

(b) For each x ∈ 𝔇(ρ), there exists a unit vector u such that

d_{−}^{2}f(x + αu; u, 0) < −δ, ∀α ∈ [0, T).

Then f has an error bound for L_{f}(λ).

Proof. Let ε = min\{ρ, \frac{δ}{4}, \frac{T δ}{2} \} and β = min\{υ − λ, \frac{ε}{2}, 1, \frac{T δ}{2} \}. We claim that for each x ∈ Domf\L_{f}(λ) there exists y ∈ f^{−1}[λ, +∞) such that

f(x) − f(y) ⩾ βd(x, y) > 0.

Granting this, one can complete the proof by virtue of Corollary 2.2. To establish our claim let x ∈ Domf\L_{f}(λ) and we divide into the following three cases.

Case 1. x ∈ 𝔇(ε) and d(x, L_{f}(λ)) < 1. Since f is continuous, we can take y ∈ L_{f}(λ) such that f(y) = λ and

∥x − y∥ < 1.

Since x ∈ 𝔇(ε) ⊆ X\L_{f}(υ), one has f(x) > υ and hence

(3.7)  f(x) − f(y) ⩾ υ − λ ⩾ (υ − λ)d(x, y) ⩾ βd(x, y) > 0.

Case 2. x ∈ 𝔇(ε) and d(x, L_{f}(λ)) ⩾ 1. By assumption let u be a unit vector such that

d_{−}^{2}f(x + αu; u, 0) < −δ, ∀α ∈ [0, T).

Let T′ = min\{\frac{1}{2}, T \}; then ε ⩽ \frac{T′δ}{2} . Note that x + T′u ∉ L_{f}(λ) as d(x, L_{f}(λ)) ⩾ 1 and by Theorem 3.1 there exists α ∈ [0, T′) such that

f(x + T′u) − f(x) − T′∇f(x)u ⩽ T^{′2}d_{−}^{2}f(x + αu; u, 0) < −T^{′2}δ

Note that ∇f(x)u ⩽ ε since x ∈ 𝔇(ε); hence

f(x + T′u) − f(x) − T′ε ⩽ −T^{′2}δ.

It follows that

(3.8)  \begin{aligned}f(x) − f(x + T′u) & ⩾ & T′(T′δ − ε) \\ & ⩾ & \frac{T^{′2}δ}{2} = \frac{T′δ}{2} d(x, x + T′u) \\ & ⩾ & βd(x, x + T′u) > 0. \end{aligned}

Case 3. x ∈ (X\𝔇(ε))\L_{f}(λ). Then ∥∇f(x)∥ > ε and and hence there exists a unit vector u such that ∇f(x)u < −ε. Thus, there exists (t_{n}) ↓ 0 such that

(3.9)  f(x) − f(x + t_{n}u) > t_{n}ε = εd(x, x + t_{n}u) ⩾ βd(x, x + t_{n}u), ∀n.

Since f(x) > λ, let y = x + t_{n}u with n sufficiently large one has y ∉ L_{f}(λ).

Corollary 3.3. Let f : X → R be a C^{2}-function. Let λ ∈ R be such that L_{f}(λ) ≠ ∅.

Let ρ, δ > 0. We suppose that ∇^{2}f is uniformly continuous on the δ-neighborhood U of 𝔇(ρ). Then f has an error bound for L_{f}(λ) if any one of the following conditions is satisfied:

(a) 𝔇(ρ) = ∅.

(b) there exists υ > λ with 𝔇(ρ) ⊆ X\L_{f}(υ) such that

sup_{x∈𝔇(ρ)} inf_{∥u∥=1} ∇^{2}f(x)(u, u) < 0.

Proof. We only need to deal with the case (b). Let ε > 0 such that

(3.10)  sup_{x∈𝔇(ρ)} inf_{∥u∥=1} ∇^{2}f(x)(u, u) < −3ε

Take T ∈ (0, δ) such that

(3.11)  ∥∇^{2}f(x) − ∇^{2}f(Y)∥ < δ

for all x, y ∈ U with ∥x − y∥ < T. Let x ∈ 𝔇(ρ), by (3.10) there exists a unit vector u such that

∇^{2}f(x)(u, u) < −3ε

and so by (3.11)

2d_{−}^{2}f(y, u, 0) = ∇^{2}f(y)(u, u) < −2ε

whenever ∥y − x∥ < T. Therefore the result follows from Theorem 3.2.

In the next section, we shall apply the results obtained in sections 2 and 3 to give a description exactly when a quadratic function on X has a Lipschitz error bound.

4. Error bound for a quadratic function on Banach space. Throughout this section, f will denote a quadratic function:

(4.1)  f(x) := \frac{1}{2} < x, Ax > + < x, z^{∗} > +γ, ∀x ∈ X,

where X is a Banach space with the dual space X^{∗}, γ ∈ R, z^{∗} ∈ X^{∗} and A : X → X^{∗} is a bounded linear operator from X into X^{∗}. Let A′ denote the dual operator of A defined by

< z, A′x >=< x, Az >

for all x, z ∈ X. Let \frac{1}{2}(A + A′) be denoted by Ā. Then

(4.2)  \begin{aligned}∇f(x) & = & \frac{1}{2}(< ·, Ax > + < x, A· >)+ < ·, z^{∗} > \\ & = & \frac{1}{2}(A + A′)x + z^{∗} = Āx + z^{∗} \end{aligned}

and

∇^{2}f(x)(u, u) =< u, \overline{A}u >, ∀x, u ∈ X,

We note that \overline{A} is symmetric: < z, \overline{A}x >=< x, \overline{A}z > for all x, z ∈ X. Since < x, Ax >=< x, \overline{A}x >=< x, A′x >, we can suppose henceforth that A is symmetric (replace A by \overline{A} if necessary). Further, we can show that

(4.3)  f(x + u) − f(x) = ∇f(x)u + \frac{1}{2}∇^{2}f(x)(u, u), ∀x, u ∈ X.

Denote the set of all critical (stationary) points of f by N_{∇f}, that is

N_{∇f} := {x ∈ X; ∇f(x) = 0}.

By (4.2) one has N_{∇f} = {x ∈ X; Ax = −z^{∗}}. We recall that (x_{n}) is a critical (or stationary) sequence of f if lim_{n→+∞} ∇f(x_{n}) = 0. η is called a critical value of f if η = f(x) for some x ∈ N_{∇f}. We will show in the following lemma that there is only one critical value (provided that N_{∇f} is nonempty).

Lemma 4.1. Suppose that N_{∇f} is nonempty. Then f and z^{∗} are constant on N_{∇f}. Moreover, if z_{0} ∈ N_{∇f}, then it holds for all x ∈ N_{∇f} that

(4.4)  z^{∗}(x) = − < z_{0}, Az_{0} >

and that

(4.5)  f(x) = γ − \frac{1}{2} < z_{0}, Az_{0} >, ∀x ∈ N_{∇f}.

If we assume in addition that A is of closed range, then there exists m > 0 such that, whenever (x_{n}) is a critical sequence of f, one has

(4.6)  lim sup_{n→+∞} d(x_{n}, N_{∇f} − z_{0}) ⩽ \frac{∥z^{∗}∥}{m}

and

(4.7)  lim_{n→+∞} f(x_{n}) = γ − \frac{1}{2} < z_{0}, Az_{0} >,

(γ − \frac{1}{2} < z_{0}, Az_{0} > will be referred to as the critical value of f.)

Proof. Since A is assumed symmetric, (4.2) reads

(4.8)  ∇f(x) = Ax + z^{∗}.

Then Az_{0} + z^{∗} = 0 and Ax + z^{∗} = 0; hence Ax = Az_{0} for each x ∈ N_{∇f}. Therefore, by symmetry of A,

z^{∗}(x) =< x, −Az_{0} >=< z_{0}, −Ax >=< z_{0}, −Az_{0} >, ∀x ∈ N_{∇f}

verifying (4.4). This also implies that

(4.9)  < x, Ax >=< z_{0}, Az_{0} >, ∀x ∈ N_{∇f}.

Consequently

\begin{aligned}f(x) & = & \frac{1}{2} < x, Ax > +z^{∗}(x) + γ \\ & = & γ − \frac{1}{2} < z_{0}, Az_{0} >, ∀x ∈ N_{∇f} \end{aligned}

verifying (4.5).

Suppose in addition that AX is closed. Then there exists m > 0 such that

∥Ax∥ ⩾ md(x, ker A), ∀x ∈ X

(cf. [18, IV. 5, Th. 5.9]). Since (4.8) reads ∇f(x) = A(x − z_{0}) it follows that

∥∇f(x_{n}) − z^{∗}∥ ⩾ m · d(x_{n}, N_{∇f} − z_{0}).

Hence, if lim_{n→+∞} ∇f(x_{n}) = 0, one has

∥z^{∗}∥ ⩾ m lim sup_{n→+∞} d(x_{n}, N_{∇f} − z_{0})

proving (4.6).

Now, for each large n, one applies (4.6) to obtain y_{n} ∈ N_{∇f} such that

∥x_{n} − (y_{n} − z_{0})∥ ⩽ \frac{∥z^{∗}∥}{m} + 1.

Note that, by (4.5), each f(y_{n}) = η, where η := γ− < z_{0}, Az_{0} > . On the other hand, by the Mean Value Theorem, there exists ξ_{n} in the line segment (x_{n}, y_{n}) such that

|f(x_{n}) − η| = |f(x_{n}) − f(y_{n})|
= |∇f(ξ_{n})(x_{n} − y_{n})|
⩽ ∥∇f(ξ_{n})∥ ∥x_{n} − y_{n}∥
⩽ ∥∇f(ξ_{n})∥ (\frac{∥z^{∗}∥}{m} + ∥z_{0}∥ + 1) → 0

because ∇f(ξ_{n}) → 0 as ∇f is affine, ∇f(x_{n}) → 0 and ∇f(y_{n}) = 0. Therefore (4.7) holds. □

Let λ ∈ R. In the following, we consider the problem whether f has an error bound for L_{f}(λ) or not. To avoid trivialities we suppose that X ≠ L_{f}(λ) ≠ ∅.

Proposition 4.2. Suppose that z^{∗} ∉ \overline{AX}, the closure of the range AX of A. Then f has an error bound for L_{f}(λ).

Proof. By the Hahn-Banach Theorem, there exists u^{∗∗} ∈ X^{∗∗} of norm 1 such that

u^{∗∗}(z^{∗}) = ∥z^{∗}∥ and u^{∗∗}(Ax) = 0, ∀x ∈ X.

Since ∇f(x) = Ax + z^{∗} it follows that

u^{∗∗}(∇f(x)) = ∥z^{∗}∥ , ∀x ∈ X.

By the Bipolar Theorem, there exists a net (u_{κ}) in the unit ball of X which converges to u^{∗∗} in the σ(X^{∗∗}, X^{∗}) -topology. Then, for any x ∈ X there exists u_{κ} such that

∇f(x)(\frac{u_{κ}}{∥u_{κ}∥}) > \frac{∥z^{∗}∥}{2 ∥u_{κ}∥} ⩾ \frac{∥z^{∗}∥}{2}.

Therefore (2.8) is satisfied (with δ = \frac{∥z^{∗}∥}{2}) and so Theorem 2.5 implies that f admits an error bound for L_{f}(λ) whenever L_{f}(λ) ≠ ∅. □

Proposition 4.3. Let λ ∈ R. Suppose that A is not positive semidefinite and is of closed range. If N_{∇f} ∩ L_{f}(λ) = ∅, then f has an error bound for L_{f}(λ).

Proof. Let us first consider the case that N_{∇f} = ∅. Since ∇f(x) = Ax + z^{∗}, it follows that z^{∗} ∉ AX. Since A is assumed to be of closed range, it follows from Proposition 4.2 that f has an error bound for L_{f}(λ). In the following we assume that N_{∇f} ≠ ∅. We claim that there exist υ > λ and ε > 0 such that 𝔇(ε) ⊆ X\L_{f}(υ). Indeed, if not, then there exists a sequence (x_{n}) such that ∥∇f(x_{n})∥ ⩽ \frac{1}{n} and f(x_{n}) ⩽ λ+ \frac{1}{n} for each n. Thus, letting η to denote the critical value of f, it follows from Lemma 4.1 that η ⩽ λ, contradicting the assumption that N_{∇f} ∩ L_{f}(λ) = ∅. Therefore our claim stands. Moreover, since A is not positive semidefinite, there exists a unit vector u_{0} such that < u_{0}, Au_{0} >< 0. Since ∇^{2}f(z) = A for each z ∈ X, Corollary (3.3) implies that has an error bound for L_{f}(λ). □

For the case when A is of closed range, the next theorem together with Proposition 4.2 provide a complete answer for the question, ”when does f defined by (4.1) have an error bound?”

Theorem 4.4. Let λ ∈ R. Suppose further that z^{∗} ∈ AX (namely N_{∇f} ≠ ∅).Then the following assertions hold.

(i) If λ is the critical value of f, then f has no error bound for L_{f}(λ)

(ii) If λ is not the critical value of f, then f has an error bound for L_{f}(λ) provided that A is of closed range.

Proof. (i) We assume that z^{∗} ∈ AX and that λ = f(x) for some (and hence for all by Lemma 4.1) x in N_{∇f}. By virtue of Proposition 2.8 it is sufficient to show C_{L_{f} (λ)}(x) ≠ X. By the way of contradiction we assume that C_{L_{f} (λ)}(x) = X. Then for any u ∈ X, there exists T_{u} > 0 such that x + tu ∈ L_{f}(λ), ∀t ∈ [0, T_{u}]. Thus, for each t ∈ [0, T_{u}], it follows from (4.3) that

\begin{aligned}λ ⩾ f(x + tu) & = & f(x) + ∇f(x)tu + \frac{t^{2}}{2} ∇^{2}f(x)(u, u) \\ & = & λ + \frac{t^{2}}{2} < u, Au > . \end{aligned}

This implies that

< u, Au >⩽ 0, ∀u ∈ X.

Thus, f is a concave function and hence, any x ∈ N_{∇f} is a maximum point of f. Consequently L_{f}(λ) = X, the case that we have rejected at the outset.

(ii) By Lemma 4.1, there exists η ∈ R such that f(x) = η for each x ∈ N_{∇f}. By assumption, λ ≠ η. Thus, we have two cases to consider: (a) λ < η and (b) λ > η. For the case (a), we can assume that A is not positive semidefinite (if A is positive semidefinite, then f is a convex function and so η = inf f. Since η > λ, this is not possible because we have assumed that L_{f}(λ) ≠ ∅). Thus, since S is of closed range it follows from Proposition 4.3 that f has an error bound for L_{f}(λ).

Next consider the case (b): λ > η. Then

(4.10)  inf_{x∉L_{f} (λ)} ∥∇f(x)∥ > 0

(and so (2.8) is satisfied for some δ > 0 and hence it follows from Theorem 2.5 that f has an error bound for L_{f}(λ)). To verify (4.10), we suppose on the contrary that there exists a sequence (x_{n}) ⊆ X\L_{f}(λ) such that ∇f(x_{n}) → 0. Then, by Lemma 4.1 it follows that lim_{n→+∞} f(x_{n}) = η. But this is not possible because η is strictly smaller than λ and λ < f(x_{n}) for all n. □

In the special case when X = R^{n}, the consideration of error bound for a general quadratic function f is equivalent to that for ϕ of the form

ϕ(x) := \frac{1}{2} ∑_{i=1}^{k} x_{i}^{2} − \frac{1}{2} ∑_{i=k+1}^{m} x_{i}^{2} + ∑_{i=m+1}^{n} c_{i}x_{i} + γ

where 0 ⩽ k ⩽ m ⩽ n (cf. [13]). Note that

(4.11)  ϕ(x) = \frac{1}{2} < x, Hx > + < c, x > +γ,

where H = [ \begin{matrix}I_{k} & 0 & 0 \\ 0 & −I_{m−k} & 0 \\ 0 & 0 & 0 \end{matrix} ] , I_{k} and I_{m} are respectively the k × k unit matrix

and the (m − k) × (m − k) unit matrix, c = (0, ⋯, 0, c_{m+1}, ⋯, c_{n}) and x ∈ R^{n}. The (operator associated with) matrix H is certainly of closed range. To compare our results with that in [13], let us fix λ = 0, and write S_{ϕ} for L_{ϕ}(0). We assume that ∅ ≠ S_{ϕ} ≠ R^{n}, that is, we reject the following trivial cases

(a) k = m, c = 0, and γ > 0.
(b) 0 = k < m, c = 0, and γ ⩽ 0.

Note that also that c = 0 if and only if c belongs to the range of H.

Corollary 4.5. Let ϕ be of the form (4.11).

(I) Suppose that c = 0. Then ϕ has an error bound for S_{ϕ} if and only if γ ≠ 0. (II) If c ≠ 0, then ϕ has an error bound for S_{ϕ}.

Proof. (I) Since ∇ϕ(x) = Hx + c = Hx, we see that 0 ∈ N_{∇ϕ} and γ = ϕ(0) is the critical value of ϕ. It follows from Theorem 4.4 that γ ≠ λ if and only if ϕ has an error bound.

(II) This follows from Proposition 4.2. □

5. Appendix. We end the paper with an example showing that Theorem 2.5 improves a result in [13].

Example 1. Let X = ℓ^{2}. Let e_{n} ∈ ℓ^{2} denote the n^{th} unit vector: e_{n} := (0, ⋯, 0, 1, 0, ⋯ 0), where 1 appears at the n^{th} coordinate. Let L_{n} be the line segment defined by

L_{n} := {x ∈ ℓ^{2}; x = te_{n}, n^{−1} ⩽ t ⩽ 1}.

and let A := ∪_{n=2}^{+∞}L_{n}. Then A ∪ {0} is closed and for any unit vector v, there exists ε > 0 such that

(5.1)  tB(v, ε) ∩ A = ∅, ∀ 0 ⩽ t < ε.

In fact, the claim is clearly true if v = e_{n} for some n ⩾ 2. Moreover if the claim is not true for some unit vector v ≠ e_{n}, n = 2, 3, ⋯, then there exist sequences (v_{n}) ⊆ ℓ^{2}, (ε_{n}) ↓ 0 and (t_{n}) ↓ 0 such that each

(5.2)  v_{n} ∈ t_{n}B(v, ε_{n}) ∩ A.

Since v_{n} ∈ L_{m_{n}} for some m_{n} ⩾ 2, one can write τ_{n}e_{m_{n}} for v_{n} with m_{n}^{−1} ⩽ τ_{n} ⩽ 1. It follows from (5.2) that

\frac{τ_{n}}{t_{n}} e_{m_{n}} = \frac{v_{n}}{t_{n}} → v

which implies that \frac{τ_{n}}{t_{n}} → 1 and that (e_{m_{n}}) → v. By definition of e_{n}’s, this is impossible. Define a function f : X → R ∪ {+∞} by

f(x) := \{ \begin{matrix}−(1 − n^{− \frac{1}{3}} )[\frac{t−n^{−1}}{1−n^{−1}} − 1], & x ∈ L_{n}, x = te_{n}, n = 2, 3, ⋯, \\ 1 + ∥x∥ , & x ∉ L_{n}, ∥x∥ < 1, n = 2, 3, ⋯, \\ 0, & ∥x∥ ⩾ 1 \end{matrix}

Then f is lower semicontinuous and

0 ∉ L_{f}(0) = {x ∈ ℓ^{2}; ∥x∥ ⩾ 1} ∪ {e_{n}; n = 2, 3, ⋯ }.

Let u_{n} = n^{− \frac{1}{3}} e_{n}. Then n^{− \frac{2}{3}} u_{n} = \frac{1}{n}e_{n} ∈ L_{n} and so one has

\begin{aligned}d_{−}f(0; 0) & ⩽ & lim_{n→+∞} \frac{1}{n^{− \frac{2}{3}}} (f(n^{− \frac{2}{3}} u_{n}) − f(0)) \\ & = & lim_{n→+∞} \frac{−n^{− \frac{1}{3}}}{n^{− \frac{2}{3}}} = −∞ \end{aligned}

showing that 0 ∉ 𝔇. Moreover, by (5.1), it is easy to see that

d_{−}f(0; v) ⩾ 0, ∀v ≠ 0.

Thus, one has

inf_{∥v∥=1} d_{−}f(0; v) ⩾ 0.

Since 0 ∉ L_{f}(0), this implies that the sufficient condition of [13, Theorem 2.5] is not satisfied. On the other hand, note that for any x with x ∉ A ∪ {0} and ∥x∥ < 1,

∇f(x) = \frac{x}{∥x∥}

Then for u = −\frac{x}{∥x∥}

(5.3)  d_{−}f(x; u) = ∇f(x)u = −1.

If x ∈ A : x = te_{n}, \frac{1}{n} ⩽ t < 1 for some n ⩾ 2, then

(5.4)  d_{−}f(x; e_{n}) ⩽ −\frac{1 − n^{− \frac{1}{3}}}{1 − n^{−1}} ⩽ −(1 − 2^{− \frac{1}{3}} ).

Combining (5.3), (5.4), and noting that 0 ∉ 𝔇 we have

sup_{x∈𝔇\L_{f} (0)} inf_{∥v∥=1} d_{−}f(x; v) ⩽ −(1 − 2^{− \frac{1}{3}} ) < 0.

Thus, (2.8) is satisfied and Theorem 2.5 is applicable.

REFERENCES

[1] A. Ben-Tal, Second-order and related extremality conditions in nonlinear programming, J. Optim. Theory Appl., 3 (1980), pp. 143–165.

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

[3] F. H. Clarke, Optimization and Nonsmooth Analysis, Wiley, 1983.

[4] R. Cominetti, Metric Regularity, tangent sets, and second-order optimality conditions, Appl. Math. Optim., 21 (1990), pp. 265–287.

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

[6] R. Cominetti and J.-P. Penot, Tangent sets of order one and two to the positive cones of some functional space, Appl. Math. Optim., 36 (1997), pp. 291–312.

[7] R. Cominetti, On pseudo-differentiablity, Trans. Amer. Math. Soc., 324 (1991), pp. 843–865.

[8] A. Hamel, Remarks to equivalent formulation of Ekeland’s variational principle, Optimization, 31 (1994), pp. 233–238.

[9] L. R. Huang and K. F. Ng, On some relations between Chaney’s generalized second-order directional derivative and that of Ben-Tal and Zowe, SIAM J. Control and Optimization, 34 (1996), pp. 1220–1234.

[10] L. R. Huang, K. F. Ng and J.-P. Penot,On minimizing and critical sequences in nonsmooth optimization, SIAM J. Optim., 10 (2000), pp. 999–1019.

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

[12] Z. Q. Luo and J. F. Sturm, Error bounds for quadratic systems, In High Performance Optimization, H. Frenk, K. Roos, T. Terlaky, and S. Zhang, eds., Kluwer Academic Publishers, Dordrecht, 2000, pp.383–404.

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

[14] K. F. Ng and X. Y. Zheng, Global error bounds with fractional exponents, Math. Programming, 88 (2000), pp. 357-370.

[15] J.-P. Penot, Conditioning convex and nonconvex problems, J. Optim. Theorey Appl., 90 (1997), pp. 209-221.

[16] J. S. Pang, Error bounds in mathematical programming, Math. Programming , 79 (1997), pp. 299–332.

[17] R. T. Rockafellar, First and second-order epi-differentiability in nonlinear programming, Trans. Amer. Math. Soc., 307 (1988), pp. 75–107.

[18] A. E. Taylor and D. C. Lay, Introduction to Function Analysis, John Wiley & Sons (1980).