for all y in Y. Hence (ii) holds for any positive number strictly less than #a#.

We now suppose that there exists an 9 0 such that 1a, x2 9 ; for all

x in X. Let z be an arbitrary element of B(0, 1). Since #z# : 1, from the

Cauchy”Schwarz inequality we get that 1a, z2 : #a#, and consequently

1a, x 9 z2 : 1a, x2 9 1a, z2 9 ; 9 #a#.

Similarly, for all y in Y and z + B(0, 1),

1a, y ; z2 : 9 ; #a#.

Hence if we take : /#a#, we have that 1a, u2 9 for all u in X 9 B(0, 1) :

X ; B(0, 1) and that 1a, v2 : for all v in Y ; B(0, 1). This proves (i).

Remark 3.1. From the preceding lemma it should be clear that a necessary and

suf¬cient condition for two sets X and Y to be strongly separated is that there

exists a vector a such that

inf+1a, x2 : x + X, 9 sup+1a, y2 : y + Y ,.

Our principal objective in this section is to prove Theorem 3.4. Although

this theorem is not the best possible separation theorem in RL, it is the one that

is valid in in¬nite-dimensional spaces and it does cover the situations that

occur in optimization problems. The best possible separation theorem in RL

will be discussed in Section 7. Our proof of Theorem 3.4 will not be the most

economical one but will be one that is suggested by rather obvious geometric

considerations.

The principal step in the proof is to show that if C is a convex set and y is

a point not in C, then y and C can be properly separated. If C is not convex,

then it may not be possible to separate y and C, as can be seen by taking, in

R, y : 0 and C to be the circumference of any circle with center at the origin.

SEPARATION THEOREMS 49

Figure 2.6.

We ¬rst show that if C is closed and convex, then strong separation is

possible.

T 3.1. L et C be a closed convex set and y a vector such that y , C. T hen

?

there exists a hyperplane Ha that strongly separates y and C.

To motivate the proof, we argue heuristically from Figure 2.6, in which C is

assumed to have a tangent at each boundary point.

Draw a line from y to x , the point of C that is closest to y. The vector

*

y 9 x will be perpendicular to C in the sense that y 9 x is the normal to the

* *

tangent line at x . The tangent line, whose equation is 1y 9 x , x 9 x 2 : 0,

* * *

properly separates y and C. The point x is characterized by the fact that

*

1y 9 x , x 9 x 2 - 0 for all x + C. To obtain strong separation, we merely

* *

move the line parallel to itself so as to pass through a point x + (x , y). We

*

now justify these steps in a series of lemmas, some of which are of interest in

their own right.

If X is a set and y is a vector, then we de¬ne the distance from y to X,

denoted by d(y, X), to be

d(y, X) : inf+#y 9 x# : x + X,.

A point x in X is said to attain the distance from y to X, or to be closest to

*

y, if d(y, X) : #y 9 x #.

*

L 3.2. L et C be a convex subset of RL and let y , C. If there exists a point

in C that is closest to y, then it is unique.

CONVEX SETS IN RL

50

Proof. Suppose that there were two points x and x of C that were closest

to y. Then since C is convex, (x ; x )/2 belongs to C, and so

d(y, C) - #(x ; x )/2 9 y# : #(x 9 y) ; (x 9 y)#

- (#x 9 y# ; #x 9 y#) : d(y, C).

Hence equality holds in the application of the triangle inequality, and so by (5)

of Section 2 in Chapter I, we have that, for some . 0, (x 9 y) : (x 9 y).

Suppose 9 0. Since #x 9 y# : #x 9 y# : d(y, C), we get that : 1, and so

x : x . If : 0, we get x : y, contradicting the assumption that y , C.

L 3.3. L et C be a closed subset of RL and let y , C. T hen there exists a

point x in C that is closest to y.

*

Proof. Let x + C and let r 9 #x 9 y#. Then C : B(y, r) 5 C is nonempty,

closed, and bounded and hence is compact. The function x ; #x 9 y# is

continuous on C and so attains its minimum at some point x in C . Thus,

*

for all x + C , #x 9 y# . #x 9 y#. For x + C and x , C we have

*

#x 9 y# 9 r 9 #x 9 y# . #x 9 y#,

*

since x + B(y, r).

Lemmas 3.2 and 3.3 show that if C is a closed convex set and y , C, then there

is a unique closest point in C to y.

The next lemma characterizes closest points.

L 3.4. L et C be a convex set and let y , C. T hen x + C is a closest point

*

in C to y if and only if

1y 9 x , x 9 x 2 - 0 for all x + C. (1)

* *

Note that if C is not convex, then the above characterization of closest point

need not hold. To see this, let y be the origin in R and let C be the

circumference of the unit circle. Let x be a ¬xed point in C. Then it is not true

*

that 10 9 x , x 9 x 2 - 0 for all x in C.

* *

Proof. Let x be a closest point to y and let x be any point in C. Since C

*

is convex, the line segment [x , x] : +z(t) : z(t) : x ; t(x 9 x ), 0 - t - 1,

* * *

belongs to C. Let

(t) : #z(t) 9 y# : 1x ; t(x 9 x ) 9 y, x ; t(x 9 x ) 9 y2. (2)

* * * *

For 0 - t - 1, (t) is the square of the distance between the point z(t) + [x , x]

*

and y. If t : 0, then z : x . Since is continuously differentiable on (0, 1] and

*

SEPARATION THEOREMS 51

x is a point in C closest to y, we have (0;) . 0. Calculating (t) from (2)

*

gives

(t) : 2[91y 9 x , x 9 x 2 ; t#x 9 x #]. (3)

* * *

If we now let t ; 0; and use (0;) . 0, we get (1).

We now suppose that (1) holds. Let x be any other point in C. It follows

from (3) that (t) 9 0 for 0 : t - 1. This is strictly increasing function on

[0, 1], and so for any point z(t) in (x , x]. We have #z(t) 9 y# 9 #x 9 y#. In

* *

particular, this is true for z : x, and so x is a closest point to y.

*

We can now complete the proof of Theorem 3.1. Let x be the closest point

*

in C to y and let a : y9x . Then for all x + C, 1a, x9x 2 - 0, and so 1a, x2 -

* *

1a, x 2, with equality occurring when x:x . Therefore sup+1a, x2 : x + C, :

* *

1a, x 2. On the other hand, 1a, y 9 x 2 : #a# 9 0, so

* *

1a, y2 : 1a, x 2 ; #a# 9 sup+1a, x2 : x + C,.

*

The conclusion of the theorem now follows from Remark 3.1 with X : +y, and

Y : C.

We now take up the separation of a point y and an arbitrary convex set;

that is, we shall no longer assume that C is closed. We shall obtain separation,

but shall not be able to guarantee proper separation unless we assume that C

has nonempty interior.

T 3.2. L et C be a convex set and let y , C. T hen there exists a hyperplane

H? such that for all x in C

a

1a, x2 - and 1a, y2 : . (i)

If int(C) " `, then for all x in int(C)

1a, x2 : . (ii)

Proof. We ¬rst suppose that y : 0. Then to establish (i), we must ¬nd an

a " 0 such that

1a, x2 - 0 for all x in C. (4)

For each x in C de¬ne

Nx : +z : #z# : 1, 1z, x2 - 0,.

The set Nx is nonempty since it contains the element 9x/#x#.

CONVEX SETS IN RL

52

To establish (4), it suf¬ces to show that

7 Nx " `.

x+C

Each Nx is closed and is contained in S(0, 1) : +u : #u# : 1,. Thus we may

write the last relation as

7 Nx : 7 Nx 5 S(0, 1) " `. (5)

x+C x+C

Since S(0, 1) is compact, it has the ¬nite-intersection property. Thus, if

the intersection in (5) were empty, there would exist a ¬nite subcollection

Nx , . . . , Nx that is empty. Therefore, we may establish (5) by showing that

P

every ¬nite subcollection Nx , . . . , Nx has nonempty intersection.

I

Now consider any ¬nite collection of sets Nx , . . . , Nx and the corre-

I

sponding k points x , . . . , x in C. Let co[x , . . . , x ] denote the convex hull

I I

of x , . . . , x . Then co[x , . . . , x ] is compact and convex. Since C is convex,

I I

co[x , . . . , x ] 3 C. Thus, since 0 , C, we have 0 , co[x , . . . , x ]. Hence, by

I I

Theorem 3.1, there exists a vector w " 0 such that

0 : 1w, 02 9 1w, x2, x + co[x , . . . , x ]. (6)

I

We may divide through by #w# " 0 in (6) and so assume that #w# : 1. Thus,

(6) says that

I

w + 7 Nx 5 S(0, 1),

G

G

and we have shown that the intersection of any ¬nite subcollection Nx , . . . , Nx

I

of the closed sets +Nx,x + C has nonempty intersection with S(0, 1). Hence (5)

holds.

We now remove the restriction that y : 0. We have

y , C if and only if 0 , C 9 y : +x : x : x 9 y, x + C,.

Therefore, there exists an a " 0 such that 1a, x2 - 0 for all x in C 9 y. Hence

for all x in C,

1a, x 9 y2 - 0,

and so

1a, x2 - 1a, y2 for all x in C.

SEPARATION THEOREMS 53

If we now let : 1a, y2, we get the ¬rst conclusion of the theorem. The second

follows from Exercise 2.16.

Our ¬rst separation result for convex sets will follow from Theorem 3.2.

T 3.3. L et X and Y be two disjoint convex sets. T hen there exists a

hyperplane H? that separates them.

a

Note that the theorem does not assert that proper separation can be

achieved. Theorem 7.2 in the sequel will allow us to conclude that the

separation is proper. Our proof of Theorem 3.3 does not yield this fact.

To prove the theorem, we ¬rst note that