Journal of Convex Analysis Volume 4 (1997), No. 1, 1–25

C-Minimal Pairs of Compact Convex Sets

D. Pallaschke

Institut für Statistik und Mathematische Wirtschaftstheorie, Universität Karlsruhe, Kaiserstr. 12, D-76128 Karlsruhe, Germany. e-mail: lh09@dkauni2.bitnet

W. Urbańska

Poznań University of Technology, Department of Mathematics, Piotrowo 3a, PL-60965 Poznań, Poland.

R. Urbański

Faculty of Mathematics and Computer Science, Adam Mickiewicz University, Matejki 48/49, PL-60-769 Poznań, Poland.

Received July 11, 1995 Revised manuscript received April 4, 1996

Pairs of compact convex sets naturally arise in quasidifferential calculus as a sub- and superdifferentials of a quasidifferentiable function (see [1]). Since the sub- and superdifferential are not uniquely determined, minimal representations are of special importance. For the 2-dimensional case, equivalent minimal pairs of compact convex sets are uniquely determined up to translations (see [3], [14]). For the 3-dimensional case, this is not longer true. J. Grzybowski [3] gave an example of finitely many equivalent minimal pairs of compact convex sets which are not connected by translations. A continuous family of equivalent minimal pairs of compact convex sets which are not connected by translation for different indices is given in [9]. In a recent paper R. Urbański [16] investiged the mimimality of pairs of compact convex sets which satisfy additional conditions, namely the minimal convex pairs. This paper is a continuation of this research direction. Here we study the minimality under a different type of conditions. Moreover we give a definition of a “convex hull” of a pair of sets.

Keywords: Pairs of convex sets, sublinear function, quasidifferential calculus

1991 Mathematics Subject Classification: 52A07, 26A27, 90C30.

1. Introduction

In this paper we consider the Rådström-Hörmander lattice [4] of equivalence classes of pairs of nonempty compact convex sets and investigate minimal representants which satisfy additional conditions. As in [6] we denote for a real topological vector space X the set of all nonempty compact convex subsets by K(X) and the set of all pairs of nonempty compact convex subsets by K^{2}(X), i.e. K^{2}(X) = K(X) × K(X). The equivalence relation between pairs of compact convex sets is given by: “(A, B) ∼ (C, D) if and only if A + D = B + C” using the Minkowski-sum, and a partial order is given by the relation: “(A, B) ≤ (C, D) if and only if A ⊆ C and B ⊆ D.” The space K^{2}(X) has been

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

investigated in series of papers, (see for instance [3], [6], [7], [8], [9], [14], [16]). Pairs of compact convex sets arise in quasidifferential calculus as the sub- and superdifferentials of the directional derivative of a quasidifferentiable function (see [1], [13]). Let us first set some notations: Let X be a real topological vector space, and X^{∗} be the space of all continuous real valued linear functional. For two compact convex sets A, B ∈ K(X) we will use the notation

A ∨ B := conv(A ∪ B),

where the operation “conv” denotes the convex hull. With \overline{A} we denote the closure of a set A. During the proofs, an easy identity for compact convex sets, which was first observed by A. Pinsker [10] will be used frequently, namely: For A, B, C ∈ K(X) we have:

(A + C) ∨ (B + C) = C + (A ∨ B).  (∗)

This identity can be proved as follows: Every x ∈ (A ∨ B) + C can be represented as x = α · a + (1 − α) · b + c with a ∈ A, b ∈ B, c ∈ C and 0 ≤ α ≤ 1. Now x = α · a + (1 − α) · b + c = α · (a + c) + (1 − α) · (b + c) and hence C + (A ∨ B) ⊆ (A + C) ∨ (B + C). The converse inclusion can be seen as follows: Let x ∈ (A + C) ∨ (B + C). Then we have: x = α · (a + c_{1}) + (1 − α) · (b + c_{2}) with a ∈ A, b ∈ B, c_{1}, c_{2} ∈ C and 0 ≤ α ≤ 1. Now x = α · (a + c_{1}) + (1 − α) · (b + c_{2}) = α · a + (1 − α) · b + α · c_{1} + (1 − α) · c_{2}. Hence we see that the converse inclusion (A + C) ∨ (B + C) ⊆ C + (A ∨ B) holds also. We will use the abbreviation A+B ∨C for A+(B ∨C) and C +d for C +{d} for compact convex sets A, B, C and a point d. Moreover we will write [a, b] instead of {a} ∨ {b}. Finally let us state explicitely the order cancellation law (see [4], [15]). Let X be real topological vector space and A, B, C ⊆ X compact convex subsets. Then the inclusion

A + B ⊆ A + C

implies

B ⊆ C.

Thus from the algebraic point of view the set K(X) of all nonempty compact convex subsets of a real topological vector space X is a commutative semi-ring with cancellation property endowed with the “addition # ” given by:

A # B := A ∨ B

and the “multiplication ⋆” given by:

A ⋆ B := A + B.

Within this context, the elements of K^{2}(X) with respect to the relation ∼ can be considered as fractions.

The starting point of this paper is a characterization, which is proved in [16], of those convex subsets of a compact convex set, which define a decomposition in the following sense:

In [8] the following notation was introduced: Let A, B, S ∈ K(X), then we say that S “separates” the sets A and B if for every a ∈ A and b ∈ B we have [a, b] ∩ S ≠ ∅. In this terminology we have:

Theorem 1.1. Let X be a real topological vector space and A, B ∈ K(X). Then the following statements are equivalent:

(i) The set A ∪ B is convex (ii) The set A ∩ B separates the sets A and B (iii) The set A ∨ B is a summand of the set A + B (iv) A + B = A ∨ B + A ∩ B and A ∩ B ≠ ∅.

Let us remark, that if A∩B separates the sets A and B, the basic relationship between the Minkowski-sum, the convex hull and the intersection is given by property (iv) of Theorem 1.1. The algebraic analogue of this formula is, that the product of two integers a, b ∈ IN is equal to the product of its greatest common divisor d(a, b) with its smallest common multiplier m(a, b). i.e. a · b = d(a, b) · m(a, b). In [16] a pair (A, B) ∈ K^{2}(X) is called “convex” if A ∪ B is a convex set. Moreover it is shown, that every pair (A, B) ∈ K^{2}(X) is equivalent to a convex pair, namely:

Proposition 1.2. Let X be a real topological vector space and (A, B) ∈ K^{2}(X). Then:

(i) The pair (A + A ∨ B, B + A ∨ B) ∈ K^{2}(X) is convex (ii) (A + A ∨ B) ∩ (B + A ∨ B) = A + B (iii) (A, B) ∼ (A + A ∨ B, B + A ∨ B). (iv) Let (C, D) ∈ K^{2}(X) and (A, B) ∼ (C, D) and assume that the pair (A, B) is convex.

Then

A + D = B + C = C ∨ D + A ∩ B.

Let us recall that for a real topological vector space X a pair (A, B) ∈ K^{2}(X) is minimal if and only if for every equivalent pair (C, D) ∈ K^{2}(X) the relation (C, D) ≤ (A, B) implies C = A and B = D. Therefore we define:

Definition 1.3. Let X be a real topological vector space. Then a convex pair (A, B) ∈ K^{2}(X) is minimal convex if and only if for every equivalent convex pair (C, D) ∈ K^{2}(X) the relation (C, D) ≤ (A, B) implies C = A and B = D.

It is shown in [16] that for every convex pair (A, B) ∈ K^{2}(X) there exists an equivalent minimal convex pair and the following characterization of minimal convex pairs holds.

Theorem 1.4. Let X be a real topological vector space. Then the convex pair (A, B) ∈ K^{2}(X) is minimal convex if and only if the pair (A ∩ B, A ∪ B) is minimal.

2. Algebraic Properties of Compact Convex Sets

In this section we prove several algebraic properties of compact convex sets, which are usefull for further discussions and also interesting in itself. Let us start with the following observations:

Lemma 2.1. Let X be a real topological vector space and A, B, C ⊂ X nonempty subsets. Then

A ∪ B + C = (A + C) ∪ (B + C).

Proof. For x ∈ A ∪ B + C, exists c ∈ C and d ∈ A ∪ B such that x = c + d. Hence x ∈ (A + C) ∪ (B + C), i.e. A ∪ B + C ⊆ (A + C) ∪ (B + C). Conversely, for x ∈ (A + C) ∪ (B + C) there exist elements c ∈ C and d ∈ A or d ∈ B such that x = c + d. Hence x ∈ A ∪ B + C, i.e. (A + C) ∪ (B + C) ⊆ A ∪ B + C.

Lemma 2.2. Let X be a real topological vector space with dim X > 1 and (A, B) ∈ K^{2}(X). If for every singleton C = {c} ∈ K(X)

(A ∨ C) ∪ (B ∨ C) = A ∨ B ∨ C  (2.2.1)

holds, then A ∩ B ≠ ∅.

Proof. Suppose that A ∩ B = ∅. Then there exists a ∈ A and b ∈ B such that (a, b) ∩ (A ∪ B) = ∅, where (a, b) is the open line segment between the points a, b. Let us denote by l the line passing through the points a and b. Now we consider two cases:

(i) A, B ⊂ l, i.e. the sets A and B are intervalls lying in l. Then for every c ∈ X \ l and C := {c} we have (A ∨ C) ∩ (B ∨ C) = {c}. But {c} ∩ [a, b] = ∅. From this follows that {c} does not separate the sets A ∨ C and B ∨ C. Hence the set (A ∨ C) ∪ (B ∨ C) is not convex which is a contradiction to the assumption.

(ii) Now let us assume, that one of the sets A and B is not contained in the line l, for instance that B ⊄ l. Then there exists a point b_{1} ∈ B with b_{1} ∉ l such that (a, b_{1}) ∩ B = ∅. Now put C_{1} := {b_{1}}. Then it follows from equation (2.2.1) and Theorem 1.1 (ii) that the set (A ∨ b_{1}) ∩ B separates the sets A ∨ b_{1} and B. Hence there exist numbers α, β ≥ 0, α+β = 1, such that α·a + β ·b ∈ (A∨b_{1})∩B. But by assumption we have (a, b) ∩ (A ∪ B) = ∅, hence α = 0 and β = 1, and we obtain that b ∈ A∨b_{1}. From this follows, that b = α_{1} ·b_{1} + β_{1} ·a_{1} for some α_{1}, β_{1} ≥ 0, α_{1} +β_{1} = 1 and a_{1} ∈ A.

Now we proceed analogously for the set C_{2} := {a_{1}} and obtain that a = α_{2} · a_{1} + β_{2} · b_{2} for some α_{2}, β_{2} ≥ 0, α_{2} + β_{2} = 1 and b_{2} ∈ B. Hence we have (a, b_{1}) ∩ [b, b_{2}] ≠ ∅. Since (a, b_{1}) ∩ [b, b_{2}] = {p} for some p ∈ (a, b_{1}), this is a contradiction to (a, b_{1}) ∩ B = ∅. Hence we have A ∩ B ≠ ∅.

Remark 2.3. If dim X = 1, and A, B ∈ K(X) with A ∩ B = ∅. Then for every C ∈ K(X) we have (A ∨ C) ∪ (B ∨ C) = A ∨ B ∨ C.

Lemma 2.4. Let X be a real topological vector space and A, B ∈ K(X). Moreover assume, that A ∩ B ≠ ∅ and that for every segment C = [a, b] ∈ K(X)

(A ∨ C) ∩ (B ∨ C) = (A ∩ B) ∨ C

holds. Then the set A ∩ B separates the sets A and B.

Proof. First observe, that if dim X = 1 and A ∩ B ≠ ∅ then A ∪ B is convex and hence A ∩ B separates the sets A and B. Now suppose that dim X > 1 and that A ∩ B does not separate the sets A and B. Then there exist elements a ∈ A and b ∈ B such that [a, b] ∩ (A ∩ B) = ∅. For an arbitrary element p ∈ A ∩ B let us consider the sequences (a_{n})_{n∈IN} and (b_{n})_{n∈IN} given by:

a_{n} := \frac{1}{n} · p + (1 − \frac{1}{n}) · a and b_{n} := \frac{1}{n} · p + (1 − \frac{1}{n}) · b for n ∈ IN.

Denote I_{n} := [a_{n}, b_{n}] = \frac{1}{n} · p + (1 − \frac{1}{n}) · [a, b]. It is easy to observe that I_{n_{0}} ∩ [a, b] = ∅ for some n_{0} ∈ IN. Namely, assume that for every n ∈ IN we have I_{n} ∩ [a, b] ≠ ∅. Then there exits a sequence (c_{n})_{n∈IN} with:

c_{n} := \frac{1}{n} · p + (1 − \frac{1}{n}) · [α_{n} · a + (1 − α_{n}) · b]

and 1 ≥ α_{n} ≥ 0. Since there exist a subsequence (α_{n_{k}})_{k∈IN} which converges to α_{0} ∈ [0, 1], it follows, that the sequence (c_{n_{k}})_{k∈IN} which converges to c_{0} = α_{0} · a + (1 − α_{0}) · b. Since A ∩ B is compact and for every n ∈ IN we have c_{n} ∈ A ∩ B it follows additionally that c_{0} ∈ [a, b] ∩ (A ∩ B).

Now let H be the linear manifold generated by the points a, b, p. Moreover let l_{n} be the line which passes through the points a_{n} and b_{n}. This line devides the plane into the halfplanes H^{+} and H^{−} where we assume that p ∈ H^{−}. Suppose that H^{+} ∩ (A ∩ B) ≠ ∅. Then there exists x ∈ H^{+} ∩ (A ∩ B) and therefore [x, p] ∩ l ≠ ∅. Let us put {y} := [x, p] ∩ l, then we have I_{n} ∩ A ∩ B ≠ ∅. But this is a contradiction, hence H^{+} ∩ A ∩ B = ∅. Now put {z} := [a_{n}, b] ∩ [a, b_{n}], then z ∈ H^{+}. First observe that z = ({a} ∨ {b_{n}}) ∩ ({b} ∨ {a_{n}}) ⊂ (A ∨ I_{n}) ∩ (B ∨ I_{n}), and that z ∉ I_{n}. Furthermore choose u ∈ {[(A ∩ B) ∨ I_{n}] \ I_{n}} ∩ H. Then there exist α, β > 0, α + β = 1 such that u = α · q + β · v for some q ∈ A ∩ B and v ∈ I_{n} ⊂ H^{−}. This implies that q = \frac{1}{α} · u − \frac{β}{α} · v and \frac{1}{α} − \frac{β}{α} = 1. Hence q ∈ A ∩ B ∩ H ⊂ H^{−}, and we obtain that u ∈ α · H^{−} + β · H^{−} ⊂ H^{−}. Now suppose that z ∈ [(A ∩ B) ∨ I_{n}] ∩ H. Since z ∉ I_{n} this implies that z ∈ {[(A ∩ B) ∨ I_{n}] \ I_{n}} ∩ H ⊂ H^{−}. But this contradicts the assumption that z ∈ H^{+}. Now for C := I_{n} we have that (A ∨ C) ∩ (B ∨ C) ≠ (A ∩ B) ∨ C, hence A ∩ B separates the sets A and B.

Now we are able to prove the following equivalences:

Proposition 2.5. Let X be a real topological vector space and (A, B) ∈ K^{2}(X). Then the following assertions are equivalent:

(i) A ∪ B is convex (ii) For every C ∈ K(X) we have (A + C) ∪ (B + C) = A ∨ B + C (iii) A ∩ B ≠ ∅ and for every C ∈ K(X) we have (A + C) ∩ (B + C) = A ∩ B + C (iv) A∩B ≠ ∅ and for every segment C ∈ K(X) we have (A∨C)∩(B ∨C) = (A∩B)∨C (v) For every singleton C ∈ K(X) we have (A ∨ C) ∪ (B ∨ C) = A ∨ B ∨ C, if A ∩ B ≠ ∅

or dim X > 1.

Proof. (i) ⟺ (ii). If A ∪ B is convex then A ∪ B = A ∨ B. But from Lemma 2.1 follows that for every C ∈ K(X) we have (A + C) ∪ (B + C) = A ∪ B + C. Hence (A + C) ∪ (B + C) = A ∨ B + C. For the converse direction observe that (i) follows from (ii) for C := {0}, then A ∪ B = A ∨ B. (ii) ⟺ (iii). By formula (∗) and Theorem 1.1 we have A+C +B +C = A∨B +C +(A+ C) ∩ (B + C). This implies A + B + C = A ∨ B + (A + C) ∩ (B + C). But (ii) is equivalent to (i), hence we know that A ∪ B is convex and therefore we have A + B = A ∨ B + A ∩ B. From this we obtain that

A ∨ B + A ∩ B + C = A ∨ B + (A + C) ∩ (B + C).

Hence by the law of cancellation we get

A ∩ B + C = (A + C) ∩ (B + C).

(iii) ⟹ (i). Observe that for C := A ∨ B, we get from (iii):

A + B ⊂ (A + A ∨ B) ∩ (B + A ∨ B) = A ∩ B + A ∨ B.

Thus by [16] Theorem 2.3 we have that A∩B separates the sets A and B and hence A∪B is convex.

(i) ⟹ (iv) and (v). For C ∈ K(X), then we have:

A ∨ C + B ∨ C = (A ∨ C + B) ∨ (A ∨ C + C)
= (A + B) ∨ (B + C) ∨ (A + C) ∨ (C + C)
= (A ∪ B + A ∩ B) ∨ (A ∨ B + C) ∨ (C + C)
= (A ∪ B + (A ∩ B) ∨ C) ∨ (C + C)
⊆ (A ∪ B + (A ∩ B) ∨ C) ∨ ((A ∩ B) ∨ C + C)
⊆ (A ∪ B) ∨ C + (A ∩ B) ∨ C
⊆ (A ∨ C) ∨ (B ∨ C) + (A ∩ B) ∨ C
⊆ (A ∨ C) ∨ (B ∨ C) + (A ∨ C) ∩ (B ∨ C).

Hence

A ∨ C + B ∨ C ⊆ (A ∨ C) ∨ (B ∨ C) + (A ∨ C) ∩ (B ∨ C),

and by [16] Theorem 2.3 and Theorem 1.1 we have:

A ∨ C + B ∨ C = (A ∨ C) ∨ (B ∨ C) + (A ∨ C) ∩ (B ∨ C).

Hence we have

(A ∨ C) ∩ (B ∨ C) = (A ∩ B) ∨ C

and

(A ∨ C) ∪ (B ∨ C) = (A ∨ B) ∨ C.

(iv) ⟹ (i). By Lemma 2.4 we have that A ∩ B separates the sets A and B, hence the set A ∪ B is convex.

(v) ⟹ (i). If A ∩ B ≠ ∅, then for x ∈ A ∩ B and C := {x} we obtain A ∪ B = A ∨ B. If dim X > 1, then from Lemma 2.2 we get A ∩ B ≠ ∅ and proceed as in the above mentioned case.

Proposition 2.6. Let X be a real topological vector space and (A, B), (C, D) ∈ K^{2}(X) are two equivalent pairs and assume that the pair (C, D) is convex. Then the pairs (A + C, B + C), (A + D, B + D) are convex.

Proof. From Proposition 1.2 we have that

A + D = B + C = A ∨ B + C ∩ D.

This implies that

A + C + B + C = A ∨ B + C + A + C ∩ D,

and

A + D + B + D = A ∨ B + D + B + C ∩ D.

Moreover,

(A + C) ∨ (B + C) = A ∨ B + C and (A + D) ∨ (B + D) = A ∨ B + D.

Now from Theorem 1.1 follows, that (A + C, B + C) and (A + D, B + D) are convex pairs.

3. C-minimal pairs

Definition 3.1. Let X be a real topological vector space and C ∈ K(X). Then the pair (A, B) ∈ K^{2}(X) is called “C-minimal” if the pair (A + C, B + C) is convex, and if for every C_{1} ∈ K(X) with C_{1} ⊆ C and such that (A + C_{1}, B + C_{1}) is a convex pair it follows that C_{1} = C.

Remark 3.2. The pair (A, B) is convex if and only if the pair (A, B) is C-minimal and the set C is a singleton.

Theorem 3.3. Let X be a real topological vector space and C ∈ K(X). Then the pair (A, B) ∈ K^{2}(X) is C-minimal if and only if there exists a D ∈ K(X) such that the pair (C, D) is minimal and equivalent to (A ∨ B, A + B).

Proof. “⟹” Since the pair (A, B) ∈ K^{2}(X) is C-minimal, we know by Theorem 1.1 (iv) that

A + C + B + C = (A + C) ∪ (B + C) + (A + C) ∩ (B + C).

Since

(A + C) ∪ (B + C) = (A + C) ∨ (B + C) = (A ∨ B) + C

we obtain that

A + B + C = A ∨ B + (A + C) ∩ (B + C).

If we put D := (A + C) ∩ (B + C), then it follows, that

(A ∨ B, A + B) ∼ (C, D).  (3.3.1)

Now suppose that there exists a C_{1} ⊂ C and D_{1} ⊂ D such that (C, D) ∼ (C_{1}, D_{1}). Then (A ∨ B, A + B) ∼ (C_{1}, D_{1}). Hence we have A ∨ B + D_{1} = A + B + C_{1}, which implies (A+C_{1})∨(B +C_{1})+D_{1} = (A+C_{1})+(B +C_{1}). Thus (A+C_{1})∨(B +C_{1}) is a summand of (A + C_{1}) + (B + C_{1}), which means that the set (A + C_{1}) ∪ (B + C_{1}) is convex. Hence by the C-minimality of (A, B) it follows that C = C_{1} and D = D_{1}. “⟸” Now if (A ∨ B, A + B) ∼ (C, D) and (C, D) minimal, then (A + C, B + C) is a convex pair. Then for every (C_{1}, D_{1}) ≤ (C, D) which is equivalent to (C, D) we have C = C_{1} and D = D_{1}.

Corollary 3.4. For every pair (A, B) ∈ K^{2}(X) there exists a set C ∈ K(X) such that the pair (A, B) is C-minimal.

Theorem 3.5. Let X be a real topological vector space and A, B, C ∈ K(X). Then the pair (A + C, B + C) is minimal convex if and only if there exists a D ∈ K(X) such that (A ∨ B, A + B) is equivalent to (C, D) and (A ∨ B + C, D) is a minimal pair.

Proof. “⟸” First observe, that the minimality of the pair (A ∨ B + C, D) implies, that (C, D) is minimal since

(A ∨ B + C, D) = (A ∨ B, 0) + (C, D)

and (A ∨ B, 0) is minimal (see [6]). Now by Theorem 3.3 the pair (A, B) is C-minimal. But then we have:

(A + C) ∪ (B + C) = A ∨ B + C and (A + C) ∩ (B + C) = D.

Hence it follows from Theorem 1.4 that (A + C, B + C) is a minimal convex pair. “⟹” Now let us assume that (A + C, B + C) is a minimal convex pair. Then the set (A + C) ∪ (B + C) is convex and by Theorem 1.1 the pair (A ∨ B, A + B) is equivalent to (C, D), with D = (A + C) ∩ (B + C). Now from Theorem 1.4 follows that (A ∨ B + C, D) is a minimal pair.

Corollary 3.6. The pair (A + A ∨ B, B + A ∨ B) ∈ K^{2}(X) is minimal convex if and only if the pair (A ∨ B, A + B) is minimal.

Proof. The minimality of the pair (A ∨ B, A + B) is equivalent to the minimality of the pair (2 · (A ∨ B), A + B). Hence we obtain from the above Theorem, that (A + A ∨ B, B + A ∨ B) ∈ K^{2}(X) is a minimal convex pair if and only if (A ∨ B, A + B) is a minimal pair.

Remark 3.7.

(i) The set D ∈ K(X) of Theorem 3.5 is uniquely determined and coincides with (A + C) ∩ (B + C).

(ii) If the pair (A + C, B + C) is minimal convex, then (A, B) is a C-minimal pair.

Proposition 3.8. Let X be a real topological vector space and (A, B), (C, D) ∈ K^{2}(X) are two equivalent minimal pairs and assume that the sets A ∪ C and B ∪ D are convex. Then A = C and B = D.

Proof. Observe that by Proposition 2.5 (iii)

A + (B ∩ D) = (A + B) ∩ (A + D) = (A + B) ∩ (B + C) = B + (A ∩ C),

since the sets A ∪ C and B ∪ D are convex. By assumption the pair (A, B) ∈ K^{2}(X) is minimal. Hence

A ∩ C = A and B ∩ D = B.

Since the pair (C, D) ∈ K^{2}(X) is is also minimal, it follows that A = C and B = D.

In analogy to the above Proposition 3.8 and the results of J. Grzybowski [3] and S. Scholtes [14] we have:

Theorem 3.9. If (A, B), (C_{1}, C_{2}) ∈ K^{2}(IR^{n}), 1 ≤ n ≤ 2 and the pair (A, B) is C_{i}-minimal for i = 1, 2, then there exists an x ∈ IR^{n} such that C_{2} = C_{1} + x.

Proof. Since for i = 1, 2 the pair (A, B) is C_{i}-minimal, there exists by Theorem 3.3 elements D_{i} ∈ K(IR^{n}), such that the pairs (C_{i}, D_{i}), i = 1, 2 are both minimal and equivalent to (A ∨ B, A + B). Hence it follows from the resultes of J. Grzybowski and S. Scholtes (see for instance: [3], Lemma 3.7) that C_{2} = C_{1} + x for an x ∈ IR^{n}.

Now we study some properties of C-minimal equivalence classes.

Lemma 3.10. Let X be a topological vector space and A, B_{α} ∈ K(X), for α ∈ Λ. If the family {B_{α}}_{α∈Λ} is a chain, then ⋂_{α∈Λ} B_{α} ≠ ∅ and

A + ⋂_{α∈Λ} B_{α} = ⋂_{α∈Λ}(A + B_{α}).

10 D.Pallaschke, W.Urbańska, R.Urbański / C-minimal pairs of compact convex sets

Proof. Since the family F := {B_{α}}_{α∈Λ} has the finite intersection property, we have ⋂_{α∈Λ} B_{α} ≠ ∅ (see [2]). If we define for α, β ∈ Λ a partial order by:

α ≤ β if and only if B_{β} ⊆ B_{α}

then the set Λ is directed by ≤ . Now observe that

A + ⋂_{α∈Λ} B_{α} ⊆ ⋂_{α∈Λ}(A + B_{α}).

To prove the converse inclusion, let us choose an arbitrary element x ∈ ⋂_{α∈Λ}(A + B_{α}). Then for every α ∈ Λ there exist a_{α} ∈ A and b_{α} ∈ B_{α} such that x = a_{α} + b_{α}. Since the set S := {a_{α} | α ∈ Λ } is a net in the compact set A, there exists a cluster point a ∈ A of S. Now b_{α} = x − a_{α} and since X is a topological vector space, there exists an element b ∈ X which is a cluster point of the net S′ := {b_{α} | α ∈ Λ } with x = a + b. To complete the proof, it suffices to show, that b ∈ X belongs to all members of the family F. Therefore take a B_{α} ∈ F. Then for every neighborhood V of b there exists an index β ≥ α such that b_{β} ∈ V. Since b_{β} ∈ B_{β} ⊆ B_{α}, we conclude that B_{α} ∩V ≠ ∅. Furthermore, the set B_{α} is closed which implies, that b ∈ B_{α}.

Definition 3.11. Let X be a real topological vector space and A, B, C ∈ K(X). The class [A, B] is called “C-convex” if for every representant (A_{1}, B_{1}) ∈ [A, B] the pair (A_{1} + C, B_{1} + C) is convex.

Definition 3.12. Let X be a real topological vector space and A, B, C ∈ K(X). The class [A, B] is called “C-minimal” if for every C_{1} ∈ K(X) with C_{1} ⊆ C for which the class [A, B] is C_{1}-convex, follows that C_{1} = C.

Theorem 3.13. Let X be a real topological vector space. Then for every class [A_{0}, B_{0}], with A_{0}, B_{0} ∈ K(X), there exists a set C_{0} ∈ K(X) such that the class [A_{0}, B_{0}] is C_{0}-minimal.

Proof. For the pair (A_{0}, B_{0}) ∈ K^{2}(X) let us consider the family

C_{[A_{0},B_{0}]} := {C | C ∈ K(X) such that for every (A, B) ∈ [A_{0}, B_{0}]

the pair (A + C, B + C) is convex }.

This family is non empty, namely A_{0} + A_{0} ∨ B_{0} ∈ C_{[A_{0},B_{0}]}, which can be seen as follows: Observe first that the pair (A_{0}, B_{0}) is equivalent to the convex pair (A_{0} + A_{0} ∨ B_{0}, B_{0} + A_{0} ∨ B_{0}). If we put now C^{∗} := A_{0} + A_{0} ∨ B_{0} then the rest follows from Proposition 2.6. Now we can order the class C_{[A_{0},B_{0}]} by inclusion, namely C_{α} ⊆ C_{β} ⟺ α ≤ β. Now consider an ordered chain {C_{α}}_{α∈Λ}. Then by Lemma 3.10 we have:

A + ⋂_{α∈Λ} C_{α} = ⋂_{α∈Λ}(A + C_{α})

and

B + ⋂_{α∈Λ} C_{α} = ⋂_{α∈Λ}(B + C_{α}).

for arbitrary elements A, B ∈ K(X). Now consider (A, B) ∈ [A_{0}, B_{0}]. From the definition of the class C_{[A_{0},B_{0}]} follows, that for every α ∈ Λ the pair (A + C_{α}, B + C_{α}) is convex. Therefore we have: (A ∨ B, A + B) ∼ (C_{α}, (A + C_{α}) ∩ (B + C_{α})), which means that

A + B + C_{α} = A ∨ B + (A + C_{α}) ∩ (B + C_{α}).

Now by Lemma 3.10 we have:

⋂_{α∈Λ}(A + B + C_{α}) = A + B + ⋂_{α∈Λ} C_{α},

and also

⋂_{α∈Λ}(A ∨ B + (A + C_{α}) ∩ (B + C_{α})) = A ∨ B + ⋂_{α∈Λ}(A + C_{α}) ∩ (B + C_{α}).

Denote

C_{0} = ⋂_{α∈Λ} C_{α}.

Hence

A + B + C_{0} = A ∨ B + (A + C_{0}) ∩ (B + C_{0}).

Now from C_{0} ∈ C_{[A_{0},B_{0}]} and the Lemma of Kuratowski-Zorn follows, that C_{[A_{0},B_{0}]} has a minimal element.

Proposition 3.14. Let X be a real topological vector space C ∈ K(X) and (A_{0}, B_{0}) ∈ K^{2}(X) be a C-minimal pair. Moreover let us assume that A_{0} or B_{0} is a summand of (A_{0} + C) ∩ (B_{0} + C). Then the class [A_{0}, B_{0}] is C-minimal.

Proof. For every (A, B) ∈ [A_{0}, B_{0}] we have (A, B) ∼ (A_{0} + C, B_{0} + C). Hence

A + B_{0} + C = A_{0} + C + B = A ∨ B + (A_{0} + C) ∩ (B_{0} + C).  (3.14.1)

Now assume that B_{0} is a summand of (A_{0} + C) ∩ (B_{0} + C). Hence we have (A_{0} + C) ∩ (B_{0} + C) = B_{0} + S, for some S ∈ K(X). Now we obtain from (3.14.1) that

B + C = A ∨ B + S,

and by adding A + C we get A + B + C + C = A ∨ B + C + A + S, and therefore we have:

(A + C) + (B + C) = (A ∨ B + C) + (A + S)

i.e.

(A + C) + (B + C) = (A + C) ∨ (B + C) + (A + S).

From Theorem 1.1 and the formula (A + C) ∨ (B + C) = (A ∨ B + C), follows that (A + C) ∪ (B + C) is convex. Since (A_{0}, B_{0}) ∈ K^{2}(X) a C-minimal pair it follows, that the class [A_{0}, B_{0}] is C-minimal.

Proposition 3.15. Let X be a real topological vector space. Then a convex pair (A_{0}, B_{0}) ∈ K^{2}(X) is minimal convex if and only if for every convex pair (A, B) ∈ K^{2}(X) equivalent to (A_{0}, B_{0}) with A ∪ B ⊆ A_{0} ∪ B_{0} follows that A = A_{0} and B = B_{0}.

Proof. “⟹” Let (A, B) be a convex pair which is equivalent to (A_{0}, B_{0}) and such that A ∪ B ⊆ A_{0} ∪ B_{0}. Then

A + B_{0} = A_{0} + B = A ∪ B + A_{0} ∩ B_{0} ⊆ A_{0} ∪ B_{0} + A_{0} ∩ B_{0} = A_{0} + B_{0}.

Now from the order cancellation law we get that A ⊂ A_{0} and B ⊂ B_{0}. From the convex minimality we deduce that A = A_{0} and B = B_{0}. “⟸” Now let (A, B) ∼ (A_{0}, B_{0}) be a convex pair with A ⊂ A_{0} and B ⊂ B_{0}. Then A ∪ B ⊂ A_{0} ∪ B_{0}, and therefore by assumption we have A ∪ B = A_{0} ∪ B_{0}. This means by Theorem 1.1 that

A + B_{0} = B + A_{0} = A_{0} ∪ B_{0} + A_{0} ∩ B_{0} = A_{0} + B_{0},

and hence A = A_{0} and B = B_{0}.

4. Convex hull of pairs of compact convex sets

In this section we give a definition of a convex hull of a pair of compact convex sets. The intention is, that the convex hull can be considered as a smallest convexification of the set, and this is the motivation for our definition:

Definition 4.1. Let X be a real topological vector space and and (A, B) ∈ K^{2}(X). A convex pair (C, D) ∈ K^{2}(X) is called a “convex hull” of the pair (A, B) if (A, B) ≤ (C, D) ∼ (A, B) and if for every convex pair (C_{1}, D_{1}) ∈ K^{2}(X) with (C_{1}, D_{1}) ∼ (C, D) and (A, B) ≤ (C_{1}, D_{1}) ≤ (C, D), it follows that (C, D) = (C_{1}, D_{1}).

Proposition 4.2. Let X be a real topological vector space and (C, D) ∈ K^{2}(X) a convex pair, which is equivalent to (A, B) ∈ K^{2}(X). Then the following statements are equivalent:

(i) The set C ∩ D separates the sets A and B, (ii) (A, B) ≤ (C, D), (iii) A ∪ B ⊆ C ∪ D.

Proof. “(i) ⟹ (ii)” Since the pair (C, D) is convex and equivalent to (A, B) by Theorem 1.2 we have that A+D = B +C = A∨B +C ∩D. Since C ∩D separates the sets A and B we have by (see [8]) that A + B ⊆ A ∨ B + C ∩ D. Therefore A + B ⊆ A + D = B + C and from the order law of cancellation we get that A ⊂ C and B ⊂ D. “(ii) ⟹ (i)” is obvious by (see [8]). “(iii) ⟹ (ii)” Since the pair (A + A ∨ B, B + A ∨ B) is convex and equivalent to the convex pair (C, D) it follows immediately from Lemma 1.2 that

A + A ∨ B + D = B + A ∨ B + C = A + B + C ∪ D ⊇ A + B + A ∨ B.

The inclusions A ⊆ C and B ⊆ D follow now from the order law of cancellation. “(ii) ⟹ (iii)” This implication is obvious.

Theorem 4.3. Let X be a real topological vector space. Then for every pair (A, B) ∈ K^{2}(X) there exists a convex hull of (A, B).

Proof. For the pair (A, B) ∈ K^{2}(X) let us consider the family

C_{(A,B)} :=

{(C, D) | (C, D) ∈ K^{2}(X) such that (A, B) ≤ (C, D) ∼ (A, B) and (C, D) is convex}.

This family is non empty, namely for every arbitrary x ∈ A ∨ B we have by Proposition 1.2 that the pair (A + A ∨ B − x, B + A ∨ B − x) is convex and equivalent to (A, B). Moreover

(A, B) ≤ (A + A ∨ B − x, B + A ∨ B − x).

Analogously to the proof of Theorem 3.13 we can show that for an arbitrary totally ordered set B ⊆ C_{(A,B)}, with B := {(A_{α}, B_{α}) | α ∈ Λ }, the pair (A_{0}, B_{0}) is equivalent to (A, B), where

A_{0} = ⋂_{α∈Λ} A_{α} and B_{0} = ⋂_{α∈Λ} B_{α}.

It is obvious that (A, B) ≤ (A_{0}, B_{0}). Hence by the Lemma of Kuratowski-Zorn there exists a minimal element in C_{(A,B)} and this is a convex hull of the pair (A, B).

Remark 4.4. If the pair (A, B) is equivalent to (C, D) and is such that (A, B) ≤ (C, D) and (C, D) is minimal convex, then (C, D) is a convex hull of (A, B).

5. Reduction of pairs of compact convex sets

In this part of the paper we discuss algorithmic concepts of reducing a pair of compact convex sets within its equivalence class and such that given properties of a pair remain preserved under the reduction. In [16] the following result is proved:

Theorem 5.1. Let X be a real topological vector space and (A, B) ∈ K^{2}(X) be a convex pair. Then for every pair (F, G) ∈ K^{2}(X) which is equivalent to (A ∩ B, A ∪ B) such that (F, G) ≤ (A ∩ B, A ∪ B) there exists a convex pair (A_{0}, B_{0}) ∼ (A, B) with A_{0} ∩ B_{0} = F and A_{0} ∪ B_{0} = G.

Now we show:

Proposition 5.2. If (A, B) ∈ K^{2}(X) is a convex pair and F, G ∈ K(X) such that A ∪ B + F = A ∩ B + G, F ⊆ A ∩ B. Moreover let us assume that A ∪ G = A ∪ B or B ∪ G = A ∪ B. Then A ∪ B is a summand of A + G or A ∪ B is a summand of B + G.

Proof. From Theorem 5.1 follows, that there exist A_{0}, B_{0} ∈ K(X) such that

A + B_{0} = B + A_{0} = A ∪ B + F = A ∩ B + G,

with

B_{0} ∩ A_{0} = F and B_{0} ∪ A_{0} = G.

Hence we have:

B + A_{0} + A ∪ B = A ∩ B + A ∪ B + G = A + B + G,

and

A_{0} + A ∪ B = A + G.  (5.2.1)

Analogously

B_{0} + A ∪ B = B + G.  (5.2.2)

If A ∪ G = A ∪ B then A + G = A ∩ G + A ∪ B, and we obtain that

A_{0} + A ∪ B = A ∩ G + A ∪ B,

which gives A_{0} = A ∩ G. From the assumption B ∪ G = A ∪ B follows analogously, that B_{0} = B ∩ G.

Proposition 5.3. Let X be a real topological vector space and (A, B) ∈ K^{2}(X) a convex pair. Moreover let us assume that there exist sets A_{1}, B_{1}, C ∈ K(X), such that A = A_{1} ∪ C , B = B_{1} ∪ C and C ∩ A_{1} = C ∩ B_{1}. Then (A_{1}, B_{1}) is a convex pair which is equivalent to (A, B).

Proof.

Let us put S := C ∩ A_{1}. Then we have:

A + S = C + A_{1}  B + S = C + B_{1}.  (5.3.1)

Hence

A ∪ B + S = C + A_{1} ∨ B_{1}  A + B + 2S = 2C + A_{1} + B_{1}.  (5.3.2)

From the last equation we get:

A ∪ B + S + A ∩ B + S = 2C + A_{1} + B_{1}.  (5.3.3)

But

C + A_{1} ∩ B_{1} = A ∩ B + S,  (5.3.4)

hence from (5.3.3) and (5.3.4) follows, that

A_{1} + B_{1} = A_{1} ∨ B_{1} + A_{1} ∩ B_{1}.

Now by Theorem 5.1 we know that the pair (A_{1}, B_{1}) is convex and from (5.3.1) follows that A + B_{1} = B + A_{1}.

Corollary 5.4. Let (A, B) ∈ K^{2}(X) be a convex pair and let G ∈ K(X) be such that A ∪ G = B ∪ G = A ∪ B. Then the pair (A ∩ G, B ∩ G) is convex and equivalent to (A, B).

Proof. Put A_{1} := A∩G, B_{1} := B∩G, and C := A∩B. Then C∪A_{1} = (A∩B)∪ (A∩G) = A∩(B ∪G) = A, and C ∪B_{1} = B. Moreover C ∪(A_{1}∩B_{1}) = (A∩B)∪(A∩B ∩G) = A∩B and C ∩ A_{1} = C ∩ B_{1} = A ∩ B ∩ G. Hence by the above Proposition 5.3 we obtain that (A ∩ G, B ∩ G) is a convex pair, which is equivalent to the pair (A, B).

Corollary 5.5. Let (A, B) ∈ K^{2}(X) be a convex pair and assume that \overline{conv}(A ∪ B\ A ∩ B) ≠ A ∪ B. Then (A, B) is not convex minimal.

Proof. Denote

F := (A ∩ B) ∩ \overline{conv}(A ∪ B \ A ∩ B) and G := \overline{conv}(A ∪ B \ A ∩ B).

Then A ∪ B + F = A ∩ B + G and since A ∪ G = B ∪ G = A ∪ B, we obtain from Proposition 5.2 that (A ∩ G, B ∩ G) ∼ (A, B). Since A ∩ G is an essential subset of A, we see that the pair (A, B) is not convex minimal.

Proposition 5.6. Let X be a real topological vector space and (A_{1}, B_{1}), (A_{2}, B_{2}) ∈ K^{2}(X) convex pairs such that:

\begin{aligned}(A_{1} ∩ B_{1} + x) ∪ (A_{2} ∪ B_{2}) & = A_{1} ∪ B_{1}, \\ (A_{1} ∩ B_{1} + x) ∩ (A_{2} ∪ B_{2}) & = A_{2} ∩ B_{2} + x, for some x ∈ X. \end{aligned}

Moreover assume that

A_{1} ∪ B_{2} = A_{2} ∪ B_{2} and A_{1} ∩ B_{2} = A_{1} ∩ B_{1}  (5.6.1)

or

A_{2} ∪ B_{1} = A_{1} ∪ B_{1} and A_{2} ∩ B_{1} = A_{2} ∩ B_{2}.  (5.6.2)

Then

(A_{1}, B_{1}) ∼ (A_{2}, B_{2}) and (A_{2}, B_{2}) ≤ (A_{1}, B_{1}).

Proof. Let us first observe that

(A_{1} ∩ B_{1} + x) + (A_{2} ∪ B_{2}) = A_{1} ∪ B_{1} + (A_{1} ∩ B_{1} + x) ∩ (A_{2} ∪ B_{2}),

and hence

A_{1} ∩ B_{1} + A_{2} ∪ B_{2} = A_{1} ∪ B_{1} + A_{2} ∩ B_{2}.  (5.6.3)

Without loss of generality we may assume that assumption (5.6.1) is satisfied. Then by Proposition 1.2 we have:

A_{1} + B_{2} = A_{1} ∪ B_{2} + A_{1} ∩ B_{2} = A_{2} ∪ B_{2} + A_{1} ∩ B_{1}.  (5.6.4)

Now let us put F := A_{2} ∩ B_{2} and G := A_{2} ∪ B_{2}. Then we have G ⊆ A_{1} ∪ B_{1} and F ⊆ A_{1}∩B_{1}, and by Theorem 5.1 there exists a pair (A_{0}, B_{0}) ∈ K^{2}(X) which is equivalent to (A_{1}, B_{1}) and such that

A_{1} + B_{0} = A_{1} ∪ B_{1} + F = A_{1} ∩ B_{1} + G = B_{1} + A_{0}  (5.6.5)

and moreover A_{0} ∩ B_{0} = F and A_{0} ∪ B_{0} = G. From equation (5.6.4) we obtain A_{1} + B_{0} = A_{1} + B_{2}, and hence B_{0} = B_{2}. Now we observe that A_{0} + B_{0} = F + G = A_{2} + B_{2}, and hence we have A_{0} = A_{2}.

6. Application to the quasidifferential calculus

For an arbitrary real topological vector space X a characterization of a convex pair (A, B) ∈ K^{2}(X) has been given in [16] and is stated in Theorem 1.1. In the following we restrict our attention to the case of a locally convex topological vector space X and will describe the charactization of a convex pair in terms of its support functions. Therefore let X be a locally convex topological vector space and X^{∗} the topological dual, i.e. the linear space of all continuous linear functional defined on X, endowed with the weak-*-topology. Moreover let us denote by

⟨·, ·⟩ : X^{∗} × X → IR

be the dual pairing given by

⟨ v, x ⟩ := v(x).

Then the “support function” of A ∈ K(X) is given by

p_{A} : X^{∗} ⟶ IR

with

p_{A}(x) = max_{a∈A} ⟨a, x⟩.

It was shown by L. Hörmander [4] that the support function is sublinear and continuous with respect to the weak-*-topology on X^{∗}. There exists a partial order on the set of support functions, namely

p_{A} ≤ p_{B} if and only if for every x ∈ X^{∗} p_{A}(x) ≤ p_{B}(x) ⟺ A ⊆ B.

For a locally convex topological vector space X we will now give a characterization of a convex pair (A, B) ∈ K^{2}(X) in terms of the support functions p_{A} and p_{B}.

Let us furthermore denote by

D(X^{∗}) := {φ = p_{A} − p_{B} | (A, B) ∈ K^{2}(X)}

the real vector space of differences of support functions.

Theorem 6.1. Let X be a locally convex topological vector space and (A, B) ∈ K^{2}(X). Then the pair (A, B) is convex if and only if

min{p_{A}, p_{B}} : X^{∗} ⟶ IR

is a convex function.

Proof. “⟹” By Theorem 1.1 the pair (A, B) ∈ K^{2}(X) is convex if and only if A∨B is a summand of A+B. This means that there exists an S ∈ K(X) such that A+B = A∨B + S. From property (iv) of Theorem 1.1 follows easily that S = A ∩ B. Hence we have:

A + B = A ∨ B + A ∩ B.

But since for the support function of A ∨ B the formula (see [4]) p_{A∨B} = max{p_{A}, p_{B}} holds this equation can be formulated in terms of support functions as:

p_{A} + p_{B} = max{p_{A}, p_{B}} + p_{A∩B}.

Now we have min{p_{A}, p_{B}} = p_{A∩B}, since for arbitrary real numbers a, b ∈ IR the formula a + b = max{a, b} + min{a, b} holds. “⟸” Now assume that min{p_{A}, p_{B}} is convex. Since this function is also positively homogeneous there exists an S ∈ K(X) such that min{p_{A}, p_{B}} = p_{S}. Hence we have

p_{A} + p_{B} = max{p_{A}, p_{B}} + min{p_{A}, p_{B}} = p_{A∨B} + p_{S},

which means that

p_{A + B} = p_{A∨B} + p_{S} = p_{A∨B+S}.

From this follows that

A + B = A ∨ B + S,

(see [4]), which means that A ∨ B is a summand of A + B. Hence by Theorem 1.1 the set A ∪ B is convex.

Let us remark, that for A, B ∈ K(X) with A ∩ B ≠ ∅ the support function of A ∩ B is the “infimal convolution” (see [11]) p_{A} p_{B} given by:

p_{A} p_{B} : X^{∗} ⟶ IR

with

(p_{A} p_{B})(x) := inf{p_{A}(x − v) + p_{B}(v) | v ∈ X^{∗}}.

Hence we have the following

Corollary 6.2. Let X be a locally convex topological vector space and (A, B) ∈ K^{2}(X). Then the pair (A, B) is convex if and only if

min{p_{A}, p_{B}} = p_{A} p_{B}.

Observe that the representation of the elements of the space D(X^{∗}) is not unique. From the obove mentioned characterization of a convex pair, we are able to show, that some special types of representations exist.

Proposition 6.3. Let X be a locally convex topological vector space and

D(X^{∗}) := {φ = p_{A} − p_{B} | (A, B) ∈ K^{2}(X)}

the real vector space of differences of support functions, defined on X^{∗}. Then for every element φ ∈ D(X^{∗}) there exist the following types of representations:

(i) φ ∈ D(X^{∗}) can be represented as φ = p_{A} − p_{B} with min{p_{A}, p_{B}} ≥ 0 (ii) φ ∈ D(X^{∗}) can be represented as φ = p_{A_{0}} −p_{B_{0}} such that min{p_{A_{0}}, p_{B_{0}}} is a sublinear

function and that p_{A_{0}} +p_{B_{0}} is minimal, i.e. p_{A_{0}} +p_{B_{0}} = min{p_{A}+p_{B} | φ = p_{A}−p_{B}} (iii) There exists a C ∈ K(X) such that for every representation of φ ∈ D(X^{∗}) as φ =

p_{A} − p_{B} the function min{p_{A}, p_{B}} + p_{C} is sublinear.

Proof. (i) The first assertion follows immediately from the Theorem of Hahn-Banach. Namely let

φ(h) := sup_{v∈A}⟨ h, v ⟩ − sup_{v∈B}⟨ h, v ⟩.

Then we can add to the first summand a continuous linear functional f_{1} ∈ X^{⋆⋆}, given by f_{1}(h) := ⟨u_{1}, h⟩, u_{1} ∈ X, with

sup_{v∈A}⟨ h, v ⟩ ≥ f_{1}(h)

and, analogously, to the second summand a f_{2} ∈ X^{⋆⋆}, f_{2}(h) := ⟨u_{2}, h⟩, u_{2} ∈ X with

sup_{v∈B}⟨ h, v ⟩ ≥ f_{2}(h).

Now we take a representation:

φ(h) = (sup_{v∈A}⟨ h, v ⟩−f_{1}(h)+max{f_{1}(h)−f_{2}(h), 0})−(sup_{v∈B}⟨ h, v ⟩−min{f_{2}(h)−f_{1}(h), 0}).

Now we prove part (ii) Since every pair (A, B) ∈ K^{2}(X) is equivalent to a convex pair, namely (A, B) ∼ (A + A ∨ B, B + A ∨ B) there exists a minimal convex pair (A_{0}, B_{0}) equivalent to (A, B). From Theorem 1.1 and Proposition 3.15 follows, that min{p_{A_{0}}, p_{B_{0}}} is convex and p_{A_{0}} + p_{B_{0}} is minimal. Part (iii) follows immediately from Theorem 3.5. Namely for the class [A, B] there exists a minimal element C ∈ K(X) such that for all (A′, B′) ∈ [A, B] the pair (A′ +C, B′ +C) is convex. Hence by Theorem 1.1 we have that min{p_{A′+C}, p_{B′+C}} = min{p_{A′}, p_{B′}} + p_{C}, which means that the function min{p_{A′}, p_{B′}} + p_{C} is sublinear.

Now let us turn our attention to the class of quasidifferentiable functions which where introduced by V.F. Demyanov and A.M. Rubinov [1]. We will start with the definition of a quasidifferentiable function defined on an open subset of a normed vector spaces. (see: [1]). Let (X, ∥ · ∥) be a real normed vector space, let X^{∗} be its topological dual, and let U ⊆ X be an open subset of X.

Definition 6.4. A continuous real valued function f : U → IR is said to be quasidifferentiable at x_{0} ∈ U if the following two conditions are satisfied:

(a) For every g ∈ X \ {0} the directional derivative

\frac{df}{dg} |_{x_{0}} = lim_{t→0+} \frac{f(x_{0} + tg) − f(x_{0})}{t}

exists.

(b) There exist two sets \underline{∂}f|_{x_{0}}, \overline{∂}f|_{x_{0}} ∈ K(X^{∗}) such that

\frac{df}{dg} |_{x_{0}} = max_{v∈\underline{∂}f|_{x_{0}}}⟨v, g⟩ + min_{w∈\overline{∂}f|_{x_{0}}}⟨w, g⟩.

Here K(X^{∗}) denotes the collection of all nonempty weak-*-compact convex subsets of X^{∗}. We remark that, by the Theorem of Alaoglu ( cf. [12], p. 228) the elements of K(X^{∗}) are bounded in the dual norm. Observe that the condition (b) is equivalent to the requirement that the directional derivative as a function of the direction g can be expressed as the difference of two sublinear functions. Although the quasidifferential Df|_{x_{0}} = ( \underline{∂}f|_{x_{0}}, \overline{∂}f|_{x_{0}} ) is not uniquely determined it preserves certain properties within an equivalence class. In [1], chapter 17, it is shown that for a quasidifferentiable function all steepest ascentand descent directions can be explicitely determined. Namely, if for a given quasidifferentiable function f : U ⟶ IR a quasidifferential Df|_{x_{0}} = ( \underline{∂}f|_{x_{0}}, \overline{∂}f|_{x_{0}} ), in x_{0} ∈ U ⊂ X is known, then every steepest descent direction of the function f in x_{0} is given by

g^{∗} := −\frac{w_{0} + v_{0}}{∥w_{0} + v_{0}∥^{∗}}  (6.4.1)

with

∥w_{0} + v_{0}∥^{∗} = sup_{w∈\overline{∂}f|_{x_{0}}} inf_{v∈\underline{∂}f|_{x_{0}}} ∥w + v∥^{∗},  (6.4.2)

where ∥.∥^{∗} denotes the dual norm. An analogue formula holds for the steepest ascent direction. If the quasidifferentiable function f : U ⟶ IR has a local maximum in x_{0} ∈ U then the formulas (6.4.1) and (6.4.2) imply that

−\overline{∂}f|_{x_{0}} ⊆ \underline{∂}f|_{x_{0}}  (6.4.3)

and analogously for a local minimum in x_{0} ∈ U of the function f : U ⟶ IR in x_{0} ∈ U one has

−\underline{∂}f|_{x_{0}} ⊆ \overline{∂}f|_{x_{0}}.  (6.4.4)

Hence we see, that in the case of a local extremum of a quasidifferentiable function f : U ⟶ IR in x_{0} ∈ U the class [ \underline{∂}f|_{x_{0}}, −\overline{∂}f|_{x_{0}} ] is convex and that it is C-minimal for every C := {p}, p ∈ X.

7. Examples of different types of minimality

Example 7.1. Let X := IR^{2} and let us put 0 := (0, 0), a := (0, 1), b := (1, 1), c := (1, 0) and put d := b + c. Now we define the following compact convex sets:

\begin{aligned}A_{0} & := 0 ∨ a \\ A_{1} & := A_{0} ∨ b \\ A_{2} & := A_{0} + I_{0} \\ A_{3} & := A_{0} + I_{1} \\ A_{4} & := A_{1} + I_{1} \end{aligned}  \begin{matrix}, \\ , \\ , \\ , \\ , \end{matrix}  \begin{aligned}B_{0} & := 0 ∨ b ∨ c \\ B_{1} & := B_{0} ∨ d \\ B_{2} & := B_{0} + I_{0} \\ B_{3} & := B_{0} + I_{1} \\ B_{4} & := B_{1} + I_{1} \end{aligned}

where I_{0} := 0 ∨ c and I_{1} := 0 ∨ b. Moreover put b_{1} := 2b and c_{1} := c + b_{1}.

It is obvious that (A_{0}, B_{0}) is equivalent to (A_{2}, B_{2}) and (A_{3}, B_{3}). Moreover (A_{4}, B_{4}) is equivalent to (A_{1}, B_{1}). Now we show that (A_{0}, B_{0}) is equivalent to (A_{1}, B_{1}). This can be seen as follows: First we have:

(A_{1} + c) ∪ B_{0} = B_{1} and (A_{1} + c) ∩ B_{0} = A_{0} + c.

Now from [16] Corollary 2.4 follows that

B_{0} + A_{1} + C = A_{0} + c + B_{1} and hence B_{0} + A_{1} = A_{0} + B_{1},

which means that (A_{0}, B_{0}) ∼ (A_{i}, B_{i}) for i ∈ {1, 2, 3, 4}. Moreover it follows immediately from [7] Theorem 2.1 that the pair (A_{0}, B_{0}) is minimal. The pair (A_{1}, B_{1}) is convex and (A_{1} ∪ B_{1}, A_{1} ∩ B_{1}) = (A_{1} ∪ B_{1}, I_{1}). Since the pair (A_{1} ∪ B_{1}, I_{1}) is minimal, it follows from Theorem 1.4 that the pair (A_{1}, B_{1}) is minimal convex. Now observe that

(A_{0} ∨ B_{0}, A_{0} + B_{0}) ∼ (A_{0} + I_{0}, A_{0} + B_{0}) ∼ (I_{0}, B_{0}),

and since (I_{0}, B_{0}) is a minimal pair it follows by Theorem 3.3 that the pair (A_{0}, B_{0}) is C-minimal with C := I_{0}. Moreover we have A_{2} = A_{0} + C and B_{2} = B_{0} + C. Since B_{0} = (A_{0} + C) ∩ (B_{0} + C), it follows from Proposition 3.14 that the class [A_{0}, B_{0}] is C-minimal. Now we will prove that the pair (A_{4}, B_{4}) is a convex hull of the pair (A_{3}, B_{3}). Therefore suppose that there exists a convex pair (C, D) ∈ K^{2}(X) such that

(A_{3}, B_{3}) ≤ (C, D) ≤ (A_{4}, B_{4}).

Then

A_{3} ∩ B_{3} = I_{1} ⊂ C ∩ D ⊂ A_{4} ∩ B_{4} = 2 · I_{1}.

If we assume that C ∩ D ≠ A_{4} ∩ B_{4}, then there exists a point p ∈ 2 · I_{1}, p ≠ b_{1} such that C ∩ D = [(0, 0), p]. But since C ∪ D is convex, the intersection C ∩ D separates the sets C and D. Now for the two points a_{1} ∈ C and b_{1} ∈ D we have [a_{1}, b_{1}] ∩ C ∩ D = ∅. This is a contradiction and therefore we have p = b_{1} and C ∩ D = A_{3} ∩ B_{3}. From [16] Corollary 3.7 it follows, that C = A_{4} and D = B_{4}. Moreover we have that A_{3}+x ⊆ A_{4} implies that x = 0, and hence the pair (A_{4}+x, B_{4}+x) is not a convex hull of the pair (A_{3}, B_{3}) for x ≠ 0.

Example 7.2. Let X := IR^{2} and let us put

A := {(−1, 0)}∨{(0, −1)}∨{(1, 0)}∨{(1, 1)} and B := A + x_{0} with x_{0} := (2, 0).

Then the pair (A, B) ∈ K^{2}(IR^{2}) is not convex.

Given any c_{α} := α · a + (1 − α) · b, 0 ≤ α ≤ 1, where a := (0, 1) and b := (2, 1). Now we consider

C_{α} := {−c_{α}} ∨ {c_{α}} ∨ {(c_{α} − x_{0})} ∨ {(x_{0} − c_{α})}, and D_{α} := C_{α} + x_{0}.

The pair (C_{α}, D_{α}) is a convex hull of the pair (A, B). We observe that for every x ≠ 0 the pair (C_{α} + x, D_{α} + x) is not a convex hull of (A, B). Moreover

⋂_{0≤α≤1}C_{α} = A and ⋂_{0≤α≤1}D_{α} = B.

A minimal pair which is equivalent to the pair (A, B) is the pair ({0}, {x_{0}}) and a convex minimal pair of (A, B) is the pair ([0, x_{0}], [x_{0}, 2 · x_{0}]).

Example 7.3. Let X := IR^{2} and let us put

\begin{matrix}A := \{(0, 0)\} ∨ \{(0, 1)\} & , B := \{(0, 0)\} ∨ \{(1, 0)\} \\ C := \{(0, 1)\} ∨ \{(1, 0)\} & , D := C ∨ \{(1, 1)\}. \end{matrix}

It is easy to see that the pair (A ∨ B, A + B) is equivalent to the pair (C, D). Moreover by Theorem 1.4 the pair (A + C, B + C) is convex minimal.

Example 7.4. Let X := IR^{2} and let us put

A := \{(0, 1)\} ∨ \{(\frac{1}{2}\sqrt{3}, −\frac{1}{2})\} ∨ \{(−\frac{1}{2}\sqrt{3}, −\frac{1}{2}, 0)\}, and B := −A.

Then the pair (A, B) ∈ K(IR^{2}) is minimal.

Also (A ∨ B, A + B) is minimal. Hence by Theorem 1.4 we see that the pair (A + A ∨ B, B + A ∨ B) is minimal convex. Since (A + A ∨ B) ∩ (B + A ∨ B) = A + B, it follows from Proposition 3.14 that the class [A, B] is C-minimal with C = A ∨ B.

Example 7.5. Let X := IR^{2} and let us put

A := {(0, 0)} ∨ {(0, 1)} and B := {(0, 0)} ∨ {(1, 0)} ∨ {(1, 1)}.

Then the following pairs (A′_{j}, B′_{j}) for j ∈ {1, ..., 7} and the convex pairs (A_{k}, B_{k}) for k ∈ {1, ..., 8} are equivalent to the pair (A, B) and the pair (A_{8}, B_{8}) is minimal convex.

The first assertion can be seen by using subsequently the reduction technique for pairs of compact convex sets (see [8] Theorem 2.6).

Now we construct the convex pairs (A_{k}, B_{k}) for k ∈ {1, ..., 8}. Let us put A_{1} := A+A∨B and B_{1} := B + A ∨ B. Then the pair (A_{1}, B_{1}) is convex and equivalent to the pair (A, B). Moreover the following convex pairs (A_{k}, B_{k}) for k ∈ {2, ..., 8} are equivalent to (A_{1}, B_{1}) and from Theorem 1.4 follows, that the pair (A_{8}, B_{8}) is minimal convex.

References

[1] V. F. Demyanov and A. M. Rubinov: Quasidifferential calculus, Optimization Software Inc., Publications Division, New York, 1986.

[2] R. Engelking: General Topology, PWN - Polish Scientific Publishers, Warszawa, 1977.

[3] J. Grzybowski: Minimal pairs of compact convex sets, Arch. Math. 63 (1994) 173–181.

[4] L. Hörmander: Sur la fonction d’ appui des ensembles convexes dans un espace localement convex, Arkiv för Matematik 3 (1954) 181–186.

[5] D. Pallaschke, P. Recht, R. Urbański: On locally Lipschitz quasidifferentiable functions in Banach spaces, Optimization 17 (1986) 287–295.

[6] D. Pallaschke, S. Scholtes, R. Urbański: On minimal pairs of compact convex sets, Bull. Acad. Polon. Sci. Sér. Math. 39 (1991) 1–5.

[7] D. Pallaschke and R. Urbański: Some criteria for the minimality of pairs of compact convex sets, Zeitschrift für Operations Research 37 (1993) 129–150.

[8] D. Pallaschke and R. Urbański: Reduction of quasidifferentials and minimal representations, Mathem. Programming, (Series A) 66 (1994) 161–180.

[9] D. Pallaschke and R. Urbański: A continuum of minimal pairs of compact convex sets which are not connected by translations, Journ. of Convex Analysis 3, No. 1 (1996) 83–95.

[10] A. G. Pinsker: The space of convex sets of a locally convex space, Trudy Leningrad Engineering-Economic Institute, 63 (1966) 13–17.

[11] R. T. Rockafellar: Convex Analysis, Princeton University Press, Princeton, New Jersey, 1970.

[12] S. Rolewicz: Metric linear spaces, PWN Warszawa and D.Reidel Publ. Company, Boston, 1984.

[13] A. M. Rubinov and I. S. Akhundov: Differences of compact sets in the sense of Demyanov and its Application to Non-Smooth Analysis, Optimization 23 (1992) 179–189.

[14] S. Scholtes: Minimal pairs of convex bodies in two dimensions, Mathematika 39 (1992) 267–273.

[15] R. Urbański: A generalization of the Minkowski-Rådström-Hörmander Theorem, Bull. Acad. Polon. Sér. Sci. Math. 24 (1976) 709–715.

[16] R. Urbański: On minimal convex pairs of convex compact sets, Arch. Math. 67 (1996) 226–238.

26 D.Pallaschke, W.Urbańska, R.Urbański / C-minimal pairs of compact convex sets HIER :

Leere Seite