Clarke critical values of subanalytic Lipschitz continuous functions

CLARKE CRITICAL VALUES OF SUBANALYTIC LIPSCHITZ CONTINUOUS FUNCTIONS J´ ERˆ OME BOLTE, ARIS DANIILIDIS, ADRIAN LEWIS & MASAHIRO SHIOTA Abstract. We prove that any subanalytic locally Lipschitz function has the Sard property. Such functions are typically nonsmooth and their lack of regularity necessitates the choice of some generalized notion of gradient and of critical point. In our framework these notions are defined in terms of the Clarke and of the convex-stable subdifferentials. The main result of this note asserts that for any subanalytic locally Lipschitz function the set of its Clarke critical values is locally finite. The proof relies on Pawlucki’s extension of the Puiseux lemma. In the last section we give an example of a continuous subanalytic function which is not constant on a segment of “broadly critical” points, that is, points for which we can find arbitrarily short convex combinations of gradients at nearby points. 1. Introduction Several Sard-type results are known in the literature using various notions of a critical point. For example, Yomdin’s classical paper [18] addresses this issue for near-critical points and gives an evaluation of the Kolmogorov metric entropy for the set of near-critical values. In a recent work, Kurdyka- Orro-Simon [12] show that the set of asymptotically-critical values of a Cpsemialgebraic mapping f:Rn→Rkhas dimension less than kprovided that p≥max {1, n −k+ 1}. Concerning non-differentiable functions, Rifford [15], extending a previous result of Itoh-Tanaka [10], establishes that the set of Clarke critical values of the distance function to a closed submanifold of a complete Riemannian manifold has Lebesgue measure zero. Our work relies mainly on two concepts of a critical point that we now proceed to describe. The notion of a limiting subgradient for a continuous function fon Rncan be briefly defined as follows: x∗is a limiting subgradient of fat x, written x∗∈∂f(x), if there exist sequences xn→x, x∗ n→x∗ 2000 Mathematics Subject Classification. Primary 26B05 ; Secondary 49J52, 32B30. Key words and phrases. Clarke critical point, convex-stable subdifferential, nonsmooth analysis, Morse-Sard theorem, subanalytic function. 1 2 J´ ER ˆ OME BOLTE, ARIS DANIILIDIS, ADRIAN LEWIS & MASAHIRO SHIOTA such that, for nfixed: lim inf y→xn, y6=xn f(y)−f(xn)− hx∗ n, y −xni ky−xnk≥0, that is, each x∗ nis a Fr´echet subgradient of fat xn. Clearly, for C1functions the notion of limiting subgradient coincides with the usual derivate ∇fof f, while in general the operator x7→ ∂f(x) is multivalued. A limiting-critical point xof fis therefore a point for which there exists a zero subgradient: that is ∂f(x)30. Concerning nonsmooth analysis and related problems of subdifferentiation, see the introductory books of Clarke [6], Clarke-Ledyaev- Stern-Wolenski [7] or Rockafellar-Wets [16]. In a recent work [4, Theorem 13], we show that any continuous subanalytic function fon Rnis constant on each connected component of the set of its limiting-critical points. The main motivation for proving this Sardtype result for subanalytic continuous functions was to derive a generalized ÃLojasiewicz inequality which in turn was used in the asymptotic analysis of subgradient-like dynamical systems ([3, Theorem 3.1]. These dynamics occur frequently in various domains such as Optimization, Mechanics and PDE’s. With this line of research in mind we adopt here a different viewpoint. The assumptions on fare enhanced – namely, fis assumed to be locally Lipschitz continuous – while the definition of a critical point is weakened. As above, this alternative notion relies on a concept of subdifferentiation: we say that x∗is a Clarke-subgradient of fat xif x∗∈∂◦f(x) := co ∂f(x), where co ∂f(x) is the closed convex hull of ∂f(x). Accordingly, a point xis said to be Clarke critical if ∂◦f(x)30. This turns out to be equivalent to the following property 0∈co   [ z∈B(x,ε) ˆ ∂f(z)   ,for every ε > 0 (CR) (see Proposition 9 or [5]) which reflects the idea that a point is Clarke critical if we can find short convex combinations of gradients at nearby points.1For instance, x= 0 is a Clarke critical point for the function x7−→ −||x||, but it is not a limiting-critical, since ∂f(0) = Sn−1(the unit sphere of Rn), while ∂◦f(x) = BRn(0,1) (the unit ball of Rn). 1This is no longer true for continuous functions: a point satisfying (CR) need not be Clarke critical. CLARKE CRITICAL VALUES OF SUBANALYTIC LIPSCHITZ CONT. FUNCT. 3 Our main result asserts that any locally Lipschitz continuous subanalytic function fdefined on some open subset of Rnis constant on each connected component of the set of its Clarke critical points. Since the latter is subanalytic, it follows directly that the set of Clarke critical values of fis locally finite. The proof of this result is based on a “path-perturbation” lemma [4, Lemma 12], which itself relies heavily on Pawlucki’s extension of the Puiseux Lemma [14, Proposition 2]. An alternative notion of subdifferential, namely the convex-stable subdifferential, has been introduced by Burke, Lewis and Overton [5]. The corresponding critical points are precisely the points which comply with (CR). As pointed out above, if fis a Lipschitz continuous function, one recovers exactly the notion of a Clarke critical point; however for general continuous functions the convex-stable subdifferential appears to be larger than the usual Clarke subdifferential, giving rise to another concept of a critical point: the “broadly critical points”. In the last section we show that a continuous subanalytic function may fail to have the Sard property on the broadly critical set. We indeed exhibit a function f:R3→Rwhich is not constant on some segment of points satisfying (CR). 2. Preliminaries In this section we recall several definitions and results necessary for further developments. For basic and fundamental results of subanalytic geometry see Bierstone-Milman [2], ÃLojasiewicz [13], van der Dries-Miller [9] or Shiota [17]. Concerning nonsmooth analysis some general references are Clarke [6], Clarke-Ledyaev-Stern-Wolenski [7] or Rockafellar-Wets [16]. In the first two sections, we are interested in locally Lipschitz functions: accordingly, we state the definitions and theorems of nonsmooth analysis that we use specifically for this case. The case of continuous functions is treated in Section 4. Consequently, throughout Section 2 and 3 we make the following standing assumption: Uis a nonempty open subset of Rnand f:U→R is a locally Lipschitz continuous function. We shall essentially deal with the following three notions of subdifferentiation. 4 J´ ER ˆ OME BOLTE, ARIS DANIILIDIS, ADRIAN LEWIS & MASAHIRO SHIOTA Definition 1 (subdifferential).For any x∈Ulet us define (i) the Fr´echet subdifferential ˆ ∂f(x) of fat x: ˆ ∂f(x) = ½x∗∈Rn: lim inf y→x,y6=x f(y)−f(x)− hx∗, y −xi ky−xk≥0¾, (ii) the limiting subdifferential ∂f(x) of fat x: x∗∈∂f(x)⇔ ∃xn∈U, :∃x∗ n∈ˆ ∂f(xn),:xn→x, :x∗ n→x∗as n→ ∞, (iii) the Clarke subdifferential ∂◦f(x) of fat x: ∂◦f(x) = co ∂f(x),(1) where co ∂f(x) is the closed convex hull of ∂f(x). Remark 1. (a) If T:U⇒Rnis a point-to-set mapping, its domain and its graph are respectively defined by dom T:= {x∈U:T(x)6=∅} and Graph T:= {(x, y)∈U×Rn:y∈T(x)}. Clearly dom ˆ ∂f ⊂dom ∂f ⊂ dom ∂◦f. A well known result of variational analysis asserts that dom ˆ ∂f is a dense subset of U(see [6], for example). (b) Since fis locally Lipschitz continuous the point-to-set mapping U3 x7−→ ∂◦f(x) is bounded on compact subsets of U. (c) If fis differentiable at x, then ˆ ∂f(x) = {∇f(x)}. (d) If fis a subanalytic function all the subdifferential mappings defined above have a subanalytic graph (see [4, Proposition 2.13]). The notion of a Clarke critical point is then defined naturally. Definition 2 (Clarke critical point).A point a∈Uis called Clarke critical for a locally Lipschitz function fif ∂◦f(a)30, or equivalently, if relation (CR) holds (see Proposition 9). Remark 2 (subdifferential regularity).Let us recall that a locally Lipschitz function fis called subdifferentially regular if ˆ ∂f =∂f, or equivalently if ˆ ∂f =∂◦f. For subdifferentially regular functions, the sets of Fr´echet-critical and of Clarke critical points coincide and one can obtain easily the conclusion of our main result via an elementary argument (see Remark 3 for details). Let us recall the chain-rule for subdifferentials (see [16, Theorem 10.6, page 427], for example). CLARKE CRITICAL VALUES OF SUBANALYTIC LIPSCHITZ CONT. FUNCT. 5 Proposition 3 (subdifferential chain rule).Let Vbe an open subset of Rm and G:V→UaC1mapping. Define g:V→Rby g(x) = f(G(x)) for all x∈V. Then ˆ ∂g(x)⊃ ∇G(x)Tˆ ∂f(G(x)),(2) ∂g(x)⊂ ∇G(x)T∂f(G(x)),(3) where ∇G(x)Tdenotes the transpose of the Jacobian matrix of Gat x. If in addition Gis a diffeomorphism the above inclusions become equalities, thus ∂g(x) = ∇G(x)T∂f(G(x)), ∂◦g(x) = ∇G(x)T∂◦f(G(x)),∀x∈V. (4) The following lemma, based on a result of Pawlucki [14], plays a key role in the proof of both Theorem 5 and Theorem 7. Lemma 4 (path perturbation lemma).([4, Lemma 12]) Let Fbe a nonempty subanalytic subset of Rn,γ: [0,1] →clFa one-to-one continuous subanalytic path and η > 0. Then there exists a continuous subanalytic path z: [0,1] →clFsuch that (i) k˙z(t)−˙γ(t)k< η for almost all t∈(0,1), (ii) the (subanalytic) set ∆ := {t∈[0,1] : z(t)∈clFF}(5) has a Lebesgue measure less than η, (iii) z(t) = γ(t), for all t∈∆∪ {0,1}. Let us recall the following Sard-type result concerning the limiting-critical points of continuous subanalytic functions. Theorem 5 (Sard theorem for limiting-critical points).([4, Theorem 13]) Let g:U→Rbe a subanalytic continuous function. Then fis constant on each connected component of the set of its limiting-critical points (∂f)−1(0) := {x∈U:∂f(x)30}. Unless the function is subdifferentially regular, the above theorem is obviously not appropriate for the study of locally Lipschitz functions with the Clarke-subdifferential. Typical examples are given by functions whose epigraph have “inward corners”, such as for instance f(x) = −||x||. Sharp saddle points also provide some elementary illustrations. For example if one sets f:Rm×Rn×Rp3(x, y, z)7−→ ||x|| − ||y||, 6 J´ ER ˆ OME BOLTE, ARIS DANIILIDIS, ADRIAN LEWIS & MASAHIRO SHIOTA points of the type (0,0, z) are Clarke critical but they are not limitingcritical. This follows from the straightforward computations: ∂f(0,0, z) = BRm(0,1) ×Sn−1× {0}pand ∂◦f(0,0, z) = BRm(0,1) ×BRn(0,1) × {0}p. 3. A Sard theorem for subanalytic Lipschitz continuous functions For the proof of the central result of this note we will need the following lemma. Lemma 6. Set e:= (1,0, . . . , 0) ∈Rnand assume that [0,1]e⊂U, with ∂◦f(te)30for all t∈[0,1].Then fis constant on [0,1]e. Proof. Let us provisionally set SL:= {x∈[0,1]e: 0 ∈∂f(x)}, where ∂f denotes the limiting subdifferential of f(Definition 1(ii)). By Remark 1 (d), the set SLis subanalytic thus, being a (closed) subset of [0,1]e, it is a finite union of segments. By using Theorem 5 we conclude that fis constant on each one of them. Owing to the continuity of f, it is therefore sufficient to prove that fis also constant on each non-trivial segment of [0,1]e\SL. This shows that there is no loss of generality to assume that SLis empty, that is: 0/∈∂f(te), t ∈[0,1]. Let us now fix some δ > 0 and let us define Γδ={x∈[0,1]e:∀x∗∈∂f(x),|hx∗, ei| > δ}.(6) We observe that (6) defines a subanalytic subset of Rn. Let us prove by contradiction that this set is finite. Indeed, if this were not the case, then by using the subanalyticity of Γδ, there would exist a < b in [0,1] such that (a, b)e⊂Γδ. Let Vbe an open bounded subset of Usuch that [0,1]e⊂V⊂cl V⊂Uand define ˆ Γ+ δ={x∈cl V:∃x∗∈ˆ ∂f(x),hx∗, ei> δ}, ˆ Γ− δ={x∈cl V:∃x∗∈ˆ ∂f(x),hx∗, ei<−δ}, where ˆ ∂f denotes the Fr´echet subdifferential of f(Definition 1(i)). Since 0∈∂◦f(x) = co ∂f(x) for every x∈Γδ, we have that max{hx∗, ei:x∗∈∂f(x)}> δ and min{hx∗, ei:x∗∈∂f(x)}<−δ. So using the definition of the limiting subdifferential we obtain that (a, b)e⊂ cl ˆ Γ+ δand (a, b)e⊂cl ˆ Γ− δ. Let us set l=b−aand M:= sup{||x∗|| :x∗∈∂◦f(x), x ∈cl V}. The finiteness of Mcomes from the Lipschitz continuity property of f(see Remark 1 (b) for instance) and the compactness of cl V. The function t→ CLARKE CRITICAL VALUES OF SUBANALYTIC LIPSCHITZ CONT. FUNCT. 7 f(te) is subanalytic and continuous, hence absolutely continuous ([4, Lemma 5]). Thus by using relation (3) of Proposition 3 (subdifferential chain rule), we obtain that Zv u |d dtf(te)|dt ≤(v−u) sup{|he, x∗i| :t∈[u, v], x∗∈∂f(te)} ≤ (v−u)M, for all 0 ≤u≤v≤1. Take η > 0 and apply Lemma 5 (path perturbation lemma) for F=ˆ Γ+ δ, and γ(t) = te, t ∈(a, b). Since ˙γ(t) = e, for all t∈[0,1], it follows that there exists a subanalytic continuous curve z: [a, b]→cl ˆ Γ+ δ such that • k ˙z(t)−e|| < η for almost all t∈(a, b), •the (subanalytic) set ∆ := nt∈[a, b] : z(t)∈clˆ Γ+ δˆ Γ+ δohas a Lebesgue measure less than η, •z(t) = γ(t), for all t∈∆∪ {a, b}. The continuous function g(t) = f(z(t)) is also subanalytic so for all but finitely many t’s in (a, b)\∆ we conclude from relation (2) of Proposition 3 and Remark 1 (c) that {g0(t)}=ˆ ∂g(t)⊃ h ˙z(t),ˆ ∂f(z(t)i ⊃ { h ˙z(t), z∗ +(t)i}, where z∗ +(t)∈ˆ ∂f(z(t)) can be chosen in order to satisfy he, z∗ +(t)i> δ (since z(t)∈ˆ Γ+ δ). Thus for almost all tin [a, b]\∆ we have g0(t) = he, z∗ +(t)i+h˙z(t)−e, z∗ +(t)i ≥ δ− || ˙z(t)−e||M≥δ−ηM, so that f(be)−f(ae) = Zb a d dtf(z(t))dt ≥Z[a,b]\∆ g0(t)dt −Z∆ |d dtf(z(t))|dt ≥(l−η)(δ−ηM)−ηM. By choosing ηsmall enough, the above quantity can be made positive so that f(be)> f(ae). It suffices to repeat the argument with ˆ Γ− δto obtain f(be)< f(ae), which yields a contradiction. 8 J´ ER ˆ OME BOLTE, ARIS DANIILIDIS, ADRIAN LEWIS & MASAHIRO SHIOTA Thus the set Γδis finite. We further set Γ0={x∈[0,1]e:∃x∗∈∂f(te),hx∗, ei= 0}. It follows easily from Definition 1 (ii) that the limiting subdifferential ∂f has closed values. Thus, the set ∂f(te) is closed for every t∈[0,1], which yields [0,1]e= Γ0∪¡∪i≥1Γ1/i¢. Note that ∪i≥1Γ1/i is countable and equal to the subanalytic set [0,1]eΓ0. It follows that ∪i≥1Γ1/i is finite and so {t∈[0,1], te ∈Γ0} is a finite union of intervals with a finite complement in [0,1]. Using the continuity of f, it suffices to prove that fis constant on each segment of Γ0. Let (a, b)e⊂Γ0with 0 ≤a < b ≤1. For any ² > 0 we define ˆ Γ² 0:= {x∈cl V:∃x∗∈ˆ ∂f(x),|hx∗, ei| < ²}. By definition of the limiting subdifferential, (a, b)e⊂cl ˆ Γ² 0. Applying Lemma 4 for the set ˆ Γ² 0, for η < ² and for the path γ(t) = te, we obtain a curve z: [a, b]→ˆ Γ² 0and a set ∆ ⊂[a, b] satisfying (i), (ii), (iii) of Lemma 4. Set h(t) = f(z(t)). As before, for all but finitely many t’s in [a, b]\∆: {h0(t)}={h ˙z(t), z∗ ²(t)i}, where z∗ ²(t)∈ˆ ∂f(z(t)) can be taken such that |hz∗ ²(t), ei| < ². Therefore for almost all tin [a, b]\∆ we have |h0(t)|=|he, z∗ +(t)i+h˙z(t)−e, z∗ +(t)i| ≤ ²+ηM, so that |f(be)−f(ae)| ≤ Zb a |d dtf(z(t))|dt ≤ | Z[a,b]\∆ |h0(t)|+Z∆ |d dtf(z(t))dt| ≤(l−η)(²+ηM) + ηM. Taking ²(and thus η) sufficiently small, we see that the function fis constant on [0,1]eand the proof is complete. ¤ Theorem 7 (main result).Let Ube a nonempty open subset of Rnand f:U→Ra locally Lipschitz subanalytic mapping. Let Sdenote the set of Clarke critical points of f, that is S:= {x∈U:∂◦f(x)30}. Then fis constant on each connected component of S. Proof. Let x, y belong to the same connected component of S. It is sufficient to prove that f(x) = f(y). Since S= (U× {0}n)∩Graph ∂◦f, we conclude by Remark 1(d) that it is a subanalytic set, so every connected CLARKE CRITICAL VALUES OF SUBANALYTIC LIPSCHITZ CONT. FUNCT. 9 component of Sis also path-connected (see [1], [2] or [8], for example). Thus, there exists a continuous subanalytic path γ: [0,1] →Sjoining x to y. To prove that f(x) = f(y) it suffices to prove that fis constant on γ(0,1). By using the subanalyticity of γtogether with the continuity of f, we can assume that -γ(0,1) is a subanalytic submanifold of U, [Indeed, since γ(0,1) is a finite union of subanalytic manifolds, we can deal with each one separately obtaining (as will be described below) that f is constant on each such manifold. Then the same conclusion will follow for γ(0,1) by a continuity argument.] - there exists a subanalytic diffeomorphism Gfrom a neighbourhood V of γ(0,1) into an open subset of Rnsuch that G(γ(0,1)) = (0,1)e; see [2] for instance. In view of relation (4) of Proposition 3 we have that γ(0,1) ⊂(∂◦f)−1(0) if and only if (0,1)e⊂[∂◦(f◦G−1)]−1(0). This is indeed a consequence of the equivalence ∂◦f(x)30⇔∂◦[f◦G−1](G(x)) 30,for all x∈V. As a consequence fis constant on γ(0,1) if and only if f◦G−1is constant on (0,1)e. The conclusion follows then from Lemma 6. ¤ Corollary 8 (Sard theorem for Clarke critical points).Under the assumptions of Theorem 7 the set f(S)of the Clarke critical values of fis countable (and hence has measure zero). Proof. This follows from Theorem 7 and the fact that the set S, being subanalytic, has at most a countable number of connected components (a finite number on each compact subset of U). ¤ Let us finally conclude with the following remark. Remark 3 (an easy proof for the case of subdifferential regularity).If fis assumed to be subdifferentially-regular (see Remark 1(b)) then Theorem 7 follows via a straightforward application of [16, Theorem 10.6]. Let us recall the simple argument (see also [3, Remark 3.2]): Assume that x, y are in the same connected component of S. Let z: [0,1] →Sbe a continuous subanalytic path with z(0) = xand z(1) = yand define the subanalytic function h(t) = (f◦z)(t). From the “monotonicity lemma” (see [9, Fact 4.1], or [11, Lemma 2], for example) we get h0(t) = 0, for all 16 J´ ER ˆ OME BOLTE, ARIS DANIILIDIS, ADRIAN LEWIS & MASAHIRO SHIOTA J´erˆome BOLTE ([email protected] ; http://www.ecp6.jussieu.fr/pageperso/bolte/) Equipe Combinatoire et Optimisation (UMR 7090), Case 189, Universit´e Pierre et Marie Curie 4 Place Jussieu, 75252 Paris Cedex 05. Aris DANIILIDIS ([email protected] ;http://mat.uab.es/~arisd) Departament de Matem`atiques, C1/320 Universitat Aut`onoma de Barcelona E-08193 Bellaterra (Cerdanyola del Vall`es), Spain. Adrian LEWIS ([email protected] ; http://www.orie.cornell.edu/~aslewis) School of Operations Research and Industrial Engineering Cornell University 234 Rhodes Hall, Ithaca, NY 14853, United States. Masahiro SHIOTA ([email protected]) Department of Mathematics Nagoya University (Furocho, Chikusa) Nagoya 464-8602, Japan.