Journal of Convex Analysis Volume 3 (1996), No.1, 83–95

A Continuum of Minimal Pairs of Compact Convex Sets which are not Connected by Translations

Diethard Pallaschke

Institut für Statistik und Mathematische Wirtschaftstheorie, Universität Karlsruhe, Kaiserstr. 12, 76128 Karlsruhe, Germany.

Ryszard Urbański

Wydział Matematyki i Informatyki Uniwersytetu im Adama Mickiewicza, ul. Matejki 48/49, 60-769 Poznań, Poland.

Received May 24, 1994 Revised manuscript received July 3, 1995

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

Pairs of compact convex sets naturally arise in quasidifferential calculus as the sub- and superdifferentials of the directional derivative of a quasidifferentiable function (see [1]). Since the sub- and superdifferential in a given point 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 [2],[13]). For the 3-dimensional case, J. Grzybowski [2] gave an example of finitely many equivalent minimal pairs of compact convex sets which are not connected by translations. In this paper we construct for the 3-dimensional case a continuum of equivalent minimal pairs of compact convex sets which are not connected by translation for different indices. Moreover, we present a more general method of reducing pairs of compact convex sets by hyperplanes as in [7].

Keywords : Convex Analysis, quasidifferential calculus, pairs of compact convex sets.

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

1. Introduction

In this note we consider inclusion minimal representants for elements of the Rådström -Hörmander lattice of equivalence classes of pairs of nonempty compact convex sets (see [4], [6], [7], [9], [10]). 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 the relation (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, B) ∼ (C, D) and A ⊆ C, B ⊆ D. Pairs of compact convex sets naturally arise in quasidifferential calculus as the sub- and superdifferentials of the directional derivative of a quasidifferentiable function (see [1], [11]).

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

84 D. Pallaschke, R. Urbański / A continuum of minimal pairs of compact convex sets

To be more precise: Let U ⊆ X be an open subset of a real locally convex topological vector space. A continuous function f : U → IR is said to be quasidifferentiable at x_{0} ∈ U if and only if the following conditions are satisfied:

i) for every h ∈ X the directional derivative

\frac{df}{dh}|_{x_{0}} = lim_{{α→0 \atop α>0}} \frac{f(x_{0} + αh) − f(x_{0})}{α}

exists; ii) there exist two nonempty weak-*-compact convex subsets \overline{∂}f|_{x_{0}}, \underline{∂}f|_{x_{0}} ⊆ X^{∗} such

that

\frac{df}{dh}|_{x_{0}} =: df|_{x_{0}}(h) = sup_{v∈\underline{∂}f|_{x_{0}}}< v, h > + inf_{v∈\overline{∂}f|_{x_{0}}}< v, h > ,

where < , > denotes the dual pairing.

Note that a quasidifferential Df|_{x_{0}} = ( \underline{∂}f|_{x_{0}}, \overline{∂}f|_{x_{0}} ) is not uniquely determined, which is a severe drawback as pointed out in [3].

Therefore a reduction or even a minimal representation of a quasidifferential is of special importance. In this connection, we mention the following two problems:

i) In [1], chapter 17, it is shown that for a quasidifferentiable function of max-min-type (i.e. a function generated by finitely many max- and min-operations over a finite set of C^{1}-functions) all steepest ascent- and descent directions can be determined from a quasidifferential by solving finitely many convex quadratic programs. In fact, given a quasidifferential Df|_{x_{0}} = ( \underline{∂}f|_{x_{0}}, \overline{∂}f|_{x_{0}} ), then every steepest descent direction in x_{0} ∈ IR^{n} is given by

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

with

∥w_{0} + v_{0}∥ = sup_{\overline{∂}f|_{x_{0}}} inf_{\underline{∂}f|_{x_{0}}} ∥w + v∥.

An analogous formula holds for the steepest ascent-directions. For a function of max-min-type, the sets \underline{∂}f|_{x_{0}}, \overline{∂}f|_{x_{0}} can be choosen as polytopes. Since the steepest ascent- and descent directions are invariants of a function, the latter formulas led to the investigation of minimal representations of quasidifferentials.

ii) In [11] the relation between the Clarke subdifferential ∂_{cl}f|_{x_{0}} and a quasidifferential Df|_{x_{0}} = ( \underline{∂}f|_{x_{0}}, \overline{∂}f|_{x_{0}} ) is investigated. In this connection two operations, considered as “set-differences” are introduced, namely:

\overline{∂}f|_{x_{0}} ˙− \underline{∂}f|_{x_{0}} and \overline{∂}f|_{x_{0}} ¨− \underline{∂}f|_{x_{0}}.

For a large class of locally Lipschitz quasidifferentiable functions, which contain all functions of max-min-type, the following inclusions are proved:

\overline{∂}f|_{x_{0}} ˙− (−\underline{∂}f|_{x_{0}}) ⊆ ∂_{cl}f|_{x_{0}} ⊆ \overline{∂}f|_{x_{0}} ¨− (−\underline{∂}f|_{x_{0}})

While the first expression is independent of the specific choice of a quasidifferential,

(since ∂_{cl}(df|_{x_{0}}(h)|_{h=0} = \overline{∂}f|_{x_{0}} ˙− (−\underline{∂}f|_{x_{0}}) ) the second depends on it. To get a

good upper bound for Clarke’s subdifferential, it is therefore of considerable interest to work with a minimal representant of the quasidifferential.

In this paper, we will show that in Euclidean space IR^{n} of dimension greater or equal to three there exists a continuous family of equivalent minimal pairs of compact convex sets which are not connected by translations. So the use of minimal pairs of compact convex sets may not necessarily lead to an essential reduction of the two problems mentioned above, i.e of determining the steepest descent- or ascent-directions or the upper estimates for the Clarke-subdifferential. However, the classification of minimal pairs of nonempty compact convex sets is an interesting problem in Convex Analysis (see [10])

Let us first set some notations: Let X be a real topological vector space, f ∈ X^{∗} be a continuous linear functional, and K ⊆ X a nonempty compact convex set.

Then we denote by

H_{f}(K) := {z ∈ K | f(z) = max_{y∈K}f(y)}

the face of K with respect to f. For the sum of the faces of two nonempty compact convex sets A, B ⊆ X with respect to f ∈ X^{∗} the following identity holds:

H_{f}(A + B) = H_{f}(A) + H_{f}(B).

For A ∈ K(X) we denote by E(A) the set of extremal points. For two compact convex sets A, B ⊆ X we will use the notation

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

where the operation “conv” (see [10]) denotes the convex hull.

For a locally convex topological vector space X, A. Pinsker [8] proved the following identity about nonempty compact convex sets A, B, C ⊆ X :

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

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.

Finally let us state explicitely the order cancellation law (see [4], [9],[14]).

Let X be real topological vector space and A, B, C ⊆ X nonempty 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 locally convex 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.

2. The Reduction of Pairs of Nonempty Compact Convex Sets by Cutting Hyperplanes

Let X be a real locally convex topological vector space, A ⊆ X a nonempty compact convex set, and f ∈ X^{∗} a continuous linear functional. For a point z ∈ X let us put

A_{f,z}^{+} := {x ∈ A | f(x) ≥ f(z)}
A_{f,z}^{−} := {x ∈ A | f(x) ≤ f(z)}

and

A_{f,z} := {x ∈ A | f(x) = f(z)}.

In [7] we proved the following result:

Lemma 2.1. Let X be a real locally convex topological vector space, A ∈ K(X) a nonempty compact convex set, f ∈ X^{∗} a continuous linear functional, and let us assume that A_{f,z} ≠ ∅ for an element z ∈ X. Then the pairs

(A, A_{f,z}^{−}) and (A_{f,z}^{+}, A_{f,z}) ∈ K^{2}(X)

are equivalent. Now we are able to show how to reduce pairs of compact convex sets by hyperplanes.

Theorem 2.2. Let X be a locally convex topological vector space and (B, D) ∈ K^{2}(X).

a) Assume that there exist points z_{1}, d_{1} ∈ X and a continuous linear functional f_{1} ∈ X^{∗} \ {0} such that B_{f_{1},z_{1}} ≠ ∅ and B_{f_{1},z_{1}+d_{1}}^{−} = D_{f_{1,}z_{1}}^{−} + {d_{1}}. Then the pairs

(B, D) and (B_{f_{1},z_{1}}^{+} , D_{f_{1},z_{1}+d_{1}}^{+})

are equivalent.

b) Moreover, if there exist points z_{2}, d_{2} ∈ X and a continuous linear functional f_{2} ∈ X^{∗} \ {0} such that B_{f_{2},z_{2}} ≠ ∅, B_{f_{1},z_{1}}^{−} ∩ B_{f_{2},z_{2}}^{+} = ∅, D_{f_{1},z_{1}+d_{1}}^{−} ∩ D_{f_{2},z_{2}+d_{2}}^{+} = ∅, and D_{f_{2,}z_{2}+d_{2}}^{+} = B_{f_{2},z_{2}}^{+} + {d_{2}}. Then the pairs

(B, D) and (B_{f_{1},z_{1}}^{+} ∩ B_{f_{2},z_{2}}^{−} , D_{f_{1},z_{1}+d_{1}}^{+} ∩ D_{f_{2},z_{2}+d_{2}}^{−})

are equivalent.

Remark 2.3. This is a generalization of a reduction method, which was introduced in [7]. In other words: all parts of two compact convex sets which can be translated onto each other can be cut off without leaving the equivalence class.

The situation is illustrated in figure 1.

Proof. To prove part a) we cut the set D ∈ K(X) by {x ∈ X | f_{1}(x) = f_{1}(z_{1} + d_{1})}. This gives that D_{f_{1,}z_{1}+d_{1}} = B_{f_{1},z_{1}} + {d_{1}} ≠ ∅. Now by Lemma 2.1 we have:

B + B_{f_{1},z_{1}} = B_{f_{1},z_{1}}^{−} + B_{f_{1},z_{1}}^{+}

and

D + D_{f_{1},z_{1}+d_{1}} = D_{f_{1},z_{1}+d_{1}}^{−} + D_{f_{1},z_{1}+d_{1}}^{+}.

Since D_{f_{1,}z_{1}+d_{1}}^{−} = B_{f_{1},z_{1}}^{−} + {d_{1}} we write the second equation as:

D + D_{f_{1},z_{1}+d_{1}} = D_{f_{1},z_{1}+d_{1}}^{+} + B_{f_{1},z_{1}}^{−} + {d_{1}}.

Adding both equations i.e.

B_{f_{1},z_{1}}^{−} + B_{f_{1},z_{1}}^{+} + D + D_{f_{1},z_{1}+d_{1}} = B + B_{f_{1},z_{1}} + D_{f_{1},z_{1}+d_{1}}^{+} + B_{f_{1},z_{1}}^{−} + {d_{1}}

and simplifying the sum by B_{f_{1},z_{1}}^{−} and by D_{f_{1},z_{1}+d_{1}} = B_{f_{1},z_{1}} + {d_{1}} we get

(B, D) ∼ (B_{f_{1},z_{1}}^{+} , D_{f_{1},z_{1}+d_{1}}^{+}).

Figure 1

To prove part b) let us first observe that, by symmetry with respect to the origin in X, the statement obtained in part a) remains true if we exchange the exponents + and −.

Let us now apply the same technique to the sets B′ := B_{f_{1},z_{1}}^{+} and D′ := D_{f_{1},z_{1}+d1}^{+}.

By assumption we have:

D_{f_{2},z_{2}+d_{2}}^{′+} = D_{f_{2},z_{2}+d_{2}}^{+} = B_{f_{2},z_{2}}^{+} + {d_{2}} = B_{f_{2},z_{2}}^{′+} + {d_{2}},

and hence B′_{f_{2},z_{2}} ≠ ∅.

Now the symmetric part of a) gives for the pair (B′, D′) ∈ K^{2}(X) that

D′ + B_{f_{2},z_{2}}^{′−} = B′ + D_{f_{2},z_{2}+d_{2}}^{′+}.

By definition of B′ and D′ we have:

B_{f_{2},z_{2}}^{′−} = B_{f_{1},z_{1}}^{+} ∩ B_{f_{2},z_{2}}^{−}

and

D_{f_{2},z_{2}+d_{2}}^{′−} = D_{f_{1},z_{1}+d_{1}}^{+} ∩ D_{f_{2},z_{2}+d_{2}}^{−}.

Hence

(B, D) ∼ (B′, D′) ∼ (B_{f_{1},z_{1}}^{+} ∩ B_{f_{2},z_{2}}^{−} , D_{f_{1},z_{1}+d_{1}}^{+} ∩ D_{f_{2},z_{2}+d_{2}}^{−}),

which proves the assertion.

3. Properties of Equivalent Minimal Pairs of Compact Convex Sets which are constructed by a General Frustum

In [12] G. T. Sallee studied a special type of convex sets, called general frusta. By definition, a general frustum is the convex hull of two convex sets that lie in different parallel hyperplanes. We will restrict ourselves to the case of compact general frusta which can be defined as follows:

Let X be a real locally convex topological vector space, f ∈ X^{∗} a continuous linear functional, z ∈ X, with f(z) ≠ 0 and E, F ∈ K(X) a nonempty compact convex set with E, F ⊂ f^{−1}(0). Then

A := E ∨ (F + {z})

is called a general frustum over E and F.

Fixing the continuous linear functional, f ∈ X^{∗} and the point z ∈ X, with f(z) ≠ 0, we use the notation

A :=: IF(E, F) := E ∨ (F + {z})

for a general frustum over E and F.

Now we will consider pairs of general frusta:

Theorem 3.1. Let X be a real locally convex topological vector space, f ∈ X^{∗} a continuous linear functional, z ∈ X, with f(z) ≠ 0 and for i ∈ {0, 1} let E_{i}, F_{i}, U_{i}, V_{i} ∈ K(X) be nonempty compact convex sets, with E_{i}, F_{i}, U_{i}, V_{i} ⊂ f^{−1}(0). Let A_{i} := IF(E_{i}, F_{i}) := E_{i} ∨ (F_{i} + {z}) and B_{i} := IF(U_{i}, V_{i}) := U_{i} ∨ (V_{i} + {z}) be general frusta. Then

(A_{0}, B_{0}) ∼ (A_{1}, B_{1})

if and only if

i) (E_{0}, U_{0}) ∼ (E_{1}, U_{1}) ii) (E_{0} + V_{1}) ∨ (F_{0} + U_{1}) = (E_{1} + V_{0}) ∨ (F_{1} + U_{0}) iii) (F_{0}, V_{0}) ∼ (F_{1}, V_{1})

Proof. This equivalence is a direct consequence of the following representation of the sum of two general frusta. Let us omit for a moment the index i ∈ {0, 1} and consider the general frusta

A = IF(E, F) and B := IF(U, V).

Then the formula:

A + B = (E + U) ∨ ([(E + V) ∨ (U + F)] + {z}) ∨ ((F + V) + {2 · z}).

holds.

This formula can be shown as follows: Obviously we have

A + B ⊇ (E + U) ∨ ([(E + V) ∨ (U + F)] + {z}) ∨ ((F + V) + {2 · z}),

since the righthand side of the inclusion contains only sums of subsets of A and B.

Since for the extremal points of a general frustum we have: E(A) = E(E) ∪ {E(F) + {z}} and E(B) = E(U) ∪ {E(V) + {z}}, it follows that

E(A + B) ⊆ E(E + U) ∪ ([E(E + V) ∪ E(U + F)] + {z}) ∪ (E(F + V) + {2 · z}).

Now A + B is equal to the convex hull of E(A + B), which implies

A + B ⊆ (E + U) ∨ ([(E + V) ∨ (U + F)] + {z}) ∨ ((F + V) + {2 · z}),

and proves the formula.

The equivalence stated in the assertion follows now immediately from this formula.

Let us remark that condition ii) of the above theorem can be formulated in the commutative semi-ring K(X) endowed with the “addition #” given by:

A # B := A ∨ B

and the “multiplication ∗” given by:

A ∗ B := A + B.

by using the definition of the permanent, namely as:

perm [ \begin{matrix}E_{0} & U_{1} \\ F_{0} & V_{1} \end{matrix} ] = perm [ \begin{matrix}E_{1} & U_{0} \\ F_{1} & V_{0} \end{matrix} ] ,

i.e.

E_{0} ∗ V_{1} # F_{0} ∗ U_{1} = E_{1} ∗ V_{0} # F_{1} ∗ U_{0}

4. An uncountable Family of Equivalent Minimal Pairs of Compact Convex Sets, which are not connected by Translations

In [5] we posed the question whether equivalent minimal pairs of nonempty compact convex sets are uniquely determined up to translations. An affirmative answer for the two-dimensional case was independently given by J. Grzybowski [2] and S. Scholtes [13]. Moreover J. Grzybowski [2] showed by a counterexample in IR^{3} that this is not true for higher dimensional spaces. Using a different technique, we could show in [7] by modifying this counterexample that in every locally convex topological vector space X with dim X ≥ 3 there exist equivalent minimal pairs of compact convex sets which are not related by translations and each of these sets is of full dimension.

In this paper we will construct a continuous family (A_{α}, B_{α}) ∈ K^{2}(IR^{3}), α ∈ [0, ∞) of equivalent minimal pairs of compact convex sets such that any two pairs with different indices are not related by translations.

The minimality follows from a criterium proved in [6] which we recall bellow: Let X be a real locally convex topological vector space. For a nonempty compact convex set A ⊂ X we consider a set S ⊆ X^{∗} \ {0} such that

\overline{conv( ⋃_{f∈S} H_{f}(A))} = A.

The sets S ⊂ X^{∗} \ {0} of this type can be ordered by inclusion. A minimal element will be called a shape of A and will be denoted by S(A). For a shape S(A) we consider the subsets

S_{p}(A) := {f ∈ S(A) | card(H_{f}(A)) = 1}

which may be empty and put

S_{l}(A) := S(A) \ S_{p}(A);

i.e.

S(A) = S_{l}(A) ∪ S_{p}(A).

Using this notation the following result is proved in [6].

Theorem 4.1. Let X a real locally convex topological vector space, and let A, B ⊂ X be nonempty compact convex sets. Let us assume that there is a shape S(A) of A satisfying the following conditions:

a) for every f ∈ S(A) , card(H_{f}(B)) = 1

b) for every f ∈ S_{l}(A) and every b ∈ B, the condition S_{l}(A) + (b − H_{f}(B)) ⊆ A implies b = H_{f}(B).

c) for every f ∈ S_{p}(A) , H_{f}(A) − H_{f}(B) ∈ E(A − B) or conversely by interchanging A and B.

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

Remark 4.2. This is a sufficient crierium for minimality. In [6] we required for (b) a stronger condition. But the proof given in [6] is exactly the proof for the present formulation of this theorem.

In the following theorem we construct explicitely an uncountable family of equivalent minimal pairs (A_{α}, B_{α}) ∈ K^{2}(IR^{3}), α ∈ IR_{+} := {τ ∈ IR|τ ≥ 0} which are not connected by translations, i.e. for α, β ∈ IR_{+}, α ≠ β there exists no element x ∈ IR^{3} such that

A_{α} + x = A_{β} and B_{α} + x = B_{β},

namely:

Theorem 4.3. Let f ∈ (IR^{3})^{∗} be given by f(x) := f((x_{1}, x_{2}, x_{3})) := x_{3} and put z := e_{3} := (0, 0, 1) ∈ IR^{3}. For α ≥ 0 define the following sets:

i) E_{α} := conv{(0, 0, 0), (1, 1, 0), (1 + α, 0, 0)} ii) F_{α} := conv{(0, 1, 0), (α, 0, 0), (1 + α, 1, 0)} iii) U_{α} := conv{(0, 0, 0), (0, 1, 0), (1, 1, 0), (1 + α, 0, 0)} iv) V_{α} := conv{(0, 1, 0), (α, 0, 0), (1 + α, 0, 0), (1 + α, 1, 0)} Then the families of general frusta

A_{α} := IF(E_{α}, F_{α}) := E_{α} ∨ (F_{α} + {z})
B_{α} := IF(U_{α}, V_{α}) := U_{α} ∨ (V_{α} + {z})

form a family of equivalent minimal pairs

(A_{α}, B_{α}) ∈ K^{2}(IR^{3})

which are not connected by translations.

Remark 4.4. Before the proof of this theorem, let us draw a picture for illustration. Here, we identify the kernel of the linear functional f ∈ (IR^{3})^{∗} with the subspace IR^{2}, i.e. kern f = IR^{2}.

92 D. Pallaschke, R. Urbański / A continuum of minimal pairs of compact convex sets

D. Pallaschke, R. Urbański / A continuum of minimal pairs of compact convex sets 93

Proof. The proof goes in several steps:

i) We first show that for every α ∈ IR_{+} := {τ ∈ IR|τ ≥ 0} the pairs

(A_{0}, B_{0}) , (A_{α}, B_{α}) ∈ K^{2}(IR^{3})

are equivalent. Because

A_{α} := IF(E_{α}, F_{α}) := E_{α} ∨ (F_{α} + {z})

and

B_{α} := IF(U_{α}, V_{α}) := U_{α} ∨ (V_{α} + {z}),

therefore by Theorem 3.1 we have to show that

1) (E_{0}, U_{0}) ∼ (E_{α}, U_{α}),

2) (E_{0} + V_{α}) ∨ (F_{0} + U_{α}) = (E_{α} + V_{0}) ∨ (F_{α} + U_{0}),

3) (F_{0}, V_{0}) ∼ (F_{α}, V_{α}). The conditions 1) and 3) can be shown by using the reduction method, which is stated in Theorem 2.2, since for α ∈ IR_{+} := {τ ∈ IR|τ ≥ 0} the pairs

(E_{α}, U_{α}) ∼ (F_{0}, conv{(0, 0, 0) , (1, 1, 0)})

and

(F_{α}, V_{α}) ∼ (conv{(0, 0, 0) , (1, 1, 0)}, E_{0})

are equivalent. Condition 2) can be checked by a direct calculation, since

E_{α} + V_{0} = conv{(0, 0, 0), (0, 1, 0), (1, 2, 0), (2, 2, 0), (2 + α, 0, 0), (2 + α, 1, 0)}
F_{α} + U_{0} = conv{(0, 1, 0), (0, 2, 0), (2, 0, 0), (2 + α, 1, 0), (2 + α, 2, 0)}
E_{0} + V_{α} = conv{(0, 1, 0), (1, 2, 0), (2 + α, 2, 0), (α, 0, 0), (2 + α, 0, 0)}
F_{0} + U_{α} = conv{(0, 0, 0), (0, 2, 0), (2, 2, 0), (1 + α, 0, 0), (2 + α, 1, 0)}

Hence

(E_{0} + V_{α}) ∨ (F_{0} + U_{α}) =
conv{(0, 0, 0), (0, 2, 0), (2 + α, 0, 0), (2 + α, 2, 0)}
= (E_{α} + V_{0}) ∨ (F_{α} + U_{0})

ii) Next we show, that for every α ∈ IR_{+} := {τ ∈ IR|τ ≥ 0} the pair

(A_{α}, B_{α}) ∈ K^{2}(IR^{3})

is minimal. We shall use Theorem 4.1. Denote

a_{0} := (0, 0, 0) , b_{0} := (1, 1, 0) , c_{0} := (0, 1, 1) , d_{0} := (1, 0, 1)

and

a_{1} := (1, 1, 1) , b_{1} := (0, 0, 1) , c_{1} := (1, 0, 0) , d_{1} := (0, 1, 0)

94 D. Pallaschke, R. Urbański / A continuum of minimal pairs of compact convex sets

and for α ∈ IR_{+} := {τ ∈ IR|τ ≥ 0} put

s_{α} := α · c_{1} = (α, 0, 0)

Now we define the following sets:

G_{1} := a_{0} ∨ b_{0} ∨ c_{0} and G_{2} := a_{1} ∨ b_{1} ∨ c_{1}

and notice that

A_{α} := G_{1} ∨ (G_{2} + s_{α})

and

B_{α} := (d_{1} ∨ G_{1}) ∨ ((G_{2} ∨ d_{0}) + s_{α}).

Observe that as a shape for

A_{α} = G_{1} ∨ (G_{2} + s_{α}),

we can choose the set

S(A_{α}) := S_{l}(A_{α}) = {f_{1}, f_{2}}

with

H_{f_{1}}(A_{α}) = G_{1} and H_{f_{2}}(A_{α}) = G_{2} + s_{α}.

Since

S_{p}(A_{α}) = ∅,

we need only to check the conditions i) and ii) of Theorem 4.1. Condition i) of Theorem 4.1 follows easily from the equalities

H_{f_{1}}(B_{α}) = {d_{1}}

and

H_{f_{2}}(B_{α}) = {d_{0}}.

Furthermore, condition ii) can be deduced from the facts, that for x, y ∈ IR^{3} :

x + G_{1} ⊆ A_{α} implies x = 0

and

y + (G_{2} + s_{α}) ⊆ A_{α} implies y = 0.

It is obvious that for α, β ∈ IR_{+} with α ≠ β the pair (A_{α}, B_{α}) ∈ K^{2}(IR^{3}) is not a translation of the pair (A_{β}, B_{β}) ∈ K^{2}(IR^{3}) which completes the proof. This example generalizes essentially the example of J. Grzybowski [2] and suggests to restrict the definition of minimality.

Acknowledgment. We thank an anonymous referee for valuable hints and remarks.

References

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

[2] J. Grzybowski: On minimal pairs of convex compact sets, Archiv der Mathematik 63 (1994) 173–181.

[3] J.-B. Hiriart-Urruty: Miscellanies on Nonsmooth Analysis and Optimization, in: Nondifferentiable Optimization: Motivations and Applications, Proceedings, Sopron, Hungary (1984) Eds.: V.F.Demyanov, D. Pallaschke, Lecture Notes in Economics and Mathem. Systems, Vol. 255, Springer, Heidelberg (1985) 8–24.

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

[5] D. Pallaschke, S. Scholtes and R. Urbański: On Minimal Pairs of Compact Convex Sets, Bull. Acad. Polon. Sci., Sér. Sci. Math. 39 (1) (1991) 1–5.

[6] D. Pallaschke, R. Urbański: Some Criteria for the Minimality of Pairs of Compact Convex Sets, Zeitschrift für Operations Research (ZOR), Series Theory 37 (1993) 129–150.

[7] D. Pallaschke, R. Urbański: Reduction of Quasidifferentials and Minimal Representations, Math. Programming, Series A 66 (1994) 161–180.

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

[9] H. Rådström: An embedding theorem for spaces of convex sets, Proc. Amer. Math. Soc. 3 (1952) 165–169.

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

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

[12] G. T. Sallee: On the indecomposibility of the cone, Journ. London Math. Soc. 9 (1974) 363–367.

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

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

96 D. Pallaschke, R. Urbański / A continuum of minimal pairs of compact convex sets HIER :

Leere Seite