Some remarks on the class of continuous (Semi-) strictcly quasiconvex functions

SOME REMARKS ON THE CLASS OF CONTINUOUS (SEMI-) STRICTLY QUASICONVEX FUNCTIONS ARIS DANIILIDIS & YBOON GARCIA RAMOS Abstract. We introduce the notion of variational (semi-) strict quasimonotonicity for a multivalued operator T:X⇒X∗relative to a nonempty subset Aof Xwhich is not necessarily included in the domain of T. We use this notion to characterize the subdifferentials of continuous (semi-) strictly quasiconvex functions. The proposed definition is a relaxation of the standard definition of (semi-) strict quasimonotonicity, the latter being appropriate only for operators with nonempty values. Thus, the derived results are extensions to the continuous case of corresponding results for locally Lipschitz functions. 1. Introduction The notion of quasiconvexity, referring to a function whose sublevel sets are convex, is probably the most natural generalization of convexity. Its simple definition makes it the starting point for further investigations (see [22], [4], [20], [9], for example). Comparing with the convex case, a quasiconvex function might have local minima which are not global (typical failure in almost all deterministic global optimization methods), or critical points which are not local minimizers (typical failure in all Newton type minimization methods). In this work we are interested in the important subclasses of semistrictly (respectively, strictly) quasiconvex functions, for which at least the first inconvenience is overcome. These classes meet a large domain of applications in microeconomics (see [4] and references therein) and recently regained attention due to its applications to the multicriteria (Pareto) optimization problem (see recent developments in [5], [6]). After the developments in the area of non-smooth analysis [8], there has been an effort to characterize the generalized convexity of functions in terms 2000 Mathematics Subject Classification. Primary 26B42 ; Secondary 49J52, 90C26, 91B42. Key words and phrases. Quasiconvex function, quasimonotone operator, variational analysis, utility function. 1 2 ARIS DANIILIDIS & YBOON GARCIA RAMOS of generalized monotonicity of their subdifferential (see for instance [19], [21], [1], [10]). As an outcome, a natural correspondence between notions of generalized convexity and of generalized monotonicity arises, reflecting the known duality between utility functions (typically being semistrictly quasiconvex) and demand correspondences (typically being semistrictly quasimonotone multifunctions) in the consumer’s theory (see [4], [14], for example). The aforementioned correspondence has been progressively extended from the differentiable case to the case of continuous or sometimes even lower semicontinuous functions. The main tool for these extensions is a nonsmooth version of the mean value theorem, which is known to be valid for every reasonable choice of subdifferential (see [2] for details). However, besides the importance of the classes of semistrict (respectively, strict) quasiconvexity, their dual characterization in terms of the semistrict (respectively, strict) quasimonotonicity of their subdifferentials cannot be extended beyond the class of locally Lipschitz functions, due to the restrictions the aforementioned definitions impose on the domain of the operator. In this work we propose a variational modification of the definitions of semistrict (respectively, strict) quasimonotonicity to make them operational to the continuous case. These definitions enter naturally to the aforementioned duality scheme, and entail no change in case of subdifferentials of locally Lipschitz functions. The paper is organized as follows: in Section 2 we fix our notation and recall definitions and basic results. In Section 3 we introduce the variational definitions of the semistrict and the strict quasimonotonicity (Definition 2), we use them to establish the subdifferential characterizations of the semistrict quasiconvexity (Theorem 5) and the strict quasiconvexity (Theorem 7). In the last part we discuss the compatibility of the introduced notions for operators that are subdifferentials of locally Lipschitz functions. 2. Notation and basic definitions Throughout this work Xwill denote a Banach space, X∗its topological dual and hx∗, xithe value of the functional x∗∈X∗at x∈X. For any x, y ∈Xwe set [x, y] := {tx + (1 −t)y: 0 ≤t≤1} and define the segments ]x, y], [x, y[ and ]x, y[ analogously. We denote by B(x, r) the open ball of center x∈Xand radius r > 0 and for any nonempty subset Sof Xwe denote by co Sits convex envelope. THE CLASS OF CONTINUOUS (SEMI-) STRICTLY QUASICONVEX FUNCTIONS 3 Given a lower semicontinuous function f:X→R∪ {+∞} we denote by dom f:= {x∈X:f(x)<+∞} its domain (which we always assume nonempty) and given x∈dom fwe denote by f↑(x, u) = sup δ>0 lim sup y→fx t&0+ inf v∈B(u,δ) f(y+tv)−f(y) t its Clarke-Rockafellar generalized derivative, where t&0+indicates the fact that t > 0 and t→0, and y→fxmeans that both y→xand f(y)→f(x) (this is superfluous, if fis assumed continuous). Then the Clarke-Rockafellar subdifferential ∂f(x) of the function fat the point xis defined as follows ([8]): ∂f(x) = {x∗∈X:f↑(x, u)≥ hx∗, ui,for all u∈X}. Let us recall (see [4] or [9] for example) that the function fis called: •quasiconvex, if for all x, y ∈dom (f) f(z)≤max{f(x), f(y)},∀z∈[x, y] ; (1) •semistrictly quasiconvex, if for all x, y ∈dom(f) the following implication holds: f(x)< f(y)⇒f(z)< f(y), ∀z∈]x, y[ ; (2) •strictly quasiconvex, if for all x, y ∈dom (f) f(z)<max{f(x), f(y)},∀z∈]x, y[.(3) Let further T:X⇒X∗denote a multivalued operator with domain dom (T) := {x∈X:T(x)6=∅} and graph Gr (T) := {(x, x∗)∈X×X∗:x∗∈T(x)}. Let Abe a nonempty subset of X. The operator Tis called: •quasimonotone on A, if for all x1, x2∈A, all x∗ 1∈T(x1) and all x∗ 2∈T(x2) the following implication holds: hx∗ 1, x2−x1i>0⇒ hx∗ 2, x2−x1i ≥ 0. •semistrictly quasimonotone on A, if it is quasimonotone on Aand for all x1, x2∈Aand x∗ 1∈T(x1) we have hx∗ 1, x2−x1i>0 =⇒ ∃z∈]x1+x2 2, x2[,∃z∗∈T(z) : hz∗, x2−x1i>0. (4) 4 ARIS DANIILIDIS & YBOON GARCIA RAMOS •strictly quasimonotone on A, if it is quasimonotone on Aand for every x1, x2∈Awe have x16=x2=⇒ ∃z∈]x1, x2[,∃z∗∈T(z) : hz∗, x2−x1i 6= 0.(5) The definition of quasimonotonicity is classical (see [17], [4], [12], [9], for example) and is associated with the following result, which is a cornerstone of quasiconvex analysis (see [19], [21], [1] or [11, Theorem 2.1], for example). Theorem 1. Let f:X−→ R∪ {+∞} be a lower semicontinuous function. The following assertions are equivalent: (a) fis quasiconvex ; (b) ∂f is quasimonotone ; (c) for all x, y ∈dom(f) : ∃x∗∈∂f(x) : hx∗, y −xi>0⇒f(z)≤f(y), for all z∈[x, y]. The notions of semistrict/strict quasimonotonicity were first introduced in [18] as extensions of corresponding notions for functions (that is, singlevalued operators) considered in [16]. In this latter work ([16]) it is established that a differentiable semistrictly (respectively, strictly) quasiconvex functions is characterized by the semistrict (respectively, strict) quasimonotonicity of its derivatives. In [11] the aforementioned result is extended to the class of locally Lipschitz functions f, where (4) (respectively, (5)) is used to define the semistrict (respectively, strict) quasimonotonicity for the (multivalued) Clarke subdifferential ∂f. The proof, heavily based on the Lebourg Mean Value theorem (see [8], for example), leaves no hope for further extensions: indeed, in contrast to the classical definitions of monotonicity or quasimonotonicity, the considered definitions yield implicitly the nonemptiness of the operator Ton a dense subset of every segment [x1, x2]. Concurrently, outside the class of locally Lipschitz functions, the domain of the Clarke-Rockafellar subdifferential ∂f can easily be empty on whole lines. To establish a duality between semistrict quasiconvexity and semistrict quasimonotonicity beyond the Lipschitzian case, a different approach is adapted in [3]. That approach, inspired from a previous work of Borde and Crouzeix [7], consisted in replacing the subdifferential ∂f of fby the operator “normal cone to the sublevel sets” (denoted by Nf). In doing so, an application of the Hahn-Banach theorem recompenses the need of using an approximate Mean Value Theorem. As a result, the aforementioned duality is extended to the class of continuous functions in this new framework. The aim of this work is to show that an analogous duality scheme based on the notion of subdifferential is plausible, provided a variational adaptation of the notions defined by (4) and (5) to make them compatible with THE CLASS OF CONTINUOUS (SEMI-) STRICTLY QUASICONVEX FUNCTIONS 5 the approximate Mean Value theorem. In the last part of this work (cf. Corollary 8 and Proposition 9) we show how these new definitions relate to other notions of generalized monotonicity. 3. Main result The following notation will be used in the sequel. For every x1, x2∈X we set DT(x1, x2) := (6) ={z∈]x1, x2[: ∃(zn, z∗ n)n≥1⊂Gr(T),limnzn=z&hz∗ n, x2−zni>0}. The following notions will play a central role in this work. Definition 2. Let Abe a nonempty convex subset of X. An operator T:X⇒X∗is called (i) variationally semistrictly quasimonotone on A, if it is quasimonotone on Aand for every x1, x2∈Aand x∗ 1∈T(x1) we have hx∗ 1, x2−x1i>0 =⇒DT(x1, x2)∩]x1+x2 2, x2]6=∅; (7) (ii) variationally strictly quasimonotone on A, if it is quasimonotone on Aand for every x1, x2∈Athere exist z∈]x1, x2[ and δ > 0 such that for some i0∈ {1,2}and all z0∈B(z, δ) we have DT(z0, xi0)6=∅.(8) Remark 3. (i) Assuming (4) and taking zn:= zfor all n≥1 we see that (7) holds. Thus every semistrictly quasimonotone operator is variationally semistrictly quasimonotone. On the other hand, properties (5) and (8) are not directly comparable. Nevertheless, as we show in Corollary 8, strict (respectively, semistrict) quasimonotonicity and variational strict (respectively, semistrict) quasimonotonicity coincide for subdifferentials of locally Lipschitz functions. (ii) Variational strict quasimonotonicity implies variational semistrict quasimonotonicity. Indeed, let us assume hx∗ 1, x2−x1i>0 for some x1, x2∈A and x∗ 1∈T(x1). Setting w=x1+x2 2and applying (8) on the segment [w, x2] we deduce that for some z∈]w, x2[ and δ > 0 and for all z0∈B(z, δ) we either have DT(z0, x2)6=∅(thus in particular, DT(z, x2)6=∅, yielding DT(x1, x2)∩]w, x2]6=∅and we are done) or DT(z0, w)6=∅. In the second case we obtain a sequence {zn} −→ zwith z∗ n∈T(zn) and hz∗ n, w −zni>0. On the other hand, by quasimonotonicity we infer that hz∗ n, zn−x1i ≥ 0. Multiplying the first inequality by 2 and adding to the second one we obtain hz∗ n, x2−zni>0. Thus DT(w, x2)6=∅,which yields (7). 6 ARIS DANIILIDIS & YBOON GARCIA RAMOS We now show that the above variational definitions characterize the subdifferentials of the continuous semistrictly (respectively, strictly) quasiconvex functions. We shall need the following result concerning the class of continuous quasiconvex functions (see [4]). We include a short proof for the reader’s convenience. Proposition 4. Let f:X→R∪ {+∞} be a continuous quasiconvex function. Then fis semistrictly quasiconvex if, and only if, the set of local and global minimizers of fcoincide. Proof For the needs of this proof we denote by L - min f(respectively, G - min f) the set of local (respectively, global) minimizers of f. Let us first assume fis semistrictly quasiconvex and let us show that L - min f= G - min f(continuity is not needed for this implication). Let us assume, towards a contradiction, that there exists y∈L - min fand x∈Xwith f(y)> f(x).Then by quasiconvexity, the restriction of fto the segment [x, y] should be increasing near y. Since yis local minimum, this implies fis constant on [z, y] for some z∈]x, y[,which clearly contradicts (2). Let us now assume fis quasiconvex and continuous and L - min f= G - min f. If fwere not semistrictly quasiconvex, then we would have f(x)< f(z) = f(y), for some x, y ∈dom fand z∈]x, y[. Since ycannot be a local minimum of f, there exists (yn)→ywith f(yn)< f(y). Let t=kx−yk−1kz−ykand set xn=yn+1 t(z−yn).Using the quasiconvexity of f, we deduce from the relation f(z) = f(y)> f(yn) that f(xn)≥f(y). Since (xn)→xand f(x)< f(y) we obtain a contradiction to the continuity of fat x. ¤ The following result relates variational semistrict quasimonotonicity to semistrict convexity in the continuous case. Theorem 5. Let f:X→R∪{+∞} be a continuous function with a convex domain dom f. The following assertions are equivalent : (i) fis semistrictly quasiconvex ; (ii) for all x, y ∈dom fand x∗∈∂f(x)we have hx∗, y −xi>0⇒f(z)< f(y), for all z∈[x, y[ ; (iii) ∂f is variationally semistrictly quasimonotone on dom f. Proof Throughout the proof we set K= dom fand T=∂f. (i)=⇒(ii). Let x, y ∈Kand x∗∈∂f(x) with hx∗, y −xi>0.In view of (2), it is sufficient to show that f(x)< f(y).Assuming this is not the THE CLASS OF CONTINUOUS (SEMI-) STRICTLY QUASICONVEX FUNCTIONS 7 case, then by quasiconvexity, fhas to be constant on the segment [x, y] (cf. Theorem 1(c)). Applying [11, Lemma 2.1] we obtain that every z∈]x, y] is a local minimum of fwhile xis not a local minimum. Since f(x) = f(z), we obtain a contradiction to Proposition 4. (ii)=⇒(iii). Let us assume (ii) holds. Evoking again Theorem 1 [(c)→(b)] we obtain that ∂f is quasimonotone. Let us now assume x, y ∈Kand x∗∈∂f(x) be such that hx∗, y −xi>0.Then f(z)< f(y), for all z∈[x, y[. Taking znear ysuch that kz−yk<1 2kx−yk, and applying the approximate mean value theorem on the segment [z, y] (see [2, Corollary 4.3], for example) we obtain directly that DT(z, y)6=∅, thus DT(x, y)6=∅. This shows that ∂f is variationally semistrictly quasimonotone on K. (iii)=⇒(i). Let us assume (iii) holds. Then ∂f is in particular quasimonotone, thus fis quasiconvex. Let us assume, towards a contradiction, that fis not semistrictly quasimonotone. Then by Proposition 4, there exist x, y ∈Kwith f(x)< f(y) and yis a local minimum of f. Using this information and the continuity of f, we deduce that there exists δ, δ1>0 such that f(y0)≥f(y)> f(x0), for all x0∈B(x, δ) and y0∈B(y, δ1).(9) Set C= co(B(x, δ)∪ {y})\ {y}. Then (9) together with the quasiconvexity of fyield that fis constant on C∩B(y, δ1).Since the latter set is open, we deduce ∂f(y0) = {0}, for all y0∈C∩B(y, δ1).(10) We may also assume δ1>0 to be maximal with respect to the above property. Taking now any x1∈C\B(y, δ1) such that kx1−yk<2δ1 we have f(x1)< f(y). Applying the approximate mean value theorem ([2, Corollary 4.3]) to the segment [x1, y] we obtain a sequence (zn)−→ z∈ [x1, y[ with hz∗ n, y −zni>0. Taking nsufficiently large, we ensure that zn∈Cand kzn−yk<2δ1. Applying now the definition of semistrict quasimonotonicity (cf. relation (7)) to the segment [zn, y], we infer that DT(zn, y)∩B(y, δ1)6=∅. This clearly contradicts (10). ¤ Remark 6. As already mentioned, replacing variational semistrict quasimonotonicity by semistrict quasimonotonicity (cf. relation ((4)) in the statement of Theorem 5, does not lead to a full equivalence in the continuous case. The best partial result in this direction was recently established in [15, Theorem 7] (namely, (iii)=⇒(ii)⇐⇒(i)). We are now ready to state the second main result of this work, relating variational strict quasimonotonicity to strict convexity. 8 ARIS DANIILIDIS & YBOON GARCIA RAMOS Theorem 7. Let f:X→R∪{+∞} be a continuous function with a convex domain dom f. The following assertions are equivalent : (i) fis strictly quasiconvex ; (ii) ∂f is variationally strictly quasimonotone on dom f. Proof We set again K= dom fand T=∂f. (i)=⇒(ii). Since by Theorem 1 (b) we have that ∂f is quasimonotone, we need only show that (8) holds. To this end, let x1, x2∈Kand pick any z∈]x1, x2[. Using (3) we deduce that f(z)< f(xi0) for some i0∈ {1,2}. Since fis continuous, there exists δ > 0 such that for all z0∈B(z, δ) we have f(z0)< f(xi0). Applying the approximate mean value theorem ([2, Corollary 4.3]) on each segment [z0, xi0]we obtain directly that DT(z0, xi0 )6= ∅. (ii)=⇒(i). Assume ∂f is variationally strictly quasimonotone on dom f. Then by Remark 3 and Theorem 5 [(iii)→(i)] we deduce that fis semistrictly quasiconvex. Let us assume, towards a contradiction, that fis constant in a non-trivial segment [x1, x2] of Ktaking the value a∈Rthere. We deduce from (8) that there exist i0∈ {1,2}and (u, u∗)∈Gr ∂f such that hu∗, xi0−ui>0. In view of Theorem 5 (ii) this yields a=f(xi0)> f(u)≥inf f. Thus fdoes not attain its global minimum on the segment [x1, x2]. Let us denote by Sf(a) := {x∈X:f(x)≤a} the (closed convex) sublevel set of f. The above inequality together with Proposition 4 show that the interior of Sf(a) is nonempty and coincides with the strict sublevel set S− f(a) = {x∈X:f(x)< a}. It follows that the segment [x1, x2] is in the boundary of the open convex set S− f(a) and [x1, x2]∩S− f(a) = ∅.By the Hahn-Banach separation theorem we obtain a linear functional p∈X∗and β∈Rsuch that hp, zi=β > hp, yifor all z∈[x1, x2] and y∈S− f(a).Set U={x∈X:hp, xi> β}.Then Uis an open subset of X\Sf(a) containing the segment [x1, x2] in its closure. Let now z∈]x1, x2[, δ > 0 and i0∈ {1,2}be given by (8) applied to the segment [x1, x2] and let us define C= co [(B(z, δ)∩U)∪ {xi0}]. For any z0∈B(z, δ)∩U, we infer from (8) that DT(z0, xi0)6=∅, which in view of (7) yields the existence of some u∈C\{xi0}and u∗∈∂f(u) satisfying hu∗, xi0−ui>0. It follows from Theorem 5(ii) that a= THE CLASS OF CONTINUOUS (SEMI-) STRICTLY QUASICONVEX FUNCTIONS 9 f(xi0)> f(u). On the other hand, it is easily seen that C\ {xi0} ⊂ U, thus f(u)> a, which is a contradiction. ¤ A direct consequence of the above characterizations is the following result. Corollary 8. Let T=∂f for some locally Lipschitz function f(defined on a nonempty convex subset Aof X). Then (i) Tis semistrictly quasimonotone (on the set A)if and only if it is variationally semistrictly quasimonotone (on the set A).; (ii) Tis strictly quasimonotone (on the set A)if and only if it is variationally strictly quasimonotone (on the set A). Proof (i) It follows from the observation that both notions of semistrict quasimonotonicity and of variational semistrict quasimonotonicity characterize the semistrict quasiconvexity of fin the locally Lipschitz case (cf. Theorem 5 and [11, Theorem 3.2]). (ii) Similarly, if fis locally Lipschitz, then both notions of strict and of variational strict quasimonotonicity characterize the strict quasiconvexity of the function (cf. Theorem 7 and [11, Theorem 4.1]). ¤ Let us finally see how the variational semistrict quasimonotonicity relates to the concept of proper quasimonotonicity. We recall from [10, Definition 4.2] that an operator T:X⇒X∗is called •properly quasimonotone on a convex subset Aof X, if for every {x1, x2, ..., xk} ⊂ Aand every y∈co{xj}j∈Nk, there exists i∈Nk such that ∀x∗ i∈T(xi),hx∗ i, y −xii ≤ 0.(11) It is sufficient to take k= 2 and y=x1+x2 2to see that every properly quasimonotone operator is quasimonotone. The converse implication (being in general false) is true if either X=Ror T=∂f for some continuous function fwhich has to be quasiconvex (see [10] for details). In [11, Proposition 5.1] it is shown that any semistrictly quasimonotone operator is properly quasimonotone. Let us now show that the same happens for any variationally semistrictly quasimonotone operator. Proposition 9. Let Abe a nonempty convex subset of Xand T:X⇒X∗. If Tis variationally semistrictly quasimonotone on Athen it is also properly quasimonotone on A. Proof Let as assume that Tis variationally semistrictly quasimonotone on Aand not properly quasimonotone there. Then there exist {x1, x2, ...xk} ⊂