Ha 3 H ; x ,

? x + H?. (8)

a a

Now let u be an arbitrary vector in H. Then u ; x + H ; x and

a a

1a, u ; x 2 : 1a, x 2 : .

Thus we get the inclusion opposite to the one in (8), and the lemma is proved.

Two hyperplanes Ha and Ha are said to be parallel if their normals are

scalar multiples of each other. Thus two hyperplanes are parallel if and only if

they are translates of the same hyperplane through the origin. The parallel

hyperplane through the origin is called the parallel subspace.

Exercise 1.1. (a) Draw a sketch in R and R that illustrates Lemma 1.1.

(b) In R sketch the hyperplane x ; 2y : 1 and the parallel subspace.

Exercise 1.2. (a) In R ¬nd an equation of the hyperplane through the points

(1, 1, 1, 1), (2, 0, 1, 0), (0, 2, 0, 1), and (1, 1, 91, 0).

(b) Let x , . . . , x be n points in RL. Find a suf¬cient condition for the

L

existence of a unique hyperplane containing these points.

Exercise 1.3. Show that a hyperplane is a closed set.

Exercise 1.4. Given a hyperplane H? show that a is indeed normal to Ha in the

?

a

sense that if x and x are any two points in H?, then a is orthogonal to

a

x 9x .

Exercise 1.5 (Linear Algebra Review). Let V be an (n 9 1)-dimensional sub-

space of RL. Let y be a vector in RL not in V. Show that every x in RL has a

unique representation x : v ; y where v + V and + R.

PROPERTIES OF CONVEX SETS 35

2. PROPERTIES OF CONVEX SETS

A subset C of RL is said to be convex if given any two points x , x in C the

line segment [x , x ] joining these points is contained in C. We now formulate

this de¬nition analytically.

De¬nition 2.1. A subset C of RL is convex if for every pair of points x , x in

C the line segment

[x , x ] : +x : x : x ; x , . 0, . 0, ; : 1,

belongs to C.

At this point the reader may ¬nd it helpful to do the following exercise.

Exercise 2.1. Sketch the following sets in R and determine from your ¬gure

which sets are convex and which are not:

(a) +(x, y) : x ; y - 1,,

(b) +(x, y) : 0 : x ; y - 1,,

(c) +(x, y) : y . x,,

(d) +(x, y) : "x" ; "y" - 1,, and

(e) +(x, y) : y . 1/(1 ; x),.

In R a plane determines two sets, one on each side of the plane. We extend

this notion to RL. The positive half space determined by Ha and denoted by H?>

? a

is de¬ned to be

H?> : +x : 1a, x2 9 ,. (1)

a

The negative half space H?\ is de¬ned to be

a

H?\ : +x : 1a, x2 : ,. (2)

a

The closed positive half space, denoted by H?>, is de¬ned to be the closure of

a

H?>. The closed negative half space H?\ is de¬ned to be the closure of Ha . ?\

a

a

Note that a half space is not a subspace of RL, since there exist points x in

a half space such that not all scalar multiples of x are in the half space.

Exercise 2.2. Show that

?> H?\ : +x : 1a, x2 - ,.

a

Ha : +x : 1a, x2 . ,,

CONVEX SETS IN RL

36

Figure 2.3.

If x + H?, then 1a, x 2 : . Hence, for x + Ha , we have 1a, x2 9 :

?>

a

1a, x 2. Therefore

1a, x 9 x 2 9 0 for all x + H?>.

a

Thus, vectors x in H?> are such that the angle between a, the normal to H?,

a a

and x 9 x lies between 0 and /2. In R and R this says that a and x 9 x

point in the same direction or have the same orientation. See Figure 2.3.

Half spaces are convex sets. Although this and other properties of convex

sets are ˜˜geometrically obvious™™ in R and R, they require proof in RL. To

show that H?> is convex, we must show that if x and x are in Ha , then so

?>

a

is [x , x ]. Let x + [x , x ]. Then there exist scalars . 0, . 0 with ; : 1

such that x : x ; x . Hence

1a, x2 : 1a, x ; x 2 : 1a, x 2 ; 1a, x 2 9 ; :,

and so x + H?>. Similar arguments show that Ha , H?>, H?\ and the

?\ a a

a

hyperplane H? are convex sets.

a

In the series of lemmas that follow we list some elementary properties of

convex sets. We shall provide proofs to show the reader how one ˜˜proves the

obvious.™™ When speaking of a convex set, we shall always assume that the

convex set is not empty.

L 2.1. L et +C , be a collection of convex sets such that C : 7 C is not

? ??

empty. T hen C is convex.

Proof. Let x and x belong to C. Then for each the points x and x

belong to C . Since for each the set C is convex, for each the line segment

? ?

[x , x ] belongs to C . Hence [x , x ] 3 C, so C is convex.

?

PROPERTIES OF CONVEX SETS 37

Let A be an m ; n matrix with ith row a : (a , . . . , a ) and let b :

G G GL

(b , . . . , b ) be a vector in RK. Let S denote the solution set of Ax - b. Then S

K

is the intersection of half spaces +x : 1a , x2 - b ,, so if S is nonempty, then S

G G

is convex.

Note that if A and B are convex sets, then A 6 B need not be convex.

If A and B are two sets in RL and if and are scalars, we de¬ne

A ; B : +x : x : a ; b, a + A, b + B,.

L 2.2. If A and B are convex sets in RL and and are scalars, then

A ; B is convex.

Proof. Let x and x belong to A ; B. We must show that [x , x ]

belongs to A ; B. We have x : a ; b for some a + A and b + B and

x : a ; b for some a + A and b + B. If x + [x , x ], then there exist

scalars . 0, . 0 with ; : 1 such that x : x ; x . Hence

x: x ; x : [ a ; b ]; [ a ; b ]

: ( a ; a ) ; ( b ; b ).

Since A and B are convex, the ¬rst term in parentheses on the right is an

element a in A and the second term in parentheses on the right is an element

b in B. Hence for arbitrary x + [x , x ],

x: a ; b ,

so [x , x ] 3 A ; B as required.

L 2.3. L et A 3 RL , A 3 RL ‚, . . . , A 3 RL I and let A , . . . , A be convex.

I I

T hen A ; % ; A is a convex set in RL >>LI.

I

We leave the proof as an exercise for the reader.

L 2.4. If A is convex, then so is A, the closure of A.

Proof. Let x and y be points of A. Let z + [x, y], so z : x ; y for some

. 0, . 0, ; : 1. By Remark I.5.2, there exist sequences +x , and +y ,

I I

of points in A such that lim x : x and lim y : y. Since A is convex,

I I

z : x ; y + A for each k. Letting k ; -, we get that lim z : z. From

I I I I

Remark I.5.1 we have that z + A.

The next lemma and its corollaries are fundamental results.

L 2.5. L et C be a convex set with nonempty interior. L et x and x be two

points with x + int(C) and x + C. T hen the line segment [x , x ) is contained in

the interior of C.

CONVEX SETS IN RL

38

Figure 2.4.

We ¬rst assume that x + C. The proof of the lemma in this case is based on

Figure 2.4, which illustrates how one uses geometry to motivate analytical

proofs. In the ¬gure we have normalized the dimensions so that #x 9 x # : 1.

Let x be an arbitrary point in (x , x ). Then x : x ; x with 9 0, 9 0,

and ; : 1. We must show that x + int(C). Since the point x is in int(C),

there exists a circle of radius r 9 0 centered at x that is contained entirely

within C. From x draw tangents to the circle. Since #x 9 x# : #x 9 x #,

by similar triangles we would expect the circle with center at x and radius r

to lie in C. This would show that x + int(C).

We now verify analytically that the suggested argument is indeed valid. To

prove the lemma, we must show that any point x + [x , x ) is in int(C). By

hypothesis, x + int(C), so we need only consider x + (x , x ).

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

then x : x ; x for some 9 0, 9 0, ; : 1. We shall show that

B(x, r) : C, and so x + int(C). Let y + B(x, r) and let

y9x

z:x ; .

Then,

#y 9 x# r

#z 9 x # : : : r.