<<

. 10
( 59 .)



>>


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

<<

. 10
( 59 .)



>>