Principles of Mathematics in Operations Research

7.3 Separating and Supporting Hyperplanes

7.3 Separating and Supporting Hyperplanes

Theorem 7.3.1 (Separating Hyperplane) Let X be a convex set and y

be a point exterior to the closure of X. Then, there exists a vector a £ M.n 3

aTy < inixex aTx. (Geometrically, a given point y outside X, a separating

hyperplane can be passed through the point y that does not touch X. Refer to

Figure 7.5)

Fig. 7.5. Separating Hyperplane

Proof. Let 6 = inf^gx \x — y\ > 0 Then, there is an XQ on the boundary of X

such that |xo — y\ — S. Let z £ X. Then,

Va, 0 < a < 1, XQ + a(z — XQ)

is the line segment between xo and z. Thus, by definition of xo,

\x 0 + a(z - x 0 ) - y\^2 > \x 0 - y\^2

«=> (x 0 -y)T(x 0 -y)+2a(x 0 -y)T(z-xo)+a^2 (z-x 0 )T(z-xo) > (x 0 -y)T(x 0 -y)

<=> 2a(x 0 - y)T(z - x 0 ) + a^2 \z - x 0 \^2 > 0

Let a —$• 0 +, then a^2 tends to 0 more rapidly than 2a. Thus,

(x 0 - y)T(z - x 0 ) > 0 <s> (x 0 - y)Tz - (x 0 - y)Tx 0 > 0

& (x 0 -y)Tz > (x 0 -y)Tx 0 = (x 0 -y)Ty + (x 0 + y)T{x 0 -y) = (x 0 -y)Ty + 5^2

& (x 0 - y)Ty < (x 0 - y)Tx 0 < (x 0 - y)Tz, Vz£X (Since 5 > 0).

Let a = (XQ — y), then aTy < aTxo = infz6x <iTz. U