Principles of Mathematics in Operations Research

98 7 Convex Sets

Theorem 7.3.2 (Supporting Hyperplane) Let X be a convex set, and let

y be a boundary point of X. Then, there is a hyperplane containing y and

containing X in one of its closed half spaces.

Proof. Let{yk} be sequence of vectors, exterior to the closure of X, converging

to y. Let {a,k} be a sequence of corresponding vectors constructed according to

the previous theorem, normalized so that \dk\ = 1, such that a^yk < infx€x-

Since {a*,} is a boundary sequence, it converges to a. For this vector, we have

aTy = lima^j/fe < ax. O

Definition 7.3.3 A hyperplane containing a convex set X in one of its closed

half spaces and containing a boundary point of X is said to be supporting

hyperplane of X.

7.4 Extreme Points

Remark 7.4.1 We have already defined extreme points. For example, the

extreme points of a square are its corners in M.^2 whereas the extreme points

of a circular disk are all (infinitely many!) the points on the boundary circle.

Note that, a linear variety consisting of more than one point has no extreme

points.

Lemma 7.4.2 Let X be a convex set, H be a supporting hyperplane of X and

T = X D H. Every extreme point ofT is an extreme point of X.

Proof. Suppose xo 6 T is not an extreme point of X. Then,

xo = ax\ + (1 — a)x2 for some X\,X2 6 X, 0 < a < 1.

Let H — {x : aTx = c} with X contained in its closed positive half space.

Then, aTX\ > c, aTx^ > c. However, since XQ £ H,

c = aTxo = aaTxi + (1 — a)aTX2-

Thus, xi, X2 E H. Hence, x\, X2 &T and xo is not an extreme point of T. •

Theorem 7.4.3 A closed bounded convex set in Rn is equal to the closed
convex hull of its extreme points.

Proof. This proof is by induction on n.
For n = 1, the statement is true for a line segment:

[a, b] = {x £ R : x = a + (1 - a)b,0 < a < 1}.

Suppose that the theorem is true for (n — 1). Let X be a closed bounded
convex set in Kn, and let K be the convex hull of the extreme points of X.