Journal of Convex Analysis Volume 2 (1995), No.1/2, 167–172

Quasi-convex Functions and Quasi-monotone Operators

Vladimir L. Levin^{1}

Central Economics and Mathematics Institute, Russian Academy of Sciences, Krasikova St 32, Moscow 117418, Russia. e-mail: vl levin@cemi.msk.su

Received 7 April 1994 Revised manuscript received 17 October 1994

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

The notions of a quasi-monotone operator and of a cyclically quasi-monotone operator are introduced, and relations between such operators and quasi-convex functions are established.

Keywords : quasi-convex function, monotone and cyclically monotone operators, quasi-monotone and cyclically quasi-monotone operators, revealed preference axioms in mathematical economics

1991 Mathematics Subject Classification: 26A51, 26E15, 47H05, 90A40, 90C26

1. Introduction

Let E be a Hausdorff locally convex space, X a convex set in it, and E^{∗} the dual space. We say an operator f : X → E^{∗} is quasi-monotone if

min{ ⟨y − x, f(x)⟩, ⟨x − y, f(y)⟩ } ≤ 0  (1.1)

for all x, y ∈ X, and cyclically quasi-monotone if

min{ ⟨x_{i+1} − x_{i}, f(x_{i})⟩ : i = 0, …, k } ≤ 0  (1.2)

for all integer k and all cycles x_{0}, x_{1}, …, x_{k}, x_{k+1} = x_{0} in X. Such operators are closely related to the so-called demand functions in mathematical economics [4]. Denote X = intIR_{+}^{n} and suppose that there exists the single solution d(p) for the extremal problem

u(q) → max, pq ≤ 1,

where an increasing utility function u on IR_{+}^{n} is assumed to be given, and a price vector p ∈ X is considered as a parameter. The demand function d, showing demand for n products

1 I thank the International Science Foundation and the George Soros Cultural Initiative Foundation for their support in part of the research presented in this publication.

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

168 V. L. Levin / Quasi-convex functions and quasi-monotone operators

as a vector function of their prices, satisfies the strong axiom of revealed preference due to Houthakker: no cycle p^{0}, p^{1}, …, p^{k}, p^{k+1} = p^{0} can exist in X such that

(p^{i+1} − p^{i})d(p^{i}) ≤ 0, i = 0, 1, …, k,

and d(p^{i}) ≠ d(p^{j}) for at least one pair of indices i, j = 0, …, k with i ≠ j. The same condition for k = 1 only is known as the weak axiom of revealed preference due to Samuelson. It is easily seen that each axiom implies the corresponding quasi-monotonicity property for the operator f = −d : X → IR^{n}, the strong axiom implies (1.2), and the weak axiom implies (1.1). The simplest examples of quasi-monotone (resp. cyclically quasi-monotone) operators are monotone (resp. cyclically monotone) ones. Their definitions are obtained by replacing minima with sums in (1.1) and (1.2) respectively. The notion of a (not necessarily single-valued) monotone operator was first proposed by Kachurovskii [1] (see also [2, 3]), and properties and applications of such operators were studied later by many authors. Cyclically monotone operators were introduced and investigated by Rockafellar [6–9]. Given a smooth function u on a convex domain, characterizations of its convexity in terms of monotonicity or cyclical monotonicity of gradu are known as follows:

u is convex ⇔ gradu is monotone ⇔ gradu is cyclically monotone.

The goal of the present paper is to get similar characterization theorems connecting quasiconvex functions with quasi-monotone and cyclically quasi-monotone operators.

2. Characterization theorems

Let X be a convex set in a real vector space. Recall that a function u : X → IR^{1} is said to be quasi-convex if its sublevel sets

{ x : u(x) ≤ α }, α ∈ IR^{1},

are convex or, which is the same thing, if

u((1 − t)x + ty) ≤ max{u(x), u(y)}

whenever x, y ∈ X, 0 < t < 1. It follows from this definition that u is quasi-convex if and only if all the functions φ(u, x, y; ·), x, y ∈ X, on the segment [0, 1] are so, where

φ(u, x, y; t) : = u((1 − t)x + ty).  (2.1)

Theorem 2.1. Let X be a convex open set in a Hausdorff locally convex space E, and suppose that a function u : X → IR^{1} has two properties as follows:

(i) u is Gâteaux differentiable on X, i.e. for every x ∈ X there exists an element gradu(x) ∈ E^{∗} such that

lim_{t→0} \frac{u(x + th) − u(x)}{t} = ⟨h, gradu(x)⟩ for all h ∈ E;  (2.2)

(ii) for every x, y ∈ X the function φ(u, x, y; ·) given by (2.1) is absolutely continuous on

[0, 1]. The following assertions are then equivalent:

(a) u is quasi-convex,

(b) the operator gradu is cyclically quasi-monotone,

(c) the operator gradu is quasi-monotone.

Remark 2.2. Assumptions (i) and (ii) are clearly satisfied if u is C^{1}. For the finitedimensional case of the theorem, see also [5, Proposition 3.1].

Before to pass on to a more general characterization theorem, let us formulate two assumptions, (D1) and (D2), on a function u : X → IR^{1}, where X is a convex set in a vector space. The assumptions are expressed in terms of the functions φ(u, x, y; ·) (see (2.1)) as follows: (D1) for every x, y ∈ X and every t, 0 ≤ t < 1, there exists the right derivative

Dφ(u, x, y; t) : = lim_{Δt↓0} \frac{φ(u, x, y; t + Δt) − φ(u, x, y; t)}{Δt};

(D2) for every x, y ∈ X, φ(u, x, y; ·) is absolutely continuous on [0, 1]. It follows from (D1) and (D2) that

∫_{0}^{1} Dφ(u, x, y; t) dt = u(y) − u(x) whenever x, y ∈ X.  (2.3)

Note that if (D1) holds, then for every x, y ∈ X the directional derivative is defined as follows:

u′(x, y − x) := Dφ(u, x, y; 0) = lim_{t↓0} \frac{u(x + t(y − x)) − u(x)}{t}.  (2.4)

Theorem 2.3. Let X be a convex subset in a vector space and u : X → IR^{1} satisfy (D1) and (D2). The following assertions are then equivalent:

(a) u is quasi-convex;

(b) for every integer k and every cycle x_{0}, x_{1}, …, x_{k}, x_{k+1} = x_{0} in X, the inequality

min{u′(x_{i}, x_{i+1} − x_{i}) : i = 0, …, k} ≤ 0

holds;

(c) for every x, y ∈ X, the inequality

min{u′(x, y − x), u′(y, x − y)} ≤ 0

holds.

Remark 2.4. Similarly to the case of cyclically monotone operators, the notion of cyclical quasi-monotonicity can be generalized in the natural way on multivalued operators. A well-known result of Rockafellar [6,9] asserts that subdifferentials of proper semi-continuous convex functions are characterized as maximal cyclically monotone operators. Here a multivalued cyclically monotone (resp. cyclically quasi-monotone) operator f is called maximal if no cyclically monotone (resp. cyclically quasi-monotone) operator g exists with grf ⊂ grg. This Rockafellar’s characterization theorem cannot be generalized on quasi-convex functions, because for any (single-valued) cyclically quasi-monotone operator f, the operator g(x) := {αf(x) : α ≥ 0} is cyclically quasi-monotone as well, and grf ⊂ grg provided f ≢ 0. It follows that for every non-constant smooth quasiconvex function u the single-valued cyclically quasi-monotone operator f = gradu is not maximal.

3. Proofs

Proof of Theorem 2.1 Observe that if u is Gâteaux differentiable on X, then (D1) holds and u′(x, y − x) = ⟨y − x, gradu(x)⟩ for all x, y ∈ X. Theorem 2.1 is then a direct consequence of Theorem 2.3.

Proof of Theorem 2.3 (a)⇒(b). If (b) fails, then for some cycle x_{0}, x_{1}, …, x_{k+1} = x_{0} in X,

u′(x_{i}, x_{i+1} − x_{i}) > 0, i = 0, 1, …, k.

We have Dφ(u, x_{i}, x_{i+1}; 0) > 0, so

φ(u, x_{i}, x_{i+1}; 0) < φ(u, x_{i}, x_{i+1}; t) for small t > 0,  (3.1)

and as φ(u, x_{i}, x_{i+1}; ·) is quasi-convex on [0, 1], it follows from (3.1) that

φ(u, x_{i}, x_{i+1}; 0) < φ(u, x_{i}, x_{i+1}; 1),

i.e. u(x_{i}) < u(x_{i+1}). We obtain a contradictory chain of inequalities

u(x_{0}) < u(x_{1}) < … < u(x_{k}) < u(x_{0}),

and the contradiction means that (b) is true. (b)⇒(c). Obvious. (c)⇒(a). Suppose u is not quasi-convex. There exist then x, y ∈ X and t_{0}, 0 < t_{0} < 1, such that

u((1 − t_{0})x + t_{0}y) > max{u(x), u(y)}.  (3.2)

We claim that there exist t_{1} and t_{2}, 0 < t_{1} < t_{0} < t_{2} < 1, such that

Dφ(u, x, y; t_{1}) > 0  (3.3)

and

Dφ(u, y, x; 1 − t_{2}) > 0.  (3.4)

Indeed, if Dφ(u, x, y; t) ≤ 0 for all t, 0 < t < t_{0}, then, taking into account (2.3) and the identity

φ(u, x, (1 − t_{0})x + t_{0}y; t) = φ(u, x, y; t_{0}t),

we obtain

u((1 − t_{0})x + t_{0}y) = u(x) + ∫_{0}^{1} Dφ(u, x, (1 − t_{0})x + t_{0}y; t) dt

= u(x) + ∫_{0}^{1} Dφ(u, x, y; t_{0}t) dt

= u(x) + \frac{1}{t_{0}} ∫_{0}^{t_{0}} Dφ(u, x, y; τ) dτ ≤ u(x),

which contradicts (3.2). Similarly, if Dφ(u, y, x; t) ≤ 0 for all t, 0 < t < 1 − t_{0}, then

u((1 − t_{0})x + t_{0}y) = u(y) + ∫_{0}^{1} Dφ(u, y, (1 − t_{0})x + t_{0}y; t) dt

= u(y) + ∫_{0}^{1} Dφ(u, y, x; (1 − t_{0})t) dt

= u(y) + \frac{1}{1 − t_{0}} ∫_{0}^{1−t_{0}} Dφ(u, y, x; τ) dτ ≤ u(y),

which again contradicts (3.2). The claim is thus proved. Set now

x_{k} := (1 − t_{k})x + t_{k}y, k = 1, 2,

and, by using (3.3) (3.4) and the identities

\begin{aligned}φ(u, x_{1}, x_{2}; t) & = φ(u, x, y; t_{1} + t(t_{2} − t_{1})), \\ φ(u, x_{2}, x_{1}; t) & = φ(u, y, x; 1 − t_{2} + t(t_{2} − t_{1})), \end{aligned}

one obtains

\begin{aligned}u′(x_{1}, x_{2} − x_{1}) & = Dφ(u, x_{1}, x_{2}; 0) = (t_{2} − t_{1}) Dφ(u, x, y; t_{1}) > 0, \\ u′(x_{2}, x_{1} − x_{2}) & = Dφ(u, x_{2}, x_{1}; 0) = (t_{2} − t_{1}) Dφ(u, y, x; 1 − t_{2}) > 0, \end{aligned}

hence

min{u′(x_{1}, x_{2} − x_{1}), u′(x_{2}, x_{1} − x_{2})} > 0,

a contradiction with (c).

Remark : After submitting the present paper, in November 1994, I have seen a manuscript by Aussel, Corvellec and Lassonde [10], where some related results on connections between (non-differentiable) quasi-convex functions and multivalued quasi-monotone operators in Banach spaces are proved in a different way.

References

[1] R. I. Kachurovskii : On monotone operators and convex functionals, Uspekhi Matem. Nauk, 1960, Vol. 15, 4, 213–215 ; Uchenye Zapiski Moskovskogo Oblastn. Pedagog. Inst. 1962, 231–243, Russian

[2] R. I. Kachurovskii : Non-linear operators of bounded variation, monotone and convex operators in Banach spaces, Uspekhi Matem. Nauk, 1966, Vol. 21, 5, 256–257, Russian

[3] R. I. Kachurovskii : Non-linear monotone operators in Banach spaces, Uspekhi Matem. Nauk, 1968, Vol. 23, 2, 121–168, Russian

[4] S. Karlin : Mathematical Methods and Theory in Games, Programming, and Economics, Pergamon Press, London–Paris, 1959

[5] V. L. Levin : Reduced cost functions and their applications, Journal of Mathematical Economics (to appear)

[6] R. T. Rockafellar : Characterization of the subdifferentials of convex functions, Pacific J. Math., 1966, Vol. 17, 497–510

[7] R. T. Rockafellar : Convex functions, monotone operators and variational inequalities, in: Theory and Applications of Monotone Operators, A. Ghizzetti, 1969, 35–65 Tipografia Oderisi Editrice, Gubbio Italy

[8] R. T. Rockafellar : Convex Analysis, Princeton University Press, 1970

[9] R. T. Rockafellar : On the maximal monotonicity of subdifferential mappings, Pacific J. Math, 1970, Vol. 33, 209–216

[10] D. Aussel, J.-N. Corvellec, M. Lassonde : Subdifferential characterization of quasiconvexity and convexity, Journal of Convex Analysis, 1994, Vol. 1, No. 2, 195–201.