Journal of Convex Analysis Volume 2 (1995), No.1/2, 117–144

Proximal Smoothness and the Lower–C^{2} Property

F. H. Clarke^{1}^{,}^{2}

Centre de recherches mathématiques, Université de Montréal, Montréal, Québec H3C 3J7, Canada.

R. J. Stern^{1,}^{2}

Department of Mathematics and Statistics, Concordia University, Montreal, Quebec H4B 1R6, Canada.

P. R. Wolenski

Department of Mathematics, Louisiana State University, Baton Rouge, Louisiana 70803, USA.

Dedicated to R. T. Rockafellar on his 60th Birthday

A subset X of a real Hilbert space H is said to be proximally smooth provided that the function d_{X} : H → R (the distance to X) is continuously differentiable on an open tube U around X. It is proven that this property is equivalent to d_{X} having a nonempty proximal subgradient at every point of U, and that the (Gâteaux = Fréchet) derivative is locally Lipschitz on U. The Lipschitz behavior of the derivative is a consequence of the fact that under proximal smoothness, the metric projection onto X is single valued and Lipschitz on U. Alternate characterizations of proximal smoothness are given as well, in terms of properties of the proximal normal cone multifunction on X and on nearby closed neighborhoods of X. In case X is weakly closed, the list of equivalences is extended to include each point of U admitting a unique closest point in X. Further specializations are given in finite dimensions. In that setting, we discuss properties of locally Lipschitz real valued functions whose epigraphs are proximally smooth in a local sense. It is demonstrated that this function class coincides with the lower–C2 functions studied by Rockafellar.

Keywords : Hilbert space, distance function, proximal smoothness, Gâteaux, strict and Fréchet derivatives, closest points, nonsmooth analysis, optimization, epigraph, lower–C2 function.

1991 Mathematics Subject Classification: 26B05

1. Introduction

In the core theory of nonsmooth analysis, the major analytic concepts for functions (various generalized notions of directional derivative and gradient) have geometric counterparts for sets (corresponding generalizations of the classical ideas of tangency and normality). This duality, which has always played an important role in the development of the subject,

1 Research supported in part by the Natural Sciences Engineering Research Council of Canada. 2 Research supported in part by le fonds FCAR du Québec.

ISSN 0944-6532 / $ 2.50 ◯^{c} Heldermann Verlag

118 F. H. Clarke, R. J. Stern, P. R. Wolenski / Proximal smoothness, lower–C^{2} property

is generally achieved by rephrasing analytic properties of a function f in terms of geometric properties of epi(f), the epigraph of f. An indispensible tool employed in forging this link has been the distance function. The present article proceeds in this vein. In a general Hilbert space setting, we shall employ proximal analysis in order to characterize proximal smoothness of a general closed set X, where this connotes continuous differentiability of d_{X} (the distance function to X) on an open tube U around X. We then proceed to establish analytic properties of the class of functions f : R^{n} → R for which epi(f) is proximally smooth in a local sense. It transpires that this function class corresponds precisely to one considered by R. T. Rockafellar in [18]: f is said to be lower–C^{2} provided that for each point y ∈ R^{n} there exists an open neighborhood N_{y} of y so that locally f has the representation

f(x) = max_{s∈S} F (x, s) ∀x ∈ N_{y},  (1.1)

where S is a compact set in some topological space, and F : N_{y} × S → R is a function which has second partial derivatives with respect to x and which, along with these derivatives, is jointly continuous in (x, s) ∈ N_{y} × S. Thus f is the value function of a family of maximization problems parametrized by x and satisfying specific continuity and smoothness requirements. Rockafellar derived several equivalent conditions which characterize a locally Lipschitz function f being lower–C^{2}, including a type of monotonicity in terms of the Clarke subdifferential of f, the expressibility of f as a difference of convex and quadratically convex functions, as well as the fact (referred to in section 5 below) that F in (1.1) may without loss of generality be taken to be of a particular form in which it is quadratic in x and continuous in s. In [18], the distinctions between the class of lower–C^{2} functions and the analogously defined class of lower–C^{1} functions were made clear. Properties of the latter class are well–known; see e.g. Danskin [9], Clarke [8], [5], Rockafellar [19] and Spingarn [20]. As was pointed out in [18], however, the lower–C^{k} classes all coincide for 2 ≤ k ≤ ∞. Let us also mention that the lower–C^{2} property has appeared elsewhere in the literature as well, along with geometric versions, under such names as “generalized convexity”, “weak convexity”, “convexity up to a square”, “F –convexity”, and so on. We refer the reader to Vial [21] for a comprehensive treatment of this subject as well as for references and historical comments. See also Hiriart-Urruty [12] in this regard.

The plan of the present article is as follows: Section 2 contains the requisite background in nonsmooth analysis, including recent results of Clarke, Ledyaev and Wolenski [6] on proximal subdifferentiability of the distance function in Hilbert space. Section 3 contains certain general results on the distance function which are of independent interest, and are required in section 4, where we present our main characterizations of proximal smoothness, with the only requirement on X being closedness. Notable among the properties equivalent to proximal smoothness is that d_{X} possess a nonempty proximal subdifferential at every point of the tube U. It will also be shown that the derivative is then necessarily locally Lipschitz on U. The Lipschitz behavior of the derivative will be seen to follow from the fact that for X proximally smooth, the metric projection onto X is single valued and Lipschitz on U. We shall also obtain geometric characterizations which involve the behavior of the proximal normal cone multifunction on X, as well as on nearby approximations of X. Under the additional assumption that X is weakly closed, the list of equivalences is extended to include the existence of a unique closest point in X for every u ∈ U, and certain specializations to the finite dimensional case are included as well. In section 5 we demonstrate that a locally Lipschitz function’s being lower–C^{2} is in fact a local form of proximal smoothness of its epigraph.

Prior to proceeding, we pause for a heuristic digression which serves to motivate some of the subsequent results. Consider a closed set X ⊆ R^{n}. A useful pedagogical device for describing the existence of proximal normals at a point x ∈ bdry(X) is the “paintability” of x; that is, the existence a closed ball (that can be thought of as a paintroller, if one prefers) which touches X only at x. We can then go on to say that X is “paintable” provided that, outfitted with an infinite family of paintrollers of arbitrarily small radii, we can paint every point in the boundary of X. But what if we had our disposal only a single paintroller; that is, only one radius r was available? Our results will show that paintability of X under this restriction is tantamount to what we have above termed proximal smoothness of X. An outcome of this is that if one paints the boundary of X with a single roller, and allows the roller to assume all possible positions at each point being painted, the locus of the roller’s center (which is the boundary of a closed r–neighborhood of X) is a C^{1} manifold; see part 4 of Corollary 4.15 below.

2. Preliminaries in nonsmooth analysis

In this section we present a concise overview of basic material from nonsmooth analysis; other required facts will be mentioned later. We cite Clarke [8], [5], [4], and Loewen [14] as general references and guides to the literature.

Throughout this article, we will let X denote a closed subset of a real Hilbert space H, which is equipped with an inner product ⟨·, ·⟩ and corresponding norm ∥ · ∥. The distance of a point u ∈ H to X is given by

d_{X}(u) := inf{∥u − x∥ : x ∈ X}.

We require the fact that the distance function d_{X} : H → R is globally Lipschitz of rank 1. The (possibly empty) set of closest points to u in X is denoted

proj_{X}(u) := {x ∈ X : ∥u − x∥ = d_{X}(u)}.

The multifunction proj_{X} is referred to as the metric projection onto X. If u ∉ X and x ∈ proj_{X}(u), then we say that the vector u − x is a perpendicular to X at x. The set of all nonnegative multiples of such perpendiculars is denoted N_{X}^{P}(x), and is referred to as the proximal normal cone (or P–normal cone) to X at x. One can show that ζ ∈ N_{X}^{P}(x) if and only if there exists M > 0 such that the following proximal normal inequality holds:

M∥y − x∥^{2} ≥ ⟨ζ, y − x⟩ ∀y ∈ X.

(In general, M will depend on x.) Thus the P–normal cone is convex (but may not be closed even in finite dimensions). If x ∈ int(X) or no perpendiculars to X exist at x, then by convention, we set N_{X}^{P}(x) = {0}. Let x ∈ X and 0 ≠ ζ ∈ N_{X}^{P}(x). If one has

X ∩ int \{x + r (\frac{ζ}{∥ζ∥} + cl(B))\} = ϕ ∀y ∈ X,

then we shall say that ζ is realized by an r-ball. This expresses the fact that open ball of radius r centered at x + r\frac{ζ}{∥ζ∥} has empty intersection with X. It will be useful for us to note that this condition can be rephrased as

∥x + r\frac{ζ}{∥ζ∥} − y∥ ≥ r ∀y ∈ X.

Upon squaring and expanding, this in turn becomes

\frac{1}{2r}∥y − x∥^{2} ≥ ⟨\frac{ζ}{∥ζ∥}, y − x⟩ ∀y ∈ X.  (2.1)

Let f : U → (−∞, ∞] be a lower semicontinuous extended real valued function on an open set U ⊆ H, and denote its epigraph by

epi(f) := {(x, y) : x ∈ dom(f), y ≥ f(x)},

where dom(f) is the set of points in U where f is finite. The lower semicontinuity assumption is equivalent to epi(f) being closed, a fact which is relevant in regard to the next definition: ζ ∈ H is said to be a proximal subgradient (or P–subgradient) of f at x ∈ U provided that

(ζ, −1) ∈ N_{epi(f)}^{P}(x, f(x)).

The set of all such vectors is called the P–subdifferential of f at x, and is denoted ∂_{P} f(x). Similarly, the P–superdifferential of an upper semicontinuous function f at x is defined as

∂^{P} f(x) := −∂_{P} (−f)(x),

with the members of this set referred to as P–supergradients. One can prove that ζ ∈ ∂_{P} f(x) if and only if there exist positive numbers σ and γ such that the following proximal subgradient inequality is satisfied:

f(y) − f(x) + σ∥y − x∥^{2} ≥ ⟨ζ, y − x⟩ ∀y ∈ x + γB,

where B denotes the open unit ball in H. We shall require the fact that ∂_{P} f(x) ≠ ϕ for all x in a dense subset of dom(f); for an optimization based proof, see Clarke, Stern and Wolenski [7]. The following result on proximal subdifferentiability of the distance function to a closed subset of a Hilbert space, and the existence of nearest points, appears in Clarke, Ledyaev and Wolenski [6], and is a consequence of more general variational principles. Related work on the existence of closest points in more general Banach space settings (as well as further references on this topic) may be found in Borwein and Fitzpatrick [2]; see also Borwein and Giles [3] and Ioffe [13].

Theorem 2.1. Let u ∉ X, and suppose that ∂_{P} d_{X}(u) ≠ ϕ. Then the following hold:

(1) proj_{X}(u) is a singleton, say {x}, and ∂_{P} d_{X}(u) is the singleton {ζ}, where

ζ := \frac{u − x}{d_{X}(u)}.

(2) If u_{i} is a sequence in X such that u_{i} → u, and {ζ_{i}} = ∂_{P} d_{X}(u_{i}), then ζ_{i} → ζ.

Since d_{X} has a nonempty P–subdifferential on a dense subset of H\X, the preceding theorem readily yields the conclusion that proj_{X}(u) ≠ ϕ for all u in a dense subset of H\X, the complement of X. (See also Lau [14] for a Banach space version.) It readily follows that N_{X}^{P}(x) ≠ {0} for a dense set of x ∈ bdry(X).

The limiting normal cone (or L–normal cone) to X at x ∈ X is defined to be the set

N_{X}^{L}(x) := {ζ : ζ_{i} →^{w} ζ, ζ_{i} ∈ N_{X}^{P}(x_{i}), x_{i} → x},

where “→^{w}” denotes weak convergence; this set is nonempty and weakly closed. The convexified normal cone (or C–normal cone) to X at x is defined as

N_{X}^{C}(x) := clco[N_{X}^{L}(x)],

the closure of the convex hull of the L–normal cone at x.

The normal cones defined above give rise to corresponding nonempty subdifferential sets for f as one would expect:

∂_{L}f(x) := {ζ : (ζ, −1) ∈ N_{epi(f)}^{L}(x, f(x).
∂_{C}f(x) := {ζ : (ζ, −1) ∈ N_{epi(f)}^{C}(x, f(x).

These are referred to as the limiting subdifferential (or L–subdifferential) and convexified subdifferential (or C–subdifferential) of f at x, respectively. It is not difficult to show directly that

∂_{L}f(x) = {ζ : ζ_{i} →^{w} ζ, ζ_{i} ∈ ∂_{P} f(x_{i}), x_{i} → x, f(x_{i}) → f(x)}.

Should it exist, the directional derivative of f at x in the direction v is the quantity

f′(x; v) := lim_{t↓0} \frac{f(x + tv) − f(x)}{t}.

If there exists ζ ∈ H such that f′(x; v) = ⟨ζ, v⟩ for every v, then ζ is unique, and we say that ζ := f′(x) is the Gâteaux derivative of f at x. When f has a Gâteaux derivative at x and additionally the convergence defining f′(x; v) is uniform on bounded sets of v, then f′(x) is called the Fréchet derivative. If f has a Gâteaux derivative at x, then

∂_{P} f(x) ⊆ {f′(x)}.

In other words, if f is Gâteaux differentiable at x and has a nonempty P–subdifferential at x, then this reduces to the singleton {f′(x)}.

Let us now assume that f is Lipschitz of rank K on an open set U. By a result in [7], this is equivalent to ∥ζ∥ ≤ K for every ζ ∈ ∂_{P} f(x), for each x ∈ U where the P–subdifferential is nonempty. In the Lipschitz case, ∂_{C}f(x) is weakly compact, and one has the relation

∂_{C}f(x) = clco[∂_{L}f(x)].

Furthermore, the Gâteaux derivative satisfies has

f′(x) ∈ ∂_{C}f(x)

at points of differentiability. (If H = R^{n}, then Gâteaux and Fréchet differentiabilities coincide at x; this is false if the Lipschitz assumption is removed.) A Lipschitz function f is said to be strictly differentiable at x provided that ∂_{L}f(x) (or equivalently ∂_{C}f(x)) reduces to a singleton ζ. Should this occur, then necessarily ζ is the Gâteaux derivative f′(x). We say that f is continuously differentiable at a point x_{o} ∈ H provided that the Gâteaux derivative exists on a ball around x_{o}, and the mapping x → f′(x) is continuous on that ball. It is not difficult to show that this is equivalent to continuous Fréchet differentiability; hence there is no ambiguity about what is meant by a function being continuously differentiable (C^{1}). We will require the fact that continuous differentiability of f at x implies strict differentiability at x. (On the other hand, even a C^{1} function f : R → R can have ∂_{P} f(x) = ϕ “often”, in either the sense of measure or category, as is demonstrated by an example in [6].)

For f Lipschitz near x and given v ∈ H, one defines the generalized directional derivative of f at x in the direction v as

f^{o}(x; v) := lim sup_{y→x^{t↓0}} \frac{f(y + tv) − f(y)}{t}.

For any v, one has

f^{o}(x; v) = max{⟨ζ, v⟩ : ζ ∈ ∂_{C}f(x)}.

Furthermore, ζ ∈ ∂_{C}f(x) if and only if

⟨ζ, v⟩ ≤ f^{o}(x; v) ∀v ∈ H.

We say that f (still assumed Lipschitz near x) is regular at x if the ordinary directional derivative f′(x; v) exists and f′(x; v) = f^{o}(x; v) for every v ∈ H. We shall require the fact that regularity at x is guaranteed when f is continuously differentiable at x, or if f is strictly differentiable at x. A closed set X ⊂ H is said to be regular at x ∈ X provided that

lim sup_{y∈X^{y→x}} ⟨ζ, \frac{y − x}{∥y − x∥}⟩ ≤ 0 ∀ζ ∈ N_{X}^{C}(x).

One can show that this definition of regularity agrees with the usual one given via tangency notions ([8], [5]) and that a sufficient condition for this property is that N_{X}^{P}(x) = N_{X}^{C}(x). Also, regularity of a Lipschitz function f at x is equivalent to regularity of its epigraph at (x, f(x)), and so a sufficient condition for this is ∂_{P} f(x) = ∂_{C}f(x).

3. General results

In this section, we shall collect certain preparatory results, which are also of some independent interest. The following result complements Theorem 2.1.

Theorem 3.1. Let u ∉ X be such that proj_{X}(u) ≠ ϕ. Then the following hold:

(1) ∂^{P} d_{X}(u) ≠ ϕ.

(2) If ∂_{P} d_{X}(u) ≠ ϕ, then d_{X} is Fréchet differentiable at u and

∂_{P} d_{X}(u) = ∂^{P} d_{X}(u) = \{d′_{X}(u)\} = \{\frac{u − x}{d_{X}(u)}\} ,

where proj_{X}(u) = {x}.

Proof. Consider the function

f_{x}(w) := ∥w − x∥.

For 0 < δ < d_{X}(u), it is continuously differentiable on the ball u + δB, and there exists K > 0 such that for each x ∈ X, the mapping

w → f′_{x}(w) = \frac{w − x}{∥w − x∥}

is Lipschitz of rank K on u + δB. By the mean value theorem, for each x ∈ X and w ∈ u + δB,

f_{x}(w) − f_{x}(u) = ⟨f′_{x}(q), w − u⟩

for some q contained in the line segment (u, w). The Cauchy–Schwarz inequality now implies that for each such u and w one has

f_{x}(w) − f_{x}(u) ≤ ⟨f′_{x}(u), w − u⟩ + K∥w − u∥^{2}.

Let x̃ ∈ proj_{X}(u). Then for each w ∈ u + δB we have

d_{X}(w) − d_{X}(u) − K∥w − u∥^{2} ≤ ⟨f ′ ; x̃(u), w − u⟩,  (3.1)

and therefore f ′ ; x̃(u) ∈ ∂^{P} d_{X}(u). Now let ζ ∈ ∂_{P} d_{X}(u). Then there exist positive numbers σ and γ such that

d_{X}(w) − d_{X}(u) + σ∥w − u∥^{2} ≥ ⟨ζ, w − u⟩ ∀w ∈ u + γB,  (3.2)

where γ < δ. The inequalities (3.1) and (3.2) together imply that ζ = f ′ ; x̃(u) is the Fréchet derivative of d_{X} at u.

Remark 3.2. Since the P–subdifferential of the distance function is nonempty on a dense subset of H\X, Theorems 2.1 and 3.1 together yield the fact that d_{X} is Fréchet differentiable on a dense subset of H\X. In view of the Lipschitz nature of d_{X}, this conclusion by itself could also have been reached via Rademacher’s theorem in finite dimensions, or via a result of Preiss [15] in a setting more general than Hilbert space.

We shall have frequent occasion to employ the closed r–neighborhoods of X (r ≥ 0) defined via

X(r) := {u ∈ H : d_{X}(u) ≤ r}.

Two useful elmentary facts about X(r) are now summarized.

Lemma 3.3.

(1) Suppose that x ∈ proj_{X}(x + δζ), where δ > 0 and ∥ζ∥ = 1. Then

0 ≤ r ≤ s < δ ⟹ x + rζ ∈ proj_{X(r)}(x + sζ).

(2) Let ζ ∈ N_{X(r)}^{P}(u) and ∥ζ∥ = 1. Then there exists δ > 0 such that d_{X}(u + δζ) = r + δ.

Proof. Upon noting that x+rζ ∈ X(r), the first assertion will follow upon showing that x+rζ ∈ proj_{X(r)}(x+δζ). To this end, we only need to verify that d_{X(r)}(x+δζ) ≥ δ−r. To see this, observe that if d_{X(r)}(x+δζ) < δ−r, then d_{X}(x+δζ) < δ, violating d_{X}(x+δζ) = δ.

In order to prove the second assertion of the lemma, denote z = u + δζ, where δ > 0 is chosen small enough to ensure that d_{X(r)}(z) = ∥z − u∥ = δ. Then d_{X}(z) ≤ r + δ. Now consider any x ∈ X. One has d_{X}(x) = 0, and therefore the Intermediate Value Theorem implies that there exists a point y in the segment [x, z] such that d_{X}(y) = r; that is, y ∈ X(r). But then

∥z − x∥ = ∥y − x∥ + ∥z − y∥ ≥ r + δ,

since ∥y − x∥ ≥ r and ∥z − y∥ ≥ δ. Hence d_{X}(z) ≥ r + δ, and therefore equality holds.

Consider u ∈ H such that d_{X}(u) = r > 0, and suppose that ζ ∈ ∂_{P} d_{X}(u). Then the proximal subgradient inequality tells us that that there exist positive numbers σ and γ such that

d_{X}(w) − d_{X}(u) + σ∥w − u∥^{2} ≥ ⟨ζ, w − u⟩ ∀w ∈ u + γB,

and so

σ∥w − u∥^{2} ≥ ⟨ζ, w − u⟩ ∀w ∈ {u + γcl(B)} ∩ X(r).

Therefore ζ is a P–normal to the set {u + γcl(B)} ∩ X(r) at u, and therefore also ζ ∈ N_{X(r)}^{P}(u). Since ∥ζ∥ = 1, we have shown that

∂_{P} d_{X}(u) ⊆ N_{X(r)}^{P}(u) ∩ {ζ ∈ H : ∥ζ∥ = 1}.

The reverse containment is true as well, but does not follow as readily. This is taken up next.

Theorem 3.4. Suppose that d_{X}(u) = r > 0. Then

∂_{P} d_{X}(u) = N_{X(r)}^{P}(u) ∩ {ζ ∈ H : ∥ζ∥ = 1}.  (3.3)

Proof. In view of the preceding discussion, we only need to show that the right side of (3.3) is contained in the left. Suppose that ζ ∈ N_{X(r)}^{P}(u) and that ∥ζ∥ = 1. Then, by part 2 of Lemma 3.3, there exists δ > 0 such that

d_{X}(u + δζ) = r + δ  (3.4)

and

{y ∈ H : ∥y − u − δζ∥ < r + δ} ∩ X = ϕ.  (3.5)

F. H. Clarke, R. J. Stern, P. R. Wolenski / Proximal smoothness, lower–C^{2} property 125

Then since d_{X} has Lipschitz rank 1, for all u′ one has

d_{X}(u′) ≥ r + δ − ∥u′ − u − δζ∥.  (3.6)

Now, ζ ∈ ∂_{P} d_{X}(u) if and only if there exists σ > 0such that

d_{X}(u′) − ⟨ζ, u′ − u⟩ + σ∥u′ − u∥^{2} ≥ d_{X}(u) = r  (3.7)

for all u′ near u. From (3.6) it then follows that (3.7) holds provided that

δ + σ∥u′ − u∥^{2} ≥ ⟨ζ, u′ − u⟩ + ∥u′ − u − δζ∥  (3.8)

for all u′ sufficiently near u. Now let

\begin{aligned}a & := ∥u′ − u∥ \\ b & := ∥u′ − u − δζ∥ \\ θ & := arccos (\frac{⟨ζ, u′ − u⟩}{∥u′ − u∥}) . \end{aligned}

Then (3.8) is equivalent to

δ + σa^{2} ≥ a cos(θ) + b.  (3.9)

By the law of cosines,

b^{2} = a^{2} + δ^{2} − 2δa cos(θ),

and so

a cos(θ) = \frac{a^{2} + δ^{2} − b^{2}}{2δ} .  (3.10)

First suppose that δ ≤ b. Then (3.10) implies

\begin{aligned}a cos(θ) & = \frac{a^{2}}{2δ} + \frac{(δ + b)(δ − b)}{2δ} \\ & ≤ \frac{a^{2}}{2δ} + δ − b. \end{aligned}

From this it follows that (3.9) holds with σ = \frac{1}{2δ}. Now suppose that δ > b. Then (3.10) implies that cos(θ) ≥ 0 and

\frac{2δ}{δ + b}a cos(θ) = \frac{a^{2}}{δ + b} + δ − b.  (3.11)

Since

\frac{2δ}{δ + b} ≥ 1,

we have

a cos(θ) + b ≤ \frac{2δ}{δ + b}a cos(θ) + b

= \frac{a^{2}}{δ + b} + δ

≤ \frac{a^{2}}{δ} + δ,

which is (3.9) with σ = \frac{1}{δ}.

In view of part 1 of Lemma 3.3, we have the following.

Corollary 3.5. Let ζ ∈ N_{X}^{P}(x) and ∥ζ∥ = 1. Then

∂_{P} d_{X}(x + rζ) = {ζ} ∀r ∈ (0, 1].

We shall also require the following result.

Proposition 3.6.

(1) Suppose that u ∉ X, proj_{X}(u) ≠ ϕ, and that d_{X} is Gâteaux differentiable at u. Then ∥d′_{X}(u)∥ = 1.

(2) Let u ∉ X, and d_{X} be continuously differentiable at u. Then u admits a unique closest point x ∈ X, and

d′_{X}(u) = \frac{u − x}{d_{X}(u)}.

Proof. In order to prove part 1, let x ∈ X be a closest point to u, and let v = x − u. Then for small positive t one has d_{X}(u + tv) = (1 − t)d_{X}(u). Consequently

d′_{X}(u; v) = lim_{t↓0} \frac{(1 − t)d_{X}(u) − d_{X}(u)}{t}

= lim_{t↓0} \frac{−td_{X}(u)}{t}

= −d_{X}(u) = −∥x − u∥ = ⟨d′_{X}(u), x − u⟩.

Since the distance function is Lipschitz of rank 1, we have ∥d′_{X}(u)∥ ≤ 1. The Cauchy– Schwarz inequality therefore implies ∥d′_{X}(u)∥ = 1.

We now turn to part 2. The continuous differentiability assumption implies strict differentiablity at u; that is ∂_{L}d_{X}(u) = {d′_{X}(u)}. Then d′_{X}(u) is the weak limit of a sequence ζ_{i} such that ∂_{P} d(u_{i}) = {ζ_{i}}, where u_{i} → u. But since Theorem 3.1 implies that ζ_{i} = d′_{X}(u_{i}) and d′_{X} is continuous, it follows that d′_{X}(u) is actually the strong limit of ζ_{i}. Now note that

ζ_{i} = \frac{u_{i} − x_{i}}{d_{X}(u_{i})} ,

where proj_{X}(u_{i}) = {x_{i}}. We then have

x := u − d_{X}(u)d′_{X}(u) = lim x_{i}

and

d′_{X}(u) = \frac{u − x}{d_{X}(u)}.

Since the norm of this expression is 1 and x ∈ X, it follows that x ∈ proj_{X}(u). It remains to show that this x is the unique element in proj_{X}(u). Suppose that x′ ∈ proj_{X}(u). Denote

u_{δ} := u − δ \frac{u − x′}{d_{X}(u)}.

Then

x′ ∈ proj_{X}(u_{δ}) ∀δ ∈ (0, d_{X}(u)).

It follows that

\frac{u − x′}{d_{X}(u)} ∈ N_{X(d_{X}(u)−δ)}^{P}(u_{δ}).

Then by Theorem 3.4,

\{\frac{u − x′}{d_{X}(u)}\} = ∂_{P} d_{X}(u_{δ}) = \{d′_{X}(u_{δ)}\}.

Now letting δ ↓ 0, continuity of the derivative implies

d′_{X}(u) = \frac{u − x′}{d_{X}(u)};

that is, x′ = x.

For any u ∉ X, we have

−d_{X}(u) = sup{−∥u − x∥ : x ∈ X},

and therefore, near u, the negative of the distance function is the pointwise supremum of a family of C^{1} functions parametrized by x. However, attainment is not guaranteed (unless weak closedness of X or finite dimensionality of H is assumed). For this reason, known results on pointwise maximum functions (see Clarke [8], [5]) are not directly applicable in order to prove regularity of −d_{X} on H\X. However, the special nature of the distance function allows for an independent proof. This, and a bit more, is given in the next result.

Theorem 3.7. Let u ∉ X. Then the following hold:

(1) −d_{X} is regular at u.

(2) d_{X} is regular at u if and only if d_{X} is strictly differentiable at u.

Proof. Let ζ ∈ ∂_{L}d_{X}(u). Then there exist sequences u_{i} and ζ_{i} such that u_{i} → u, ζ_{i} →^{w} ζ, and

∂_{P} d_{X}(u_{i}) = \{ζ_{i}\} = \{\frac{u_{i} − x_{i}}{d_{X}(u_{i})} \} ,

where proj_{X}(u_{i}) = {x_{i}}. Now, for any v ∈ H,

d_{X}(u_{i} + tv) − d_{X}(u_{i}) ≤ ∥u_{i} + tv − x_{i}∥ − ∥u_{i} − x_{i}∥

= \frac{∥u_{i} + tv − x_{i}∥^{2} − ∥u_{i} − x_{i}∥^{2}}{∥u_{i} + tv − x_{i}∥ + ∥u_{i} − x_{i}∥}

= \frac{2t⟨u_{i} − x_{i}, v⟩ + t^{2}∥v∥^{2}}{∥u_{i} + tv − x_{i}∥ + ∥u_{i} − x_{i}∥}.

Therefore

lim sup_{t↓0} \frac{d_{X}(u + tv) − d_{X}(u)}{t} = lim sup_{t↓0} [lim \frac{d_{X}(u_{i} + tv) − d_{X}(u_{i})}{t}]

≤ lim sup_{t↓0} [lim \frac{2⟨u_{i} − x_{i}, v⟩ + t∥v∥^{2}}{∥u_{i} + tv − x_{i}∥ + ∥u_{i} − x_{i}∥}]

= ⟨ζ, v⟩.

Since the C–subdifferential satisfies

∂_{C}d_{X}(u) = clco[∂_{L}d_{X}(u)] = −∂_{C}(−d_{X}) = (u),

it follows from the preceding that for all v ∈ H,

lim inf_{t↓0} \frac{−d_{X}(u + tv) + d_{X}(u)}{t} ≥ sup\{⟨−ζ, v⟩ : ζ ∈ ∂_{L}(d_{X})(u)\}

= max{⟨−ζ, v⟩ : ζ ∈ ∂_{C}(d_{X})(u)} = max{⟨ζ, v⟩ : ζ ∈ ∂_{C}(−d_{X})(u)} = (−d_{X})^{o}(u; v)

= lim sup_{w→u^{t↓0}} \frac{−d_{X}(w + tv) + d_{X}(w)}{t}

≥ lim sup_{t↓0} \frac{−d_{X}(u + tv) + d_{X}(u)}{t}.

From this we obtain

(−d_{X})^{o}(u; v) = lim_{t↓0} \frac{−d_{X}(u + tv) + d_{X}(u)}{t},

which verifies the regularity of −d_{X} at u. As for the second part of the theorem’s statement, we first recall that strict differentiability of d_{X} at u implies regularity. Now suppose that both d_{X} and −d_{X} are regular at u, and let ζ ∈ ∂_{C}d_{X}(u). Then for all v ∈ H one has

⟨ζ, v⟩ ≤ d_{X}^{o}(u; v) = d′_{X}(u; v).

Since also −ζ ∈ ∂_{C}(−d_{X})(u), we have

⟨−ζ, v⟩ ≤ (−d_{X})^{o}(u; v) = −d′_{X}(u; v).

It follows that

⟨ζ, v⟩ = d_{X}^{o}(u; v) ∀v ∈ H,

which implies that ∂_{C}d_{X}(u) is the singleton {ζ}.

4. Proximally smooth sets

It is our primary aim in the present section to characterize when a closed set X ⊆ H is proximally smooth; that is, when there exists r > 0 such that the distance function is continuously differentiable on a “tube” of the form

U(r) := {u ∈ H : 0 < d_{X}(u) < r}.

Let us note at the outset that it is possible for a closed nonconvex set to be proximally smooth, and that continuous differentiability of the distance function on the tube U(r) does not imply the property on U(r′) for r′ > r; both phenomena are easily illustrated by examples involving C^{2} manifolds in finite dimensions.

The following is our main result characterizing proximal smoothness. Among other facts, it asserts the following one: X ⊆ H is proximally smooth if and only if the P– subdifferential ∂_{P} d_{X}(u) is nonempty for each u ∈ U(r). We shall denote

Y (r) := {u ∈ H : d_{X}(u) ≥ r}.

Theorem 4.1. For given r > 0, the following are equivalent:

(a) d_{X} is continuously differentiable on U(r).

(b) proj_{X}(u) ≠ ϕ ∀u ∈ U(r) and the Gâteaux derivative d′_{X}(u) exists.

(c) proj_{X}(u) ≠ ϕ ∀u ∈ U(r), and for every r′ ∈ (0, r), one has

d_{X}(u) + d_{Y (r′)}(u) = r′ ∀u ∈ U(r′).

(d) proj_{X}(u) ≠ ϕ ∀u ∈ U(r), and every nonzero P–normal to X is realized by an r-ball.

(e) For every r′ ∈ (0, r) and u ∈ H such that d_{X}(u) = r′, one has N_{X(r′)}^{P}(u) ≠ {0}.

(f) ∂_{P} d_{X}(u) ≠ ϕ ∀u ∈ U(r).

Remark 4.2.

(1) U(r) = ϕ if and only if X = H, in which case all the statements are vacuously true; consequently H is proximally smooth.

(2) Since the distance function to the empty set is identically +∞ by convention, the formula in part (c) implies that Y (r′) ≠ ϕ if X is a proximally smooth proper subset of H.

Proof of the theorem:

(a) ⟹ (b):

This follows from part 2 of Proposition 3.6.

(b) ⟹ (c):

By (b), proj_{X}(u) ≠ ϕ for every u ∈ U(r). It remains to show that for any given r′ ∈ (0, r),

d_{X}(u) + d_{Y (r′)}(u) = r′ ∀u ∈ U(r′).  (4.1)

Fix r′ ∈ (0, r) and let u ∈ U(r′). We first claim that

d_{X}(u) + d_{Y (r′)}(u) ≥ r′.  (4.2)

For this purpose, we can without loss of generality assume that u admits a closest point in Y (r′), since this is so for a dense set of u in U(r′). Let y ∈ proj_{Y (r′)}(u). Then, if x is a closest point in X to u,

r′ = d_{X}(y) ≤ ∥y − x∥ ≤ ∥u − x∥ + ∥y − u∥ = d_{X}(u) + d_{Y (r′)}(u),

which gives (4.2).

We now must show that

d_{X}(u) + d_{Y (r′)}(u) ≤ r′ ∀r′ ∈ (0, r).  (4.3)

Introduce the function

V (α) := d_{Y (α)}(u), 0 < α < r.

It is useful to express V as a value function:

V (α) = \{ \begin{matrix}inf\{∥u − z∥ : d_{X}(z) ≥ α\} & if Y (α) ≠ ϕ \\ +∞ & otherwise \end{matrix} \} , 0 < α < r.  (4.4)

Claim 4.3. V is finite, nondecreasing, and Lipschitz of rank 1 on (0, r).

The nondecreasing property is immediate. Prior to proving the rest of the claim, let us observe that it implies (4.3) holds. Indeed, Claim 4.3 implies that for any r′ ∈ (0, r), we have

V (r′) − V (d_{X}(u)) ≤ r′ − d_{X}(u).

Then, since V (r′) = d_{Y (r′)}(u) and V (d_{X}(u)) = 0, (4.3) immediately follows. By part 1 of Proposition 3.6, ∥d′_{X}(u)∥ = 1. Denoting ζ = d′_{X}(u), one has

\begin{aligned}d_{X}(u + tζ) & = d_{X}(u) + ⟨ζ, tζ⟩ + o(t) \\ & = d_{X}(u) + t + o(t). \end{aligned}

Therefore for any sufficiently small ε > 0, there exists a point z_{ε} such that ∥z_{ε} − u∥ < 2ε and d_{X}(z_{ε}) > d_{X}(u) + ε. From this it follows that

V (d_{X}(u) + ε) < 2ε,

and therefore

lim_{α↓d_{X}(u)} V (α) = 0.  (4.5)

Since V (α) = 0 on (0, d_{X}(u)], (4.5) implies that proving Claim 4.3 reduces to verifying the following.

Claim 4.4. V is Lipschitz of rank 1 on (d_{X}(u), r).

Let us first make note of the fact that

V (α) = inf{∥u − z∥ : d_{X}(z) = α} ∀α ∈ (d_{X}(u), r).  (4.6)

To see this, consider a point z such that d_{X}(z) > α > d_{X}(u). Then there exists a point y in the segment (u, z) such that d_{X}(y) = α. Since ∥u − y∥ < ∥u − z∥, it follows that points z such that d_{X}(z) > α can be discarded in the definition of V given by (4.4), for α in the interval (d_{X}(u), r). This verifies (4.6).

For α ∈ (d_{X}(u), r), consider the lower semicontinuous function defined by

W (α) := lim_{α′↑α} V (α′).

In order to prove Claim 4.4, it suffices to show that W is Lipschitz of rank 1 on (d_{X}(u), r). Let ζ ∈ ∂_{P} W (α_{o}), where α_{o} ∈ (d_{X}(u), r). Note that since W is nondecreasing. Then, referring to [7], it follows that ζ ≥ 0, a fact required below. By another result in [7], the required Lipschitz behavior of W will follow upon verifying that ∥ζ∥ ≤ 1.

In view of the proximal subgradient inequality, there exist positive numbers σ and γ such that

W (α) − W (α_{o}) + σ(α − α_{o})^{2} ≥ ζ(α − α_{o})  (4.7)

whenever |α − α_{o}| < γ. Then, since V (α) ≥ W (α) on (d_{X}(u), r), for points z such that d_{X}(z) = α ∈ (d_{X}(u), r), one has

∥u − z∥ + σ(d_{X}(z) − α_{o})^{2} − ζd_{X}(z) ≥ W (α_{o}) − ζα_{o}  (4.8)

if |d_{X}(z) − α_{o}| < γ. Now let ε ∈ (0, \frac{γ}{2}), and choose z_{o} to satisfy 0 < α_{o} − d_{X}(z_{o}) < ε and |∥u − z_{o}∥ − W (α_{o})| < ε. Then, if |d_{X}(z) − d_{X}(z_{o})| < \frac{γ}{2}, we have |d_{X}(z) − α_{o}| < γ. Bearing in mind that ζ ≥ 0, we have ∥u − z∥ + σ(d_{X}(z) − d_{X}(z_{o})^{2} − ζd_{X}(z)

= ∥u − z∥ + σ(d_{X}(z) − α_{o})^{2} − ζd_{X}(z) + σ[(d_{X}(z) − d_{X}(z_{o}))^{2} − (d_{X}(z) − α_{o})^{2}]

≥ W (α_{o}) − ζα_{o} + σ[(d_{X}(z) − d_{X}(z_{o}))^{2} − (d_{X}(z) − α_{o})^{2}]

≥ ∥u − z_{o}∥ − ζd_{X}(z_{o}) − ε + ζ(d_{X}(z_{o}) − α_{o}) + σ[(d_{X}(z) − d_{X}(z_{o}))^{2} − (d_{X}(z) − α_{o})^{2}] ≥ ∥u − z_{o}∥ − ζd_{X}(z_{o}) − ε − εζ,

where in the last inequality we used the fact that

(d_{X}(z) − d_{X}(z_{o}))^{2} − (d_{X}(z) − α_{o})^{2} ≥ 0,

as a straightforward calculation shows. Let us denote δ := ε + εζ. Then z_{o} is δ–optimal for minimizing the function

z ⟶ ∥u − z∥ + σ(d_{X}(z) − d_{X}(z_{o}))^{2} − ζd_{X}(z)

over the set

S := \{z ∈ H : ∥z − z_{o}∥ ≤ \frac{γ}{2} \},

since

z ∈ S ⟹ |d_{X}(z) − d_{X}(z_{o})| ≤ \frac{γ}{2} .

By virtue of Ekeland’s Theorem ([10], [5]), there exists z′ such that ∥z′ − z_{o}∥ < \sqrt{δ} and such that z′ minimizes the function

h(z) := ∥u − z∥ + σ(d_{X}(z) − d_{X}(z_{o}))^{2} − ζd_{X}(z) + \sqrt{δ}∥z − z′∥

over S. We may choose ε sufficiently small to ensure that z′ is in the interior of S; that is, such that \sqrt{δ} < \frac{γ}{2}. Then a necessary condition for optimality of z′ is

0 ∈ ∂_{C}h(z′).

The calculus of the C–subdifferential ([5]) then yields

0 = w_{1} + 2σ\sqrt{δ}d′_{X}(z′) − ζd′_{X}(z′) + \sqrt{δ}w_{2},

where ∥w_{i}∥ ≤ 1, i = 1, 2. Since ∥d′_{X}(u)∥ = 1 (by part 1 of Proposition 3.6) and δ is arbitrarily small, we conclude that ∥ζ∥ ≤ 1, as required.

(c) ⟹ (d):

In view of formula (2.1), it suffices to show that if r′ ∈ (0, r), then every nonzero P–normal to X is realized by an r′–ball. Fix r′ ∈ (0, r), let x ∈ X, ζ ∈ N_{X}^{P}(x), and ∥ζ∥ = 1. Then there exists δ ∈ (0, r′) such that

proj_{X}(x + r′′ζ) = {x} ∀r′′ ∈ (0, δ).

For any r′′ ∈ (0, δ), part 1 of Lemma 3.3 implies that

x + r′′ζ ∈ proj_{X(r′′)}(x + δζ).

Therefore

ζ ∈ N_{X(r′′)}^{P}(x + r′′ζ).

In view of Theorem 3.4, we have ∂_{P} d_{X}(x + r′′ζ) = {ζ} =. Then Theorem 3.1 implies that

∂_{P} d_{X}(x + r′′ζ) = ∂^{P} d_{X}(x + r′′ζ) = {ζ}.

Since the formula in (c) is an identity in u (locally), we obtain

∂_{P} d_{Y (r′)}(x + r′′ζ) = {−ζ},

and so proj_{Y (r′)} = x+r′′ζ+αζ for some α >= 0. But since (c) holds and d_{X}(x+r′′ζ) = r′′, it follows that α == r′ − r′′, and therefore x + r′ζ is in the boundary of Y (r′). Hence d_{X}(x + r′ζ) = r′, which shows that ζ is realized by an r′–ball.

(d) ⟹ (e):

Suppose that d_{X}(u) = r′ where 0 < r′ < r, and let x ∈ proj_{X}(u). Then

ζ := \frac{u − x}{r′} ∈ N_{X}^{P}(x),

and ∥ζ∥ = 1. Hence (d) implies that

proj_{X}(u + δζ) = {x} ∀δ ∈ (0, r − r′).

Therefore part 1 of Lemma 3.3 gives

u ∈ proj_{X(r′)}(u + δζ) ∀δ ∈ (0, r − r′),

and so N_{X(r′)}^{P}(u) ≠ {0}, as required.

(e) ⟹ (f):

This follows immediately from Theorem 3.4.

(f) ⟹ (a):

By Theorems 2.1 and 3.1, for any u ∈ U(r), one has

∂_{P} d_{X}(u) = \{d′_{X}(u)\} = \{\frac{u − x}{d_{X}(u)}\} ,

where now d′_{X} denotes the Fréchet derivative. The required continuity of the derivative follows from part 2 of Theorem 2.1. This completes the proof of the theorem.

Remark 4.5. Note that if X is weakly closed, as when H = R^{n}, then in conditions (b)–(d), the requirement that proj_{X}(u) be nonempty is automatically satisfied.

When the conditions of Theorem 4.1 hold for a given r, we shall say that X is proximally smooth of radius r. If X is convex, then it is weakly closed, and it follows that proj_{X}(u) ≠ ϕ for all u. Furthermore, classical normals coincide with P–normals, and so (2.1) holds with 0 left hand side for every x ∈ X, and therefore for every r > 0. Hence X is proximally smooth of radius r for every r > 0. The following corollary asserts the converse.

Corollary 4.6. A closed set X ⊆ H is convex if and only if it is proximally smooth of radius r for every r > 0.

Proof. The “only if” part has already been explained, so let us assume that X is proximally smooth for every r > 0. Let u ∉ X. The proximal smoothness assumption implies that u admits a closest point in X, say x =. Furthermore, for every r > 0, we have

\frac{1}{2r}∥y − x∥^{2} ≥ ⟨\frac{ζ}{∥ζ∥}, y − x⟩ ∀y ∈ X,

where ζ := u − x. But then

0 ≥ ⟨ζ, y − x⟩ ∀y ∈ X.

Since ⟨ζ, u − x⟩ > 0, we have shown that for each point u ∉ X, there exists a hyperplane separating u from X. This is equivalent to convexity of X.

A further result in the same vein is the following. It follows directly from Corollary 4.6 and Theorem 4.1.

Corollary 4.7. A closed set X ⊆ H is convex if and only if it satisfies the following two conditions for every u ∈ H\X:

(1) proj_{X}(u) ≠ ϕ.

(2) The Gâteaux derivative d′_{X}(u) exists.

The next result asserts that proximal smoothness of a closed set X ⊆ H implies Lipschitz behavior of both the (necessarily single valued) metric projection proj_{X} and the (Fréchet = Gâteaux) derivative d′_{X} near X. In particular, the distance function to a closed set X has the feature that continuity of d′_{X} on a tube U(r) implies that d′_{X} must in fact be locally Lipschitz on U(r).

Theorem 4.8. Let X be proximally smooth, with r > 0 as in Theorem 4.1. Then the following hold:

(1) Let r′ ∈ (0, r). Then proj_{X} is Lipschitz of rank \frac{r}{r−r′} on U(r′).

(2) For every u and w in U(r) one has

⟨u − w, proj_{X}(u) − proj_{X}(w)⟩ ≥ 0.  (4.9)

(3) d′_{X} is locally Lipschitz on U(r).

Proof. Let u and w be points in the tube U(r′). Then

⟨\frac{u − proj_{X}(u)}{d_{X}(u)}, proj_{X}(w) − proj_{X}(u)⟩ ≤ \frac{1}{2r}∥proj_{X}(w) − proj_{X}(u)∥^{2}  (4.10)

and

⟨\frac{w − proj_{X}(w)}{d_{X}(w)}, proj_{X}(u) − proj_{X}(w)⟩ ≤ \frac{1}{2r}∥proj_{X}(w) − proj_{X}(u)∥^{2}.  (4.11)

Since d_{X}(u) ≤ r′ and d_{X}(w) ≤ r′, (4.10) and (4.11) yield

⟨u − proj_{X}(u), proj_{X}(w) − proj_{X}(u)⟩ ≤ \frac{r′}{2r}∥proj_{X}(w) − proj_{X}(u)∥^{2}  (4.12)

and

⟨proj_{X}(w) − w, proj_{X}(w) − proj_{X}(u)⟩ ≤ \frac{r′}{2r}∥proj_{X}(w) − proj_{X}(u)∥^{2},  (4.13)

respectively. Upon adding the inequalities (4.12) and (4.13), we obtain

⟨u − w + proj_{X}(w) − proj_{X}(u), proj_{X}(w) − proj_{X}(u)⟩ ≤ \frac{r′}{r} ∥proj_{X}(w) − proj_{X}(u)∥^{2},

and therefore

⟨u − w, proj_{X}(w) − proj_{X}(u)⟩ ≤ \frac{r′ − r}{r}∥proj_{X}(w) − proj_{X}(u)∥^{2}.  (4.14)

Consequently,

∥proj_{X}(w) − proj_{X}(u)∥^{2} ≤ \frac{r}{r − r′} ⟨w − u, proj_{X}(w) − proj_{X}(u)⟩.

An application of the Cauchy–Schwarz inequality then yields

∥proj_{X}(w) − proj_{X}(u)∥ ≤ \frac{r}{r − r′} ∥w − u∥.  (4.15)

Since u and w were arbitrary points in U(r′), part 1 of the assertion follows. Part 2 is a consequence of (4.14), while part 3 follows readily from part 1 and the fact that the formula

d′_{X}(u) = \frac{u − proj_{X}(u)}{d_{X}(u)}

holds for every u ∈ U(r).

Remark 4.9. The above results have some bearing on the issue of extending a multifunction defined on X and which is Lipschitz there (in the Hausdorff sense), beyond X. In the single–valued case, this is well understood; global extensions exist and require no smoothness properties of X, even in infinite dimensions; see Hiriart–Urruty [11]. The multivalued case is more delicate, however. When X is proximally smooth, a local extension to X(r′) is provided by F̃ (u) = F (proj_{X}(u)), in view of Theorem 4.8; furthermore, the extension has Lipschitz rank arbitrarily close to that of F on X, depending upon how small we choose r′. Responding to a conjecture of the authors, Azé and Horvath have recently shown that in finite dimensions, global Lipschitz extensions do exist [1], but whose ranks increase as a function of the dimension; the infinite dimensional case remains unsettled.

In Theorem 4.8, if X is additionally assumed to be convex, then r may be taken arbitrarily large, and (4.10), (4.11) hold with 0 on the right hand sides. We then readily obtain the following.

Corollary 4.10. Let X be a closed and convex subset of H. Then on H, proj_{X} is Lipschitz of rank 1, (4.9) holds, and d′_{X} is locally Lipschitz.

The consequences of Theorem 4.1 can be strengthened under the additional hypothesis that X be weakly closed.

Theorem 4.11. Assume that X is weakly closed and let r > 0. Then conditions (a)–(f) of Theorem 4.1 are equivalent to

(g) proj_{X}(u) is a singleton for every u ∈ U(r).

Proof. Since the other conditions imply (g), we only need to prove that (g) implies (a). To this end, we shall posit (g), and show that d_{X} has a continuously varying strict derivative.

Given u ∈ U(r), let ζ ∈ ∂_{L}d_{X}(u). Then

\frac{u_{i} − x_{i}}{d_{X}(u_{i})} ⟶^{w} ζ,  (4.16)

where u_{i} is a sequence in X converging to u, and x_{i} is the unique closest point in X to u_{i}. The weak closedness of X then implies that

x_{i} ⟶^{w} x := u − d_{X}(u)ζ ∈ X,  (4.17)

and so

ζ = \frac{u − x}{d_{X}(u)}.  (4.18)

Since (4.16) implies ∥ζ∥ ≤ 1, we conclude that x ∈ proj_{X}(u). Since this x is unique, it follows that ζ is the sole element in ∂_{L}d_{X}(u). Since u ∈ U(r) was arbitrary, d_{X} is strictly differentiable on U(r). We denote this derivative by d′_{X}. Letting u_{i} be a sequence in U(r) such that u_{i} → u ∈ U(r), we wish to show that d′_{X}(u_{i}) → d′_{X}(u). We have that for each i,

d′_{X}(u_{i}) = \frac{u_{i} − x_{i}}{d_{X}(u_{i})} ,

where proj_{X}(u_{i}) = {x_{i}}. Likewise,

d′_{X}(u) = \frac{u − x}{d_{X}(u)},

where proj_{X}(u) = {x}. Therefore we need to show that x_{i} → x. In fact, it is enough to show that x_{i} →^{w} x, for then we would have

\frac{u_{i} − x_{i}}{d_{X}(u_{i})} ⟶^{w} \frac{u − x}{d_{X}(u)},

and since both sides of this expression are of norm 1, it would follow that the convergence is strong, implying x_{i} converges to x strongly as well, as required. Now, by way of contradiction, suppose that x was not the weak limit of x_{i}. Since this sequence is norm bounded, by Alaoglu’s theorem there exists a subsequence so that x_{i′} →^{w} x̂ ≠ x, where x̂ ∈ X by the weak closedness assumption. But since

\frac{u_{i′} − x_{i′}}{d_{X}(u_{i′})} ⟶^{w} \frac{u − x̂}{d_{X}(u)}

and each term on the left is of norm 1, we have

∥\frac{u − x̂}{d_{X}(u)}∥ ≤ 1,

and so the norm in fact equals 1. Consequently x̂ ∈ proj_{X}(u), which violates the uniqueness of x as the closest point in X to u.

In a similar spirit to Corollary 4.6, we then have the following result.

Corollary 4.12. A weakly closed set X ⊆ H is convex if and only if proj_{X}(u) = is a singleton for every u ∉ X.

Remark 4.13.

(1) A longstanding conjecture (still open to our knowledge) would assert the statement of Corollary 4.12 with the a priori assumption of weak closedness replaced by strong closedness.

(2) Theorems 4.8 and 4.11 together imply that if X ⊆ H is weakly closed, then the metric projection proj_{X} is single valued on U(r) if and only if it is Lipschitz on U(r′) for any r′ ∈ (0, r), with the Lipschitz rank being \frac{r}{r−r′}.

(3) It is interesting to note that it is possible, even in finite dimensions, for a point u ∉ X to have a unique closest point in X, while ∂_{P} d_{X}(u) = ϕ. Let X = epi(f) where f : R → R is given by

f(x) = \sqrt{1 − x^{2}} − 1 + x^{6}.

The point (0, −1) admits the origin as a unique closest point in X. However, every point of the form (0, −y) with y > 1 admits multiple closest points. Consequently, N_{X(1)}^{P}(0, −1) = {0}, and Theorem 3.4 implies that ∂_{P} d_{X}(0, −1) = ϕ.

We now specialize still further, to the finite dimensional case.

Corollary 4.14. Suppose that H = R^{n}and let r > 0. Then conditions (a)–(g) in Theorems 4.1, 4.11 are equivalent to each of the following:

(h) The Gâteaux derivative d′_{X}(u) exists for each u ∈ U(r).

(i) d_{X} is strictly differentiable on U(r).

(j) d_{X} is regular on U(r).

Proof. The equivalence of (g),(h) and (i) follows readily from results in Clarke [8]; see also Chapter 2 of Clarke [5]. Then the equivalence of (j) to these conditions follows from Theorem 3.7.

Some geometric consequences of proximal smoothness in finite dimensions are summarized in the next corollary.

Corollary 4.15. Let H = R^{n} and assume that r > 0 is such that the equivalent conditions (a)–(f) hold. Then the following hold:

(1) For every x ∈ X, one has

N_{X}^{P}(x) = N_{X}^{L}(x) = N_{X}^{C}(x).

(2) For each r′ ∈ (0, r) and each u such that d_{X}(u) = r′, one has

N_{X(r′)}^{P}(u) = N_{X(r′)}^{L}(u) = N_{X(r′)}^{C}(u) = {α(u − x) : α ≥ 0},

where x is the unique closest point to u in X.

(3) X is regular, as is each set X(r′) for 0 < r′ < r.

(4) For each r′ ∈ (0, r), the boundary of X(r′) is a C^{1}–manifold.

Proof. Part 1 will follow upon verifying that N_{X}^{L}(x) ⊆ N_{X}^{P}(x) for each x ∈ bdry(X). To this end, let us assume that 0 ≠ ζ ∈ N_{X}^{L}(x) for a boundary point x. Then for a sequence of boundary points x_{i} → x there is a corresponding sequence ζ_{i} ∈ N_{X}^{P}(x_{i}) such that ζ_{i} → ζ. In view of (2.1), for each i we have

\frac{1}{2r} ∥y − x_{i}∥^{2} ≥ ⟨\frac{ζ_{i}}{∥ζ_{i}∥}, y − x_{i}⟩ ∀y ∈ X.

Then

\frac{1}{2r} ∥y − x∥^{2} ≥ ⟨\frac{ζ}{∥ζ∥}, y − x_{i}⟩ ∀y ∈ X,

which shows that ζ ∈ N_{X}^{P}(x).

In order to verify part 2, first note that in view of condition (d) of Theorem 4.1, part 1 of Lemma 3.3 implies that for each r′ ∈ (0, r), every nonzero P–normal to X(r′) is realized by an (r − r′)–ball. Hence each X(r′) is itself proximally smooth, and so part 1 and Theorem 2.1 yield part 2 of the assertion. Part 3 follows from parts 1 and 2, while. Part 4 follows from condition (a) of Theorem 4.1 (continuous differentiability of d_{X} on U(r)) and the fact that on U(r), ∥d′_{X}(u)∥ = 1 (by part 1 of Proposition 3.6).

Remark 4.16. Suppose that H = R^{n}.

(1) Part 1 of the preceding corollary implies that if X is proximally smooth, then

N_{X}^{P}(x) ≠ {0} ∀x ∈ bdry(X),  (4.19)

since the C–normal cone to a boundary point of a closed subset of R^{n} is always nonzero. (In a general Hilbert space setting, however, one can have N_{X}^{P}(x) = {0} for a boundary point x, even for closed and convex X.)

(2) In general, the C–normal cone is not a closed multifunction, unless one makes extra hypotheses on X. One such condition is that X be epi–Lipschitz; that is, locally, X is the image under an isometry of the epigraph of a Lipschitz function. (See Rockafellar [17] and section 7.3 of Clarke [5].) The preceding corollary shows that a different condition implying the closedness of the multifunction N_{X}^{C}—and N_{X}^{P} too—is that X be proximally smooth; this is a consequence of the closedness of the multifunction N_{X}^{L}. Let us note, however, that (4.19) alone does not guarantee the P–normal cone mapping’s closedness. Consider for example X = epi(f) for the function f : R → R given by

f(x) = \{ \begin{matrix}−|x|^{3/2} & if x < 0 \\ x & if x ≥ 0 \end{matrix}

Here (4.19) holds, but one can readily confirm that N_{X}^{P}(0, 0) is not closed.

(3) The following example shows that closedness of the multifunction N_{X}^{P} is not sufficient for proximal smoothness of an epi–Lipschitz set X. Choose sequences r_{n} and x_{n} such that r_{n} > 0, r_{n} ↓ 0, x_{n} ∈ (0, 1), and such that the intervals (x_{n} − r_{n}, x_{n} + r_{n}) are all disjoint and contained in (0, 1). Then set

a_{n} := \frac{ε_{n}r_{n}}{\sqrt{1 + ε_{n}^{2}}} ,

where ε_{n} > 0 and ε_{n} ↓ 0. The intervals (x_{n}−a_{n}, x_{n}+a_{n}) are all disjoint and contained in (0, 1) too. Now take X ⊆ R^{2} to be the epigraph of the following function:

f(x) = \{ \begin{matrix}\sqrt{r_{n}^{2} − (x − x_{n})^{2}} − \sqrt{r_{n}^{2} − a_{n}^{2}} & if ∥x − x_{n}∥ ≤ a_{n} \\ 0 & otherwise \end{matrix}

Then in (x_{n} − a_{n}, x_{n} + a_{n}), we have

f′(x) = \frac{−(x − x_{n})}{\sqrt{r_{n}^{2} − (x − x_{n})^{2}}} .

Hence |f′(x)| ≤ ε_{n} whenever |x − x_{n}| ≤ a_{n}, implying that f is Lipschitz. Then, upon noting that

N_{X}^{P}(0, 0) = {(0, y) : y ≤ 0},

it is readily checked that the multifunction N_{X}^{P} is closed. However, X is not proximally smooth, since near the origin, the circles employed in the construction have arbitrarily small radii.

5. Connection to the lower–C^{2} property for Lipschitz functions

In this section we continue to assume that H = R^{n}. Let us introduce a basic hypothesis:

(A) (a) U ⊆ R^{n} is open, convex and bounded.
(b) f : U → R is Lipschitz.

Under these assumptions, we shall say that f is lower–C^{2} on U provided that there exist σ > 0, a compact set S (in some topological space V) and continuous functions b : S → R^{n}, c : S → R, such that

f(x) = max_{s∈S} {−σ∥x∥^{2} + ⟨b(s), x⟩ + c(s)} ∀x ∈ U.  (5.1)

In this case we shall also say that f is σ–lower–C^{2} on U. This is in fact a local form of the lower–C^{2} property, as can be seen from the proof of Theorem 6 in Rockafellar [17], who investigated this class of functions as one having favorable properties for optimization. The following characterization is required as well; it leads to the connection between the lower–C^{2} property and proximal smoothness.

Theorem 5.1. Let hypothesis (A) hold. Then the following are equivalent for a given σ > 0:

(a) f is σ–lower–C^{2} on U.

(b) For each x ∈ U, there exists ζ ∈ R^{n} such that

f(y) ≥ −σ∥y − x∥^{2} + ⟨ζ, y − x⟩ + f(x) ∀y ∈ U.  (5.2)

(c) For each x ∈ U, (5.2) holds for all ζ ∈ ∂_{P} f(x).

Proof.

(a) ⟹ (b):

Let x ∈ U, and let ŝ ∈ S be such that

f(x) = −σ∥x∥^{2} + ⟨b(ŝ), x⟩ + c(ŝ).  (5.3)

Since

f(y) ≥ −σ∥y∥^{2} + ⟨b(ŝ), y⟩ + c(ŝ) ∀y ∈ U,

a simple calculation shows that (5.3) yields (5.2) with

ζ = −2σx + b(ŝ).

(b) ⟹ (c):

Let x_{0} ∈ U and ζ_{0} ∈ ∂_{P} f(x_{0}). Then there exists α > 0 so that

f(y) ≥ p(y) := −α∥y − x_{0}∥^{2} + ⟨ζ_{0}, y − x_{0}⟩ + f(x_{0})  (5.4)

for all y sufficiently near x_{0}. Since hypothesis (A) implies that f is bounded below on U, it readily follows that α can be taken large enough to ensure that the quadratic p satisfies

f(y) > p(y) ∀y ∈ U, y ≠ x_{0}.  (5.5)

Let

α̃ = inf{α > 0 : (5.5) holds}.

If α̃ ≤ σ, then (5.2) holds and there is nothing further to show. So we shall suppose that α̃ > σ, and let 0 < ε < α̃ − σ. Also, let the quadratic p be as in (5.4), but with α = α̃. Note that

f(y) ≥ p(y) ∀y ∈ U.

Since α̃ is an infimum, there exists x_{1} ∈ U different from x_{0} such that

p(x_{1}) + ε∥x_{1} − x_{0}∥^{2} > f(x_{1}).  (5.6)

For 0 ≤ t ≤ 1, let

x_{t} = tx_{1} + (1 − t)x_{0}.

By the present assumption that (b) holds, there exists ζ_{t} ∈ R^{n} and c_{t} ∈ R so that

q_{t}(y) := −σ∥y − x_{0}∥^{2} + ⟨ζ_{t}, y − x_{0}⟩ + c_{t}

satisfies

q_{t}(x_{t}) = f(x_{t})

and

q_{t}(y) ≤ f(y) ∀y ∈ U.

That is, we have chosen ζ_{t} so that ζ_{t} − 2σ(x_{t} − x_{0}) ∈ ∂_{P} f(x_{t}) and c_{t} so that c_{t} = q_{t}(x_{0}). Let \overline{p} and \overline{q}_{t} denote the restrictions of p and q_{t} to the line segment [x_{0}, x_{1}]; that is, for s ∈ [0, 1] we set

\overline{p}(s) = −α̃s^{2}∥x_{1} − x_{0}∥^{2} + s⟨ζ_{0}, x_{1} − x_{0}⟩ + f(x_{0})

and

\overline{q}_{t}(s) = −σs^{2}∥x_{1} − x_{0}∥^{2} + s⟨ζ_{t}, x_{1} − x_{0}⟩ + c_{t}.

If we define

w_{t}(s) := \overline{q}_{t}(s) − \overline{p}(s) − εs^{2}∥x_{1} − x_{0}∥^{2},

then

\begin{matrix}w_{t}(0) & = c_{t} − f(x_{0}) ≤ 0, \\ w_{t}(1) ≤ f(x_{1}) & − p(x_{1}) − ε∥x_{1} − x_{0}∥^{2} ≤ 0, \end{matrix}

and

\frac{d^{2}}{ds^{2}} w_{t}(s) = 2(−σ + α̃ − ε)∥x_{1} − x_{0}∥ < 0.

Thus w_{t} does not attain its maximum in (0, 1), and therefore must satisfy w_{t}(s) ≤ 0 for all s ∈ [0, 1]; that is

\overline{q}_{t}(s) ≤ \overline{p}(s) + εs^{2}∥x_{1} − x_{0}∥^{2} ∀t ∈ (0, 1), ∀s ∈ [0, 1].  (5.7)

Upon noting that \overline{p}(t) ≤ f(x_{t}) = q_{t}(x_{t}) = \overline{q}_{t}(t) and letting s = t in (5.7), we obtain

\overline{p}(t) ≤ \overline{q}_{t}(t) ≤ \overline{p}(t) + εt^{2}∥x_{1} − x_{0}∥^{2}.  (5.8)

Hence c_{t} → f(x_{0}) as t ↓ 0. Since c_{t} = \overline{q}_{t}(0) ≤ f(x_{0}), we also see from the first inequality in (5.8) that

lim sup_{t↓0}⟨ζ_{t}, x_{1} − x_{0}⟩ ≥ ⟨ζ_{0}, x_{1} − x_{0}⟩.  (5.9)

Thus we have

f(x_{1}) ≥ lim sup_{t↓0} \overline{q}_{t}(1)

= lim sup_{t↓0}[−σ∥x_{1} − x_{0}∥^{2} + ⟨ζ_{t}, x_{1} − x_{0}⟩ + c_{t}]

> −(α̃ − ε)∥x_{1} − x_{0}∥^{2} + ⟨ζ_{0}, x_{1} − x_{0}⟩ + f(x_{0})

= p(x_{1}) + ε∥x_{1} − x_{0}∥^{2}.

This violates (5.6), and therefore α̃ ≤ σ.

(c) ⟹ (a): Let x ∈ U and ζ ∈ ∂_{P} f(x) be such that (5.2) holds. We then have

f(y) = max_{(x,ζ)∈Γ} {−σ∥y − x∥^{2} + ⟨ζ, y − x⟩ + f(x)} ∀y ∈ U,

where

Γ := {(x, ζ) : x ∈ U, ζ ∈ ∂_{P} f(x)};

this set is nonempty by the density of P–subgradients. Denote the Lipschitz rank of f on U by K. Then

sup{∥ζ∥ : ζ ∈ ∂_{P} f(x), x ∈ U} ≤ K.

Therefore cl(Γ) is compact, and

f(y) = max_{(x,ζ)∈cl(Γ)} {−σ∥y − x∥^{2} + ⟨ζ, y − x⟩ + f(x)} ∀y ∈ U.

This is readily seen to be a representation of f which is of the desired form (5.1).

In order to establish the relationship between the lower–C^{2} property for functions and the proximal smoothness of sets, it is convenient to extend th= e definition of proximal smoothness to sets that are merely locally closed. (Note that this property is adequate for defining N_{X}^{P}(x).) We say that the locally clos= ed set X is proximally smooth of radius r > 0 if formula (2.1) holds for all x ∈ bdry(X) and all nonzero ζ ∈ N_{X}^{P}(x). This is precisely condition (d) of Theorem 4.1, and hence if X is closed, w= e recover the prior sense of proximal smoothness. In general, however, there = is a qualitative difference, especially as regards the existence of closest points; for example, the open ball B is locally closed and proximally smooth, but no point outside B admits a closest point in B.

The connection between the lower–C^{2} property for Lipschitz functions and proximal smoothness of their epigraphs is given in the following result.

Theorem 5.2. Let hypothesis (A) hold. Then the following are equivalent:

(a) f is lower–C^{2} on U.

(b) There exists σ > 0 such that for every x ∈ U, one has

σ∥(y, α) − (x, f(x))∥^{2} ≥ ⟨\frac{(ζ, −1)}{∥(ζ, −1)∥}, (y, α) − (x, f(x))⟩  (5.10)

for all ζ ∈ ∂_{P} f(x), y ∈ U, α ≥ f(y).

(c) epi(f) is proximally smooth. Furthermore, if f is lower–C^{2} on U, then one has

∂_{P} f(x) = ∂_{L}f(x) = ∂_{C}f(x) ∀x ∈ U,  (5.11)

and in particular, f is regular on U.

Proof. We first will prove that (a) and (b) are equivalent. Suppose that (a) holds, and let f be σ–lower–C^{2} on U. We will show that (b) holds. For each x ∈ U and ζ ∈ ∂_{P} f(x), the inequality (5.2) holds. This implies that

α − f(x) + σ [∥y − x∥^{2} + (α − f(y))^{2}] ≥ ⟨ζ, y − x⟩ ∀y ∈ U, ∀α ≥ f(y).

It follows that

σ∥(y, α) − (x, f(x))∥^{2} ≥ ⟨(ζ, −1), (y, α) − (x, f(x))⟩  (5.12)

for all ζ ∈ ∂_{P} f(x), y ∈ U, α ≥ f(y), and therefore (5.10) holds, and (b) follows.

Now suppose that (b) holds. Let x ∈ U and ζ ∈ ∂_{P} f(x). Continuing to denote the Lipschitz rank of f on U by K, we observe that (b) implies

(σ\sqrt{K^{2} + 1})∥(y, α) − (x, f(x))∥^{2} ≥ ⟨(ζ, −1), (y, α) − (x, f(x))⟩

F. H. Clarke, R. J. Stern, P. R. Wolenski / Proximal smoothness, lower–C^{2} property 143

for all ζ ∈ ∂_{P} f(x), y ∈ U, α ≥ f(y). The last inequality can be rewritten as

(σ\sqrt{K^{2} + 1}) [∥y − x∥^{2} + ∥f(y) − f(x)∥^{2}] ≥ ⟨ζ, y − x⟩ − f(y) + f(x).

Since

∥f(y) − f(x)∥^{2} ≤ K^{2}∥y − x∥^{2},

we therefore have

f(y) ≥ −σ(1 + K^{2})^{\frac{3}{2}} ∥y − x∥^{2} + ⟨ζ, y − x⟩ + f(x) ∀y ∈ U.

In view of the fact that x ∈ U and ζ ∈ ∂_{P} f(x) were arbitrary, we have shown that f is σ(1 + K^{2})^{\frac{3}{2}} –lower–C^{2} on U; that is, condition (a) holds and is equivalent to (b). Since f is Lipschitz on U, for each x ∈ U the proximal normal cone N_{epi(f)}^{P}(x, f(x)) is generated by vectors of the form (ζ, −1) as ζ varies in the proximal subdifferential ∂_{P} f(x). Consequently, (5.10) is equivalent to condition (d) of Theorem 4.1, with X = epi(f), which is locally closed. The “furthermore” part of the assertion follows from Corollary 4.15.

Remark 5.3. The equivalences provided by Theorems 5.1 and 5.2 go through with minor modifications if R^{n} is replaced by a general real Hilbert space H. At the outset, one then requires weak continuity of the functions b(·) and c(·), as well as weak compactness of the set S.

Acknowledgment. The authors benefited from useful discussions with Yu. S. Ledyaev.

References

[1] D. Azé and C. D. Horvath: A remark on extension of Lipschiz multifunctions. (to appear).

[2] J. M. Borwein and S. Fitzpatrick: Existence of nearest points in Banach spaces. Can. J. Math., 51:702–720, 1989.

[3] J. M. Borwein and J. R. Giles: The proximal normal formula in Banach spaces. Trans. Amer. Math. Soc., 302:371–381, 1987.

[4] F. H. Clarke: Methods of Dynamic and Nonsmooth Optimization. Volume 57 of CBMS-NSF Regional Conference Series in Applied Mathematics, S.I.A.M., Philadelphia, 1989.

[5] F. H. Clarke: Optimization and Nonsmooth Analysis. Wiley-Interscience, New York, 1983. Republished as Vol. 5 of Classics in Applied Mathematics, S.I.A.M., Philadelphia, 1990.

[6] F. H. Clarke, Yu. S. Ledyaev, and P. R. Wolenski: Proximal analysis and minimization principles. J. Math. Anal. Appl. to appear.

[7] F. H. Clarke, R. J. Stern, and P. R. Wolenski: Subgradient criteria for monotonicity, the Lipschitz condition, and convexity. Can. J. Math., 45:1167–1183, 1993.

[8] F.H. Clarke: Generalized gradients and applications. Trans. Amer. Math. Soc., 205:247– 262, 1975.

[9] J. M. Danskin: The Theory of Max Min. Springer Verlag, New York, 1967.

144 F. H. Clarke, R. J. Stern, P. R. Wolenski / Proximal smoothness, lower–C^{2} property

[10] I. Ekeland: On the variational principle. J. Math. Anal. Appl., 47:324–353, 1974.

[11] J. B. Hiriart–Urruty: Extension of Lipschitz functions. J. Math. Anal. Appl., 77:539–554, 1980.

[12] J. B. Hiriart–Urruty: Generalized differentiability, duality and optimization for problems dealing with differences of convex functions. Lecture Notes in Economics and Mathematical Systems, 256:37–70, 1984.

[13] A. Ioffe: Approximate subdifferentials and applications II. Mathematika, 33:111–128, 1986.

[14] K. S. Lau: Almost Chebychev subsets in relexive Banach spaces. Indiana Univ. Math. J., 2:791–795, 1978.

[15] P. Loewen: Optimal Control via Nonsmooth Analysis. CRM Proceedings and Lecture Notes, Amer. Math. Soc., 1993.

[16] D. Preiss: Differentiability of Lipschitz functions on Banach spaces. J. Funct. Anal, 91:312– 345, 1990.

[17] R. T. Rockafellar: Clarke’s tangent cones and boundaries of closed sets in R^{n}. Nonlinear Analysis, 3:145–154, 1979.

[18] R. T. Rockafellar: Favorable classes of Lipschitz continuous functions in subgradient optimization. in Nondifferentiable Optimization, E. Nurminski, Ed., Permagon Press, New York, 1982.

[19] R. T. Rockafellar: The Theory of Subgradients and its Applications to Problems of Optimization: Convex and Nonconvex Functions. Heldermann Verlag, Berlin, 1981.

[20] J. E. Spingarn: Submonotone subdifferentials of Lipschitz functions. Trans. Amer. Math. Soc., 264:77–89, 1981.

[21] J.-P. Vial: Strong and weak convexity of sets and functions. Math. Ops. Res., 8:231–259,