Let {S1, S2, . . . , Sn} be a collection of nonempty compact subsets of an m-dimensional linear space, and let x conv We

Let {S1, S2, . . . , Sn} be a collection of nonempty compact subsets of an m-dimensional linear space, and let x ˆˆ conv

We consider the Cartesian product of the convex hulls of Si, namely

Every point in P is an n-tuple (x1, x2, . . . , xn) where each xi belongs to the corresponding conv Si. Let P(x) denote the subset of P for which

1. Show that
a. P(x) is compact and convex.
b. P(x) is nonempty.
c. P(x) has an extreme point z = (z1, z2, . . . , zn) such that
€¢ zi ˆˆ conv Si for every i

2. At least n - m components zi of z = (z1, z2, . . . , zn) are extreme points of their sets conv Si. To show this, assume the contrary. That is, assume that there are l > m components of z that are not extreme points of conv Si. Without loss of generality, suppose that these are the first l components of z.
a. For i = 1, 2, . . . , l, there exists yi ˆˆ X such that
zi + yi ˆˆ conv Si and zi - yi ˆˆ conv Si
b. There exists numbers α1, α2, . . . , αl , |ai| ‰¤ 1 such that
α1y1 + α2y2 + ... + αlyl = 0
c. Define

Show that z+ and z- belong to P(x).
d. Conclude that z is not an extreme point of P(x), contradicting the assumption. Hence at least (n - m) of the zi are extreme points of the corresponding conv Si.
3. z is the required representation of x, that is

and zi ˆˆ Si for all but at most m indexes i.

P - IIconv S, 2l Xi = X, that is, P(x) = (Xi, X2, . . . , Xn ) : Xi E conv S, and x,-x Z1+1 Z1+1 -z e conv S