Page 431 - Advanced Linear Algebra

Positive Solutions to Linear Systems: Convexity and Separation 415

Definition The convex hull of a set : ~ ¸% ÁÃÁ% ¹ of vectors in s is the

:
smallest convex set in s that contains . We will denote the convex hull of :
by 9²:³ .
Here is a characterization of convex hulls.

Theorem 15.3 Let : ~ ¸% ÁÃÁ% ¹ be a set of vectors in s . Then the convex

hull 9 is the set of all convex combinations of vectors in , that is,
:
"²:³
9 "²:³~ • ! % b Ä b ! % “ !  Á ! ~ E
D

Proof. Clearly, if is a convex set that contains , then also contains .
+
:
+
"
Hence " 9 ‹²:³ . To prove the reverse inclusion, we need only show that is
"
convex, since then :‹ " implies that ²:³ ‹ " 9 . So let

? ~ ! % bÄb! %

@ ~ % bÄb %

be in . If b ~ and  Á  then
"
? b @ ~ ²! % bÄb! % ³ b ² % b Äb % ³

~ ² ! b ³% b Ä b ² ! b ³%
But this is also a convex combination of the vectors in , because
:
 ! b  ² b ³h max ² Á ! ³ ~ max ² Á ! ³ 

and

² ! b ³ ~ ! b ~ b ~

~ ~ ~
Thus, ? b @  " .
Theorem 15.4 The convex hull 9²:³ of a finite set : ~ ¸% Á Ã Á % ¹ of vectors

in s is a compact set.
Proof. The set
+ ~ ²! ÁÃÁ! ³ “  !  Á ! ~ E
D

is closed and bounded in s and therefore compact. Define a function

¢ + ¦ s as follows: If ! ~ ²! ÁÃÁ! ³, then

²!³ ~ ! % b Ä b ! %

To see that is continuous, let ~ ² Á Ã Á ³ and let 4 ~ ² % max )) ³ . Given
€ , if )
)
c !  ° 4 then