R T Rockafellar

CLARKE'S TANGENT CONES AND THE BOUNDARIES CLOSED SETS IN R"

Keywords: Tangent cones, normal cones, generalized gradients, sub-differential calculus, Lipschitzian functions, optimality conditions

INTRODUCTION

LET C BE a nonempty closed subset of R". For each x E C, the tangent cone T,(x) in the sense of Clarke consists of all y E R" such that, whenever one has sequences t, 10 and xk --f x with xk E C, there exist yk + y with xk + t,y, E C for all k. This is not Clarke's original definition in [l, 21, but it is equivalent to it by his Proposition 3.7 in [2] (see also [3, Remark 2;1] and more recently Hiriart-Urruty [4, Chapter VII; 51). It is obvious that 0 E T,(x) and that 7"(x) really is a cone (i.e. y E T,(x) implies ly E T,(x) for all 1 > 0). Moreover T,(x) is closed. What is remarkable, however, is that T,(x) is always convex (cf. Clarke [l,[START_REF] Friedman | A one phase Stephan problem[END_REF] a direct proof is also provided below). This property is surprising, because it is obtained without any convexity or smoothness assumptions on C. In the absence of such assumptions (and related 'constraint qualifications'), the other local cones that have been studied in optimization theory (cf. [6]) are typically not convex, and this has always posed difficulties. If C is a "differentiable submanifold" of R", T'(x) is the classical tangent space (as a subspace of R"), while if C is convex T,(x) is the usual closed tangent cone of convex analysis [7].

Tangent cones in this sense have a natural role in the theory of flow-invariant sets and ordinary differential equations (and inclusions), see Clarke [2] and Clarke-Aubin The main purpose of this article is to establish a strong property of interior tangent vectors (Theorem 2) which implies that the boundary of C must be Lipschit~an around any boundary point x where int T,(x) # 0. The condition int T,(x) $ 0 is equivalent to N=(x) being a ~~~~~e~ cone, in the sense that 0 # z E N&) implies -z 4 N,(x). This result is used to derive a rule for estimating the tangent cones and normal cones to the intersection of two sets and the inverse image of a set under a differentiable mapping (Theorem 5). A strengthened convexity property of C is also proved (Theorem 1). It is shown that 4$(x) cannot be a nonempty bounded set unless f is actually Lispchitzian around x (Theorem 4).

CONVEXITY OF THE TANGENT CONE

Clarke's original approach to the definition of T,(x) in [l, 23 is based on special properties of Lipschitzian functions (for which he initially defined af( x in another manner). It is of some in-) terest to know that the convexity of T,(x) can also be deduced straight from the equivalent definition adopted here. For the record we provide a proof which also shows how the convexity is approached 'uniformly' in the limit, a property that will be needed in deriving the fundamental theorem in the next section.

Let B denote the closed unit ball in R", so that x + 6B is the closed ball of radius 6 about x. One has y E T&x) if and only if for every E > 0 there exist 6 > 0 and ;1 > 0 such that

C n [x' + t(y + EB)] # 0 for all x' E C n (x + 6B), to[O,/%]. (2.1)
In what follows, the convex hull of a set D is denoted by COD.

THEOREM 1. Let D be any nonempty compact subset of T,(x). Then for every E > 0 there exist 6 > 0 and A > 0 such that (2;l) is valid simultaneously for all YE COD. (Thus in particular co D c T,(x), so T,(x) is convex.)

Proof: Let E > 0. Since D is compact, it can be covered by a finite family of balls yi + .sB, where y,ET,(x)fori= l,...,m.Then (2.2) i=l It will suffice to show that (2.1) holds for all y in co(yl,. . . , y,,J, because this will imply via (2.2) that for 2s in place of E it holds for all y E co D (a property equivalent to the desired conclusion, since E is arbitrary anyway). For i = 1,. . . , m, (2.1) holds for y, and certain di > 0, Ai > 0. Taking 6 and X to be the smallest of these values, one has Cn[x'+t~,+~B)]#~fora11x'~Cn(x+BB),t~[0,~,andi=1,...,m.

(2.3)

Choose 6 E (0, &J and ;1 E (0, X] small enough that 6 + n(p + E) d 8, where p = max{lyll,. . . , Iy,I).

(2.4)

The assertion

C n [x' + t(y + EB)] # ~25 for all x' E C n (x + 6B), t E [0, A] and ally E co(y,, . . . , y& (2.5) holds trivially for k = 1, in view of (2.3); make the induction hypothesis that it holds for k = m -1. Thus x" E C n (x + 8B), and since also (1a)t < A < 2 it follows from (2.3) that C meets x" + (1 -a)t(y, + EB). Hence C meets

[x' + at(y' + EB)] + (1 -a)t(y, + EB) = x' + t(y + EB).

This verifies (2.5) for k = m and completes the proof.

Remark. The proof of Theorem 1 is easily extended to infinite-dimensional spaces and thereby demonstrates that the convexity of Clarke's tangent cone (under the corresponding extension of the present form of the definition) is a far more general phenomenon than has been realized. For applications of this approach to the study of generalized directional derivatives of lower semicontinuous functions on locally convex spaces, see [17].

INTERIORS OF TANGENT CONES

The following theorem will be fundamental to the rest of this paper. Proof: Sufficier~cy. Suppose the condition holds, and consider arbitrary y' E (y + EB). For any sequences X~(E C) + x, t, 10, one has xk E (x + 6B) and t, E (0, A) for all k sufficiently large, and consequently xk + tkyk E C for yk E y'. Thus by definition J' E TAX). This proves 7"~) 3 (y + EB).

Necessity. Given YE int T'(x), choose E > 0 small enough that y + 3&B c T,(x). Apply Theorem.1 to D = y + 3&B to obtain 6' > 0 and 1' > 0 such that

C n [x' + t(y' + EB)] # 0 whenever x' E C n (x + 6'B), t E [O, 21, y' E (y + 3&B). (3.2)

Next choose 6 > 0 and ;i > 0 small enough that A < ;1' and6 + 2n(lyl + E) d 6'. C n [% + t(y" + EB] # @ for all t E [0, n'].

(3.9)

However, consider any t small enough that 0 < t < minfp/2e, J. -I> (hence t < ,? < d').

(3.10)

It will be shown that C n [a + t(y" + EB] = @ (even though t E [0, A']

). (3.11) The contradiction between this and (3.9) will finish the proof. Since Remark. Hiriart-Urruty [5, Theorem 41 has proved for Banach spaces a result somewhat akin to Theorem 2 but involving the interior of U,(x) = T,(x) n (-T&X)), where C' is the closure of the complement of C. He assumes x is a 'regular' boundary point (an 'angularity' property) and proves that for y E int V,(x) there then exist E > 0 and J. > 0 with x + ty' E C and x -ty' E C' for all y' E (y + EB), t E (0, A). His argument is based heavily on the 'regularity' assumption and is very different from ours. In the finite-dimensional case, one obtains from Theorem 2 (cf. also the remarks in the next section) that the same conclusion is valid not only for x but all neighboring boundary points x', whether or not x is 'regular', and assuming merely that y E int T,(x).

COROLLARY 1. One has x E int C if and only if x is a point of C such that T,(x) is all of R" (i.e. N,(x) = (0)). Thus C has at least one nonzero normal vector' at each of its boundary points.

Proqf: This is the case of Theorem 2 where y = 0. COROLLARY 2. Let x be a point of C where int T,(x) # @ (i.e. N,(x) is pointed). Then the multifunction N, is closed at x, in the sense that XL(EC) -+ x, zk E N,(x,), zk -+ z =a z E N,(x).

(3.12)

Proof. To prove (3.12), consider first any YE int T,(x). The property in Theorem 2 implies y E T,(x') for all x' E C n (x + 6B), and hence y E T(x,) for all k sufficiently large. Then (y, z,J d 0 by the definition (1.1) of N,, so that 0 3 lim (y, zk) = (y, z). This shows that 2) of 8f it is enough to show that the cone NePif(x,j"(x)) is pointed under these assumptions.

Since this cone is by nature always contained in the lower half-space ((x, tx)lcr d 0}, it fails to be pointed if and only if for some u # 0 it contains both (a, 0) and (-u,O). For an arbitrary element of N,(x) of the form (z, -1) (or any other form, for that matter) this property of u is equivalent to having (z, -1) + t(u, 0) E N,(x) for all t E R.

5

Thus if af(x) contains an element z, the property of u is equivalent to the line {z + tu( t E R) being contained in 81(x). For all t # 0 the cone IV,@, 0,O) is the x,.x,-plane, and similarly N,(O, t, 0) is the x,x,-plane, yet N,(O, 0,O) is just the x,-axis. This is a counterexample to (3.12), and by takingfto be the indicator of C, so that aI = N,(x), one obtains a counterexample to (3.14).

Of course (3.12) and (3.14) do always hold in the convex case [7, Section 24). Furthermore, (3.14) always holds when f is Lipschitzian, cf. [2] (this also follows from Corollary 3 and Theorem 4 below).

LIPSCHITZIAN PROPERTIES

A set C c R" is epi-Lipschitzian at a point x E C if it can be represented near x as the epigraph of a Lipschitzian (Lipschitz continuous) function. This means that for some neighborhood U of x there is a nonsingular linear transformation The fact that a closed set C is epi-Lipschitzian at x if and only if (3.1) holds, is of course all that is needed in deriving Theorem 3 from Theorem 2. This fact is 'well known', but an explicit statement is hard to find. Recently Caffarelli [20, proof of Theorem 21 used it without supplying an argument. A proof for a similar situation, involving boundaries of 'star-shaped' regions, has been given by Friedman and Kinderlehrer [21,Lemma 4.11. While the fact certainly is elementary it is trickier to establish than might be supposed, since the boundary is not already given as a 'surface' but must be shown to be such (locally) under (3.1). This is the crux of the proof of Theorem 3 that is furnished below. These results, which are closely related, will be derived as consequences of Theorem 2, and it is convenient to deal with Theorem 4 first. The necessity of Theorem 4 has already been established by Clarke [l,[START_REF] Friedman | A one phase Stephan problem[END_REF]in proving that his general definition for aI reduces to his first-stage definition in terms of limits in the case where f is Lipschitz continuous).

A: R" + R"-' x R such that C n U = C n A-' (epi $),
Proof of Theorem 4. Lipschitz continuity off around x means the existence of p B 0 and a neighborhood U of x such that f is finite on U and If(x") -f(k)1 gp(x" -x'\ for all x', x" E U.

This property can be expressed equivalently, although somewhat oddly, as follows: there exist 6 > 0, E E (0,l) and A > 0 such that f(x' + ty') d f(x') + t(s-i -1) for all t E [0, 11 when

x' E (x' E/X + bB), f(x') d f(x) + 6, y' E EB. (Here E corresponds to (1 + p)-' ; note that the condition applies in particular when x' = x, so f must be finite on a neighborhood of x.) The virtue of (4.1) is that it can be restated in epigraph terms as (1' finite at x and) (x', c() + t(y', fl) E epi f for all t E [0, A] when

(x', Co E @pi f) n [(x, f(x)) + 6(B x [ -1, l])],
(4.2)

(~'3 B) E [to, 1) + (B x [ -1, I],].
But this is just the condition in Theorem 2 in the case of the set C = epi f, the point (x, f(x)) in C, and the vector (0, 1). (If course C is closed, since ,f is l.s.cJ. It follows that f is (finite and) Lipschitzian in a neighborhood of x if and only iffis finite at x and (0, 1) E int Tc(x, f(x)). When this is true T&x, f(x)) cannot be the whole of R"+i (for then Corollary 1 of Theorem 2 would yield the impossible conclusion that (x, f(x)) E int C). Now for a convex cone K in R", 0 E K # R", the condition a E int K is dual to a property of the polar cone K", namely that the cross-section M = {u E K"l(u, a) = -l} is nonempty and compact [18, Corollary 7F]. Applying this to a = (0, 1) and the cone Tc(x, f(x)), whose polar is the normal cone N,(x,f(x)), one sees that f is (finite and) Lipschitzian in a neighborhood of x if and only if f is finite at x and the set {z E R"I(z, -1) E N,(x, f(x))} is nonempty and bounded. But this is just af(x) by Definition (1.1) whenf(x) < co. (When f(x) = co, @'(x) = 121.)

Proof of Theorem 3. Necessity. The proof of Theorem 4 shows that the epigraph of a Lipschitzian function has tangent cones with nonempty interior. Hence if C can be represented in a neighborhood of x as the epigraph of such a function, in the sense defined, it must be true that int T,(x) # 0.

Sztfficiency. If x E int C, the conclusion that C is epi-Lipschitzian near x is trivial. Suppose therefore that x is a boundary point of C. Then T,(x) is not all of R" (cf. Corollary 1 to Theorem 2). Let y E int T,(x), y # 0, and let H be the hyperplane through the origin orthogonal to y. Each x' E R" can be expressed uniquely in the form 5' + a'y, where 5' E H, u' E R; the mapping ,4:x' + (t', cr') is a nonsingular linear transformation from R" onto H x R. Let (<, a) = A(x). Since y E int T,(x), the property in Theorem 2 holds, and in this the ball B can be replaced equally well by the product of its intersection B' with H and the interval {tyl -1 < t < 11. In terms of A(C), the property is that for some E > 0, 6 > 0, A > 0, one has (5: a') + t(q, j?) E A(C) for all t E [0, 21 when this for T,(x) in the definitions of N,(x) and af(x), he has defined the symmetrized normal cone and symmetrized generalized gradient sets. He has noted that the symmetrized tangent and normal cones reduce to T,(x) and N,(x) if C is either convex or epi-lipschitzian at x. It follows now from Theorem 3 that the symmetrized cones can differ from Clarke's cones only in rather "degenerate" cases, where in particular int T,(x) = @ and N (x) is not pointed (and hence contains some entire line through the origin). As for the symmetrized generalized gradient set, this likewise has to reduce to af(x) except perhaps in certain cases where as(x) is empty or is unbounded and contains some entire line. (As seen in the proof of Corollary 3 in Section 3, this condition is implied by the 'nonpointedness' of Nepi f(x, f(x)).)

AN INCLUSION FOR TANGENT AND NORMAL CONES

A rule for estimating tangent and normal cones will now be derived from Theorem 2. This rule can be used in the computation of necessary conditions for optimality in problems where the feasible set is the intersection of other sets corresponding to various constraints. (cf. [7,Theorems 6.3,6.3,6.71). To establish (5.2), therefore, it will be enough to show that T,(u) includes the set in (5.1). Then (5.3) will follow immediately by passing to the polar cones (cf. [7,Corollaries 16.3.2,16.4.21).

Let v be an element of the intersection in (5.1), and let y = Jv, x = F(u); then v E T'(u), y E int T,(x). Suppose t, 1 0, uk E E, uk + u. In particular uk ED, and since v E T,(u) there must exist vk + v with uk + t,v, E D. Also uk E F-'(C), so that points xk = F(u,) belong to C and xk -+ x. For Y, = [F(u, + t,v,) -0,)1/t, one also has y, -+ Jv = y, because F is continuously differentiable.

Note that F(u, + t,v,) = xk + t,y,; the property in Theorem 2 implies therefore that F(u, + t,v,) E C for all k sufficiently large, i.e. uk + t,v, E F-'(C).

Thus uk + t,v, E E for all k sufficiently large, and it follows that v E T,(u).

Remark. The dual form of condition (5.1) is that, for some v E RP, one has (v, w) d 0 for all w E N,(u), (Jv, 2) < 0 for all nonzero z E N&F(u)).

The proof of the theorem does not really require F to be continuously differentiable on R", just strongly (strictly) differentiable at u in the sense that [F(u' + tv') -F(u')]/t -+ J(u)v when u' + u, v' + v, t 10.

For applications of Theorem 5 to the computation of generalized gradients, see [ 191.

  [3]. They are fundamental in the study of optimization problems through duality with the normal cones N,(x) = T,(x)' = {z E R"]y E T,(x), (y, z> < O} is the (closed) epigraph set {(x, g) E Rnfl ICI 2 f(x)}; iff(x) = co, af(x) is taken to be empty). Clarke has shown in [8-131 that these notions provide the means for extending to the nonconvex case the kinds of necessary conditions for optimality that have been developed for nonsmooth variational problems of convex type (cf. [7-161).

  COD c co c (yi + EB) = co(y,,...,yJ + EB.

  For any x' E C n (x + 6B), t E (0, A), y E co{yl,. . . , y,}. Write y = ay' + (1 -a)~,,,, where Y' E co{y,, . . ., y,_ ,} and a E [0, 11. Since at E [0, A], we have by induction that C meets x' + at(y' + EB). Let x" be any point in the intersection. Then in particular X" E [(x + 6B) + at(ly')B + EB)] = x + [S + at(ly'J + E)]B, where ly'l < max{ Jyr I,. . . ,I y,_ r I} < p in (2) and consequently 6 + at(ly'l + E) G 6 + A(p + E) d 8.

  (C still denotes a closed subset of R", and x is a point of C.) THEOREM 2. One has y E int T'(x) if any only if there exist E > 0, 6 > 0, I > 0 such that X' + ty' E C for all x' E C n (x

  It will be demonstrated that (3.1) holds for this choice of E, 6, ;I. Suppose (3.1) does not hold. Then there exist X E C n (x + 6B), such that X + Ajj $ C. Choose any p > 0 small enough that C n (2 + Xj + pB) = 0 (hence p < 1~ -(X + Xy)l = Xljl). [O,X]ICn(X + sq; + pB) # @}; (3.6) this maximum is attained, because C is closed and B is compact. Since (3.5) holds but X E C, one has O<X<XdA<,<. (3.7) Select any 3 E C n (X + /iji + pB), as exists by (3.6). The interior of the ball X + xj + pB cannot meet 6, in view of (3.6), so actually X=%+Xj+pewithJe/=l. (3.8) Then by (3.4), (3.5), (3.7), one has 11 -XI d 1% -x/ + /Z -ZF/ d 6 + /XJ + pe] < 6 + X/jj/ + Ajji d 6 + 2A(/yl + e). It follows from (3.3) that for this 2 and for y" = j -2&e one has z?:~Cn(x + 6'B)andjE(y + 3aB), and therefore by (3.2)

  t -c p/2& in (3.10), one has 0 < p -2Et < p -Et, so that t(p -p) = pe = (p -2d)e E (p -Et)B. Then X + tjT6 (2 -pe + tij + (p -et)@. Using (3.8) one obtains 5z f t(J7 + EB) c 51 + (I + t)jj + pB, where x < li: + t < X (since t < X -li in (3.10)). This yields (3.11), because C n (X + (X + t)j + pB) = 0 by the definition (3.6) of 1. Co~n~erexa~ple 1. Theorem 2 is no longer true when R" is replaced by an in~nite-dimensional Banach space, even in the case of a convex set. Let C be the closed convex subset of the Hilbert space 1' x R which is the epigraph of the function f(5) = f j$, where 5 = (tl, &, . . . -1. j=l It can be verified that T',(O,O) is the upper half-space ((5, a)la > 0} and hence has nonempty interior containing y = (0,l). But the interior of C is empty, because f is not bounded above on any neighborhood of 0. Hence the property in Theorem 2 cannot hold at x = (0,O).

  (x) is convex with nonempty interior, it is the closure of this interior, and the inequality in (3.13) therefore carries over to all y E T',(x). Thus z E N,(x). COROLLARY 3. Let f:R" -+ R u { + CO} be lower semicontinuous, and let x be a point where f is finite, aJ(x) is nonempty, and 8f(x) does not contain any entire line (i.e. is a convex set of linearity zero [7, p. 651). Then the multifunction 8f is closed at x, in the relative sense that Xk + & Zk E mx,), zJ( -+ z, f(XJ +A$ * z E m).

  view of Corollary 2 and the definition (1.

Counterexample 2 .

 2 The fact that (3.12) and (3.14) can fail without the assumptions in Corollaries 2 and 3 is illustrated by the set C = {(x,,x,,x,)~R~(~~ = x1x2 or x3 = -x1x2}.

  where 4 is a function on R"-' that is finite and Lipschitzian around the point 5 which is the R"l-component of A(x). The part .of the boundary of C in U is represented correspondingly by the graph of 4 and is a 'Lipschitzian surface.' THEOREM 3. A closed set C c R" is epi-Lipschitzian at a point x E C if and only if int T,(x) f @ (i.e. N,(x) is pointed).

THEOREM 4 .

 4 A lower semicontinuous function f: R" + (-co, + co] is (finite and) Lipschitzian in a neighborhood of a point x E R" if and only if 8f(x) is nonempty and bounded.

  (5'3 4 E A(C) n [(5, N) + @B x [ -1, I])],

  E H define hP)E [co, 1) + E(B) x [-1, l])]. $(t') = inf{a'Icr' 2 c1 -6, (<', a') E A(C)) 3 ~1 -6. (4.4) (where the convention inf @ = + co is implicit). Since C is closed, 4 is a lower semicontinuous function with values in (-co, + co]. Taking (5' a') = (5, a) in (4.3), one sees that (p([ + tn) d M + t(1 -E) when n E EB', t E [0, A]. Hence there exists 6' d 6 such that for all 5' E (5 + 6'B) one has &t') d c( + 6 and (consequently) (t'> 6(O) E A(C) n [K E) + 6(B' + [ -1, I])]. Then (4.3) implies (with /I = 1) (t' + tq, q5(5') + t) E A(C) when t E [0,2], q E EB'. (4.5) Therefore, for all 5' E (5 + 6'B) one has @(5' + tq) < 4(5') + t when t E [0, A], r] E EB', so that 4 is Lipschitzian on a neighborhood of 5. Furthermore (t', 4(5') + t) E A(C) for all t E [0, A] by (4.3). For t < 0, of course, one has (t', &t') + t) $ A(C) by the definition of 4. Thus there is a neighborhood of (5, ~1) = (g, 4(c)) m which A(C) coincides with the epigraph of 4. This proves that C is epi-Lipschitzian at x. Remark. Hiriart-Urruty [4, Chapter VII] has introduced the symmetrized tangent cone to C at a boundary point x as the intersection of T,(x) and -T,(x), where C' is the complement of int C. Substituting

THEOREM 5 .

 5 Let u E E = D n F-'(C), where C c R" and D c RP are closed sets and F:RP + R" is continuously differentiable. Let J be the Jacobian of F at u, and suppose that T,(u) n J-' int T,(F(u)) Theorem 5 are of particular note. The first is where E = D n C (thus RP = R", F is the identity transformation, I = J = J-' = J*). The second is where E = F-'(C) (thus D = RP = T,(u), N,(u) = (0)). Proof. Since the tangent cones are closed convex sets, condition (5.1) implies that cl[T,(u) n J-l int T'(F(u))] = T,(u) n J-'T&F(u))

E co, 47JE(Y + 8%

* Research sponsored by the Air Force Office of Scientific Research, Air Force Systems Command, USAF, under grant number 77-3204.