Journal of Convex Analysis Volume 1 (1994), No. 2, 195–201

Subdifferential Characterization of Quasiconvexity and Convexity

Didier Aussel

Mathématiques Appliquées, Université Blaise Pascal, Clermont-Ferrand, F-63177 Aubière Cedex, France. e-mail: aussel@ucfma.univ-bpclermont.fr

Jean-Noël Corvellec

Mathématiques, Université de Perpignan, F-66860 Perpignan Cedex, France. e-mail: corvellec@syspo.univ-perp.fr

Marc Lassonde

Mathématiques, Université des Antilles et de la Guyane, F-97159 Pointe-à-Pitre Cedex, Guadeloupe, France. e-mail: lassonde@univ-ag.fr

Received 4 February 1994 Let f : X → IR ∪ {+∞} be a lower semicontinuous function on a Banach space X. We show that f is quasiconvex if and only if its Clarke subdifferential ∂f is quasimonotone. As an immediate consequence, we get that f is convex if and only if ∂f is monotone.

1. Introduction

It is a very natural question in nonsmooth analysis to search for a characterization of the convexity of functions in terms of the monotonicity of their subdifferential operators. In recent years, several contributions to this question have been made using the Clarke notion of subdifferentiability. Let us just mention Clarke for locally Lipschitz functions on Banach spaces [1], Poliquin for lower semicontinuous functions on finite dimensional spaces [10], Correa-Jofré-Thibault for lower semicontinuous functions on reflexive Banach spaces [2] and on (arbitrary) Banach spaces [3]. Except in Poliquin [10], the technique of proof is based on a mean value theorem. Now another natural question arises: does there exist an analogous characterization for quasiconvex functions? In his thesis [5], Hassouni introduced the notion of a quasimonotone operator, and proved that a locally Lipschitz function on a separable Banach space is quasiconvex if and only if its subdifferential is quasimonotone. There again the proof relies on a mean value theorem. The object of this note is twofold. First, we extend Hassouni’s characterization of quasiconvexity to the general case of lower semicontinuous functions on (arbitrary) Banach

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

196 D. Aussel, J.-N. Corvellec, M. Lassonde / Subdifferential characterization

spaces (Theorem 4.1). The result appears to be an almost immediate application of Zagrodny’s approximate mean value theorem [13] (the first use of this theorem in the study of monotonicity goes back to Correa-Jofré-Thibault [2]). The key idea is to deal with a more natural (though equivalent) definition of a quasimonotone operator taken from Karamardian-Schaible [7]. Next, we show that the convex situation can be readily recovered from the quasiconvex situation (Theorem 4.3). This relies on an elementary characterization of the convexity of functions in terms of the quasiconvexity of their linear perturbations, and an analogous characterization of the monotonicity of operators (Proposition 2.1). Thus, our approach provides a significant simplification of the proof of Correa-Jofré-Thibault’s result [3], as well as a new insight on the relationships between convexity, quasiconvexity, monotonicity and quasimonotonicity. The first draft of this paper was conceived in January 1993 while the last two authors were still working in the Université Blaise Pascal. The draft was widely distributed and the results were discussed at various places throughout 1993. During that time, we learned that D. T. Luc independently obtained the quasiconvex–quasimonotone characterization (Theorem 4.1) in [8], via the same method. On the same occasion we also learned of another paper of Luc [9] dealing with the convex–monotone case (Theorem 4.3). However, in these papers the link between the two cases is not evidenced.

2. Convexity and monotonicity

Throughout this note, X stands for a real Banach space with norm ∥.∥, X^{∗} for its topological dual, and ⟨., .⟩ for the duality pairing. For u, v ∈ X, we let [u, v] = { x ∈ X | x = λu + (1 − λ)v for some λ ∈ [0, 1] }, ]u, v] = [u, v] \ {u}, [u, v[= [u, v] \ {v}, and ]u, v[= [u, v]\{u, v}; given λ > 0, we set B_{λ}([u, v]) = { x ∈ X | ∥x−y∥ < λ for some y ∈ [u, v] }.

Given a function f : X → IR ∪ {+∞}, the effective domain of f is denoted by domf = {u ∈ X | f(u) ∈ IR}. We recall that f is convex if

u, v ∈ domf, w = λu + (1 − λ)v ∈ [u, v] ⟹ f(w) ≤ λf(u) + (1 − λ)f(v),

and quasiconvex if

u, v ∈ domf, w ∈ [u, v] ⟹ f(w) ≤ max{f(u), f(v)}.

Let now A : X → X^{∗} be a multi-valued operator; the domain of A is domA = {u ∈ X | A(u) ≠ ∅}. The operator A is said to be monotone if

u^{∗} ∈ A(u), v^{∗} ∈ A(v) ⟹ ⟨v^{∗} − u^{∗}, v − u⟩ ≥ 0,

and quasimonotone (see [7]) if

u^{∗} ∈ A(u), v^{∗} ∈ A(v) and ⟨u^{∗}, v − u⟩ > 0 ⟹ ⟨v^{∗}, v − u⟩ ≥ 0.

Obviously, convex functions are quasiconvex and monotone operators are quasimonotone. The precise relation between convexity and quasiconvexity, monotonicity and quasimonotonicity is given in the following:

Proposition 2.1.

(i) A function f : X → IR ∪ {+∞} is convex if and only if for each α ∈ X^{∗} the function u ↦ f(u) + ⟨α, u⟩ is quasiconvex.

(ii) An operator A : X → X^{∗} is monotone if and only if for each α ∈ X^{∗} the operator u ↦ A(u) + α is quasimonotone.

Proof. (i) This property is well known (see for instance Crouzeix [4]), however, for the sake of comparison with the next property, we include the easy proof. Obviously, if f is convex, then for each α ∈ X^{∗} the function f + α is convex, hence quasiconvex. To prove the converse, let u, v be arbitrary points in domf, and choose α ∈ X^{∗} such that

⟨α, u − v⟩ = f(v) − f(u).

Since f + α is quasiconvex, for any w = v + λ(u − v) with λ ∈ [0, 1], it holds

\begin{aligned}(f + α)(v) ≥ (f + α)(w) & = f(w) + λ⟨α, u − v⟩ + ⟨α, v⟩ \\ & = f(w) + λ(f(v) − f(u)) + ⟨α, v⟩, \end{aligned}

which gives f(w) ≤ f(v) + λ(f(u) − f(v)).

(ii) If A is monotone, then for each α ∈ X^{∗} the operator u ↦ A(u) + α is obviously monotone, hence quasimonotone. To prove the converse, let u, v in domA with u ≠ v, let u^{∗} ∈ A(u), v^{∗} ∈ A(v), and let ε > 0 . Choose α ∈ X^{∗} such that

⟨u^{∗} + α, v − u⟩ = ε > 0.

Since u ↦ A(u) + α is assumed to be quasimonotone, this inequality implies that ⟨v^{∗} + α, v−u⟩ ≥ 0, or equivalently ⟨v^{∗}, v−u⟩ ≥ −⟨α, v−u⟩ = ⟨u^{∗}, v−u⟩−ε, i.e. ⟨v^{∗}−u^{∗}, v−u⟩ ≥ −ε. Since ε can be arbitrarily small, we conclude that A is monotone.

Remark 2.2. The definition of quasimonotone operator used in this note is taken from Karamardian-Schaible [7] (where only single-valued operators are considered). Part (ii) of Proposition 2.1 is given in Hassouni [6] but with a different definition of quasimonotone operator. However, it can be shown that both definitions are equivalent. Our approach is the natural way to establish the result.

3. Properties of the subdifferential

Let f : X → IR ∪ {+∞} be a lower semicontinuous function. The Clarke subdifferential of f is the operator ∂f : X → X^{∗} defined for each u ∈ X by

∂f(u) = \{ \begin{matrix}\{u^{∗} ∈ X^{∗} | ⟨u^{∗}, v⟩ ≤ f^{↑}(u; v) ∀v ∈ X\} & if u ∈ domf \\ ∅ & if u ∉ domf, \end{matrix}

where

f^{↑}(u; v) = sup_{ε>0} inf_{γ>0 ; {δ>0 \atop λ>0}} sup_{x∈B_{γ}(u) ; {f(x)≤f(u)+δ \atop t∈ ]0,λ[}} inf_{y∈B_{ε}(v)} \frac{f(x + ty) − f(x)}{t}

is the Rockafellar directional derivative (see [1,11]).

Among the properties of this subdifferential operator, we quote those we shall need in the sequel:

(a) For each u ∈ domf, the value ∂f(u) depends only on the values of f in some neighborhood of u,

(b) If α ∈ X^{∗}, then ∂(f + α)(u) = ∂f(u) + α for each u ∈ domf,

(c) The operator ∂f satisfies an approximate mean value estimate (see Zagrodny [13]): for any a, b ∈ domf, a ≠ b, there exist x ∈ [a, b[ and sequences (x_{k}) in dom ∂f, (x_{k}^{∗}) in X^{∗} with x_{k} → x and x_{k}^{∗} ∈ ∂f(x_{k}), such that

f(b) − f(a) ≤ \frac{∥b − a∥}{∥b − x∥} lim inf_{k→+∞} ⟨x_{k}^{∗}, b − x_{k}⟩,

and

f(b) − f(a) ≤ lim inf_{k→+∞} ⟨x_{k}^{∗}, b − a⟩.

Our results will be deduced from the following lemma, which is a consequence of the above mentioned mean value property.

Lemma 3.1. Let f : X → IR ∪ {+∞} be a lower semicontinuous function on a Banach space X. Let u, v, w ∈ X with v ∈ [u, w] and f(v) > f(u), and let λ > 0. Then, there exist x̄ ∈ dom ∂f and x̄^{∗} ∈ ∂f(x̄) such that

x̄ ∈ B_{λ}([u, v])  and  ⟨x̄^{∗}, w − x̄⟩ > 0.

Proof. Let r ∈ IR be such that f(u) < r ≤ f(v). The function h : X → IR ∪ {+∞} defined by

h(x) = \{ \begin{matrix}f(x) & if x ≠ v \\ r & if x = v \end{matrix}

is lower semicontinuous, finite in u and v, and ∂h(x) = ∂f(x) for all x ≠ v. According to Zagrodny’s approximate mean value theorem applied to the function h on the segment [u, v] there exist x̄ ∈ B_{λ}([u, v]) with x̄ ≠ v and x̄^{∗} ∈ ∂h(x̄) = ∂f(x̄) such that

⟨x̄^{∗}, v − x̄⟩ > 0 and ⟨x̄^{∗}, v − u⟩ > 0.

We conclude that

⟨x̄^{∗}, w − x̄⟩ = ⟨x̄^{∗}, w − v⟩ + ⟨x̄^{∗}, v − x̄⟩ = \frac{∥v − w∥}{∥v − u∥}⟨x̄^{∗}, v − u⟩ + ⟨x̄^{∗}, v − x̄⟩ > 0.

4. The characterizations

The following are our main results.

Theorem 4.1. Let f : X → IR∪{+∞} be a lower semicontinuous function on a Banach space X. Then, ∂f is quasimonotone if and only if f is quasiconvex.

Proof. We first show that if f is not quasiconvex then ∂f is not quasimonotone: assume that there are some u, v, w ∈ X with v ∈ ]u, w[ and f(v) > max{f(u), f(w)}. Let λ > 0 be such that f(x) > max{f(u), f(w)} for all x ∈ B_{λ}(v). According to Lemma 3.1, there exist x̄ ∈ dom ∂f and x̄^{∗} ∈ ∂f(x̄) such that

x̄ ∈ B_{λ}([u, v]) and ⟨x̄^{∗}, w − x̄⟩ > 0.  (4.1)

We claim that ]x̄, w] ∩ B_{λ}(v) is not empty. This is clear if ∥x̄ − v∥ < λ ; otherwise, any nearest point P x̄ to x̄ in [u, v] is different from v (because ∥x̄ − P x̄∥ < λ) so that v = tP x̄ + (1 − t)w for some 0 ≤ t < 1 and then the point z̄ = tx̄ + (1 − t)w belongs to ]x̄, w] ∩ B_{λ}(v). Fix z̄ ∈ ]x̄, w] ∩ B_{λ}(v). It follows from (4.1) that ⟨x̄^{∗}, y − x̄⟩ > 0 for every y ∈ [z̄, w], so there exists λ′ > 0 such that

⟨x̄^{∗}, y − x̄⟩ > 0 for all y ∈ B_{λ′}([z̄, w]).  (4.2)

Since f(z̄) > f(w), applying the lemma again we find ȳ in dom ∂f and ȳ^{∗} in ∂f(ȳ) such that

ȳ ∈ B_{λ′}([z̄, w]) and ⟨ȳ^{∗}, x̄ − ȳ⟩ > 0.

But ⟨x̄^{∗}, ȳ − x̄⟩ > 0 according to (4.2), which shows that ∂f is not quasimonotone.

Conversely, let us assume that f is quasiconvex and let us show that ∂f is quasimonotone. Let u^{∗} ∈ ∂f(u), v^{∗} ∈ ∂f(v) with ⟨u^{∗}, v−u⟩ > 0. We need only verify that f^{↑}(v; u−v) ≤ 0. Let us fix ε > 0 and γ ∈ ]0, ε[ such that

⟨u^{∗}, y − u⟩ > 0 for all y ∈ B_{γ}(v).

Now, fix y ∈ B_{γ}(v). Since f^{↑}(u; y − u) > 0 we can find ε′ ∈ ]0, ε − γ[, x ∈ B_{ε′}(u) and τ ∈ ]0, 1[ such that f(x + τ(y − x)) > f(x). From the quasiconvexity of f we infer that f(x) < f(y), whence

f(y + t(x − y)) ≤ f(y) for each t ∈ ]0, 1[,

so that

inf_{ω∈B_{ε}(u−v)} \frac{f(y + tω) − f(y)}{t} ≤ \frac{f(y + t(x − y)) − f(y)}{t} ≤ 0 for each t ∈ ]0, 1[.

Summing up, for any ε > 0 there exists γ > 0 such that

sup_{{y∈B_{γ}(v) \atop t∈ ]0,1[}} [ inf_{ω∈B_{ε}(u−v)} \frac{f(y + tω) − f(y)}{t}] ≤ 0,

which shows that f^{↑}(v; u − v) ≤ 0.

Remark 4.2. In the special case where f is locally Lipschitz and X is a separable Banach space, the characterization of Theorem 4.1 was established by Hassouni [5].

As an immediate consequence of Theorem 4.1 and Proposition 2.1, we obtain a subdifferential characterization of convexity:

Theorem 4.3. Let f : X → IR∪{+∞} be a lower semicontinuous function on a Banach space X. Then, ∂f is monotone if and only if f is convex.

Proof. The operator ∂f is monotone if and only if for each α ∈ X^{∗} the operator u ↦ ∂f(u) + α = ∂(f + α)(u) is quasimonotone. According to Theorem 4.1, this is equivalent to: for each α ∈ X^{∗} the function f + α is quasiconvex, i. e., f is convex.

Remark 4.4. Theorem 4.3 is due to Correa-Jofré-Thibault [3]. Special cases were previously established by Poliquin [10] (finite dimensional space) and by Correa-Jofré-Thibault [2] (reflexive Banach space). Though indirect, our approach proves to be more efficient.

The authors are grateful to one anonymous referee for pointing out that Theorem 4.1 (only if part) and Theorem 4.3 also hold for any presubdifferential (in the sense of Thibault-Zagrodny [12]) and hence for the Fréchet subdifferential in reflexive Banach spaces, the proximal subdifferential in Hilbert spaces, and the limiting subdifferentials associated with them. Indeed, it has been observed in [12] (see also [3]) that Zagrodny’s approximate mean value theorem still holds for any presubdifferential.

References

[1] F. H. Clarke: Optimization and Nonsmooth Analysis, Wiley-Interscience, New-York, 1983, pp. 308.

[2] R. Correa, A. Jofré, and L. Thibault: Characterization of lower semicontinuous convex functions, Proc. Amer. Math. Soc. 116 (1992), 67–72.

[3] R. Correa, A. Jofré, and L. Thibault: Subdifferential monotonicity as characterization of convex functions, Numer. Funct. Anal. Optim. 15 (1994), 531–535.

[4] J.-P. Crouzeix: Contributions à l’étude des fonctions quasi-convexes, Thèse d’État, Université de Clermont-Ferrand II, 1977, pp. 231.

[5] A. Hassouni: Sous-différentiels des fonctions quasi-convexes, Thèse de 3^{e} Cycle, Université Paul Sabatier, 1983, pp. 68.

[6] A. Hassouni: Quasimonotone multifunctions; applications to optimality conditions in quasiconvex programming, Numer. Funct. Anal. Optim. 13 (1992), 267–275.

[7] S. Karamardian, S. Schaible: Seven kinds of monotone maps, J. Optim. Theory Appl. 66 (1990), 37–46.

[8] D. T. Luc: Characterizations of quasiconvex functions, Bull. Austral. Math. Soc. 48 (1993), 393–406.

[9] D. T. Luc: On the maximal monotonicity of subdifferentials, Acta Math. Vietnam. 18 (1993), 99–106.

[10] R. A. Poliquin: Subgradient monotonicity and convex functions, Nonlinear Anal. 14 (1990), 305–317.

[11] R. T. Rockafellar: Generalized directional derivatives and subgradients of nonconvex functions, Canad. J. Math. 32 (1980), 257–280.

[12] L. Thibault, D. Zagrodny: Integration of subdifferentials of lower semicontinuous functions on Banach spaces, J. Math. Anal. Appl. 189 (1995), No. 1, 33–58.

[13] D. Zagrodny: Approximate mean value theorem for upper subderivatives, Nonlinear Anal. 12 (1988), 1413–1428.