<<

. 12
( 59 .)



>>


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

<<

. 12
( 59 .)



>>