Hence z + B(x , r) and therefore in C. Now,

y : (z 9 x ) ; x : (z 9 x ) ; x ; x : z ; x .

Since C is convex, y + C.

We now suppose that x + C and x , C. Figure 2.5 will illustrate the idea of

the proof. In the ¬gure we again take #x 9 x # : 1.

PROPERTIES OF CONVEX SETS 39

Figure 2.5.

Since x + int(C), there exists an r 9 0 such that B(x , r) : C. To prove the

lemma, we must show that if x + (x , x ), then x + int(C). If x + (x , x ), there

exist 9 0, 9 0, ; : 1 such that x : x ; x . Also by relation (5) in

Section 1, #x 9 x #/#x 9 x # : / . Since x + C, there exists a z in C such

that #z 9 x # : r( / ). De¬ne

z : x 9 (z 9 x ).

Hence #z 9 x # : r, and so z + int(C). Also,

x: x ; x : z ; (z 9 x ) ; x

: z ; z.

Since z + int(C) and z + (C), by the case already proved, x + int(C).

C¬¬ 1. If C is convex, then int(C) is either empty or convex.

C¬¬ 2. L et C be convex and let int(C) "

. T hen (i) int(C) : C and (ii)

int(C) : int(C).

Before proving Corollary 2, we note that its conclusion need not be true if

C is not convex. To see this, take C : +rational points in [0, 1], 6 [1, 2].

CONVEX SETS IN RL

40

Proof. Since for any set C int(C) 3 C, it follows that int(C) 3 C. Let x + C.

Then for any y in int(C), the line segment [y, x) belongs to int(C). Hence

x + int(C), and so C 3 int(C).

Since, for any set C, C 3 C, it follows that int(C) 3 int(C). Let x + int(C ).

Then there exists an r 9 0 such that B(x, r) : C. Now let y + int(C) and

consider the line segment [y, z), which is the extension of the segment [y, x] a

distance less than r beyond x. Then z + C, and since y + int(C), we get that

[y, z) + int(C). In particular, x + int(C). Thus (ii) is proved.

For each positive integer n, de¬ne

L

P : p : (p , . . . , p ) : p . 0, p : 1 .

L LG G

G

For n : 1, P is the point 1. For n : 2, P is the closed line segment joining

(0, 1) and (1, 0). For n : 3, P is the closed triangle with vertices (1, 0, 0),

(0, 1, 0), and (0, 0, 1). It is easy to verify that, for each n, P is a closed convex

L

set.

De¬nition 2.2. A point x in RL is a convex combination of points x , . . . , x if

I

there exists a p : (p , . . . , p ) in P such that

I I

x:p x ;p x ;%;p x .

II

L 2.6. A set C in RL is convex if and only if every convex combination of

points in C is also in C.

Proof. If every convex combination of points in C is in C, then every convex

combination of every two points in C is in C. But for any ¬xed pair of points

x and x in C, the set of convex combinations of x and x is just [x , x ]. In

other words, for every pair of points x and x in C, the line segment [x , x ]

belongs to C, and so C is convex.

We shall prove the ˜˜only if™™ statement by induction on k, the number of

points in the convex combination. If C is convex, then the de¬nition of

convexity says that every convex combination of two points is in C. Suppose

that we have shown that if C is convex, then every convex combination of k

points is in C. We shall show that every convex combination of k ; 1 points

is in C. Let

x:p x ;%;p x ;p x , p+P .

II I> I> I>

: 1, then I p 9 0. Hence,

If p : 1, then there is nothing to prove. If p

G G

I> I>

I p p

x ;%; I x ;p x .

x: p

G Ip IpI I> I>

G G G G

G

PROPERTIES OF CONVEX SETS 41

The term in square brackets is a convex combination of k points in C and so

by the inductive hyotheses is in C. Therefore x is a convex combination of two

points in C, and so since C is convex, x belongs to C. This proves the lemma.

For a given set A, let K(A) denote the set of all convex combinations of

points in A. It is easy to verify that K(A) is convex. Clearly, K(A) 4 A.

De¬nition 2.3. The convex hull of a set A, denoted by co(A), is the intersection

of all convex sets containing A.

Since RL is convex, co(A) is nonempty, and since the intersection of convex

sets is convex, co(A) is convex. Also, since we have co(A) 3 C for any convex

set C containing A, it follows that co(A) is the smallest convex set containing A.

T 2.1. T he convex hull of a set A is the set of all convex combinations of

points in A; that is, co(A) : K(A).

Proof. Let +C , denote the family of convex sets containing A. Since

?

co(A) : 7 C and K(A) is a convex set containing A, co(A) 3 K(A). To prove

?

the opposite inclusion, note that A 3 C for each and Lemma 2.6 imply that

?

for each all convex combinations of points in A belong to C . That is, for

?

each , K(A) 3 C . Hence K(A) 3 7 C : co(A).

? ?

Lemma 2.6 states that a set C is convex if and only if K(C) 3 C. Since

C 3 K(C) for any set C, Lemma 2.6 can be restated in the equivalent form that

a set C is convex if and only if K(C) : C. Since, for any set A, K(A) : co(A),

we have the following corollary to Theorem 2.1.

C¬¬ 3. A set A is convex if and only if A : co(A).

T 2.2 (C¤). L et A be a subset of RL and let x + co(A). T hen

´

there exist n ; 1 points x , . . . , x in A and a point p in P such that

L> L>

x:p x ;%;p x .

L> L>

Note that since some of the p ™s may be zero, the result is often stated that

G

a point x + co(A) can be written as a convex combination of at most n ; 1

points of A.

Proof. If x + co(A), then by Theorem 2.1,

K

x: q x , x + A, i : 1, . . . , m, q : (q , . . . , q ) + P , (3)

GG G K K

G

for some positive integer m and some q in P . If m - n ; 1, then there is

K

CONVEX SETS IN RL

42

nothing to prove. If m 9 n ; 1, we shall express x as a convex combination of

at most m 9 1 points. Repeating this argument, a ¬nite number of times gives

the desired result.

Let us then suppose that in (3) m 9 n ; 1. Consider the m 9 1 9 n vectors

in RL, (x 9 x ), (x 9 x ), . . . , (x 9 x ). Since m 9 1 9 n, these vectors are

K K K\ K

linearly dependent. Hence there exist scalars , . . . , , not all zero such that

K\

(x 9 x ) ; (x 9 x ) ; % ; 9 x ) : 0.

(x

K K K\ K\ K

: 9( ;%; ). Then

Let

K K\

x ;%; ; x :0 (4)

x

K\ K\ KK

and

K

: 0. (5)

G

G

From (3) and (4) it follows that for any t

K

x : (q 9 t )x . (6)

G GG

G

We shall show that there is a value of t such that the coef¬cients of the x are

G

nonnegative, have sum equal to 1, and at least one of the coef¬cients is zero.

This will prove the theorem.

Let I : +i : i : 1, . . . , m, 9 0,. Since , . . . , are not all zero, it follows

G K

from (5) that I " `. Let i denote an index in I such that

q

G : min+i + I : q / ,.

GG

G

Now take t : q / . Then t . 0, and for i + I

G G

q q

G 9 G . 0,

(q 9 t ) :

G G G

G G

with equality holding for i : i . If i , I, then - 0, so q 9 t . 0 whenever

G G G

t . 0. Thus, if t : q / , then

G G

q 9 t . 0, i : 1, . . . , m with q 9 t : 0.

G G G G

Upon comparing this statement with (6), we see that we have written x as a

nonnegative linear combination of at most m 9 1 points. This combination is

PROPERTIES OF CONVEX SETS 43

also a convex combination since, using (5), we have

K K K K

(q 9 t ) : q 9 t : q : 1.

G G G G G

G G G G

L 2.7. If A is a compact subset of RL, then so is co(A).

If A is closed, then co(A) need not be closed, as the following example

shows. Let

A : +(x , x ) : x 9 0, x 9 0, x x . 1,

and let

A : +(x , x ) : x 9 0, x : 0, x x - 91,.

Let A : A 6 A . Then A is closed, but co(A) : +(x , x ) : x 9 0, is open.

We now prove the lemma. By Theorem 2.2

L>

co(A) : x : x : p x x + A p : (p , . . . , p ) + P .

GG G L> L>

G

Let

:P ;A;%;A

L>

L>

Since A is compact and P is compact, by Theorem I.8.1 the set is