Principles of Mathematics in Operations Research

7.4 Problems 99

We will show that X = K.

Assume that 3y e X 3 y $ K. Then, by Theorem 7.3.1, there is a hyperplane

separating y and K;

3a ^ 0 3 aTy < inf aTx

xEK

Let XQ = m{X£x(aTx)- xo is finite and 3xo £ X 3 aTxo = bo (because by

Weierstrass' Theorem: The continuous function aTx achieve its minimum over

any closed bounded set).

Hence, the hyperplane H = {x : aTx = bo} is a supporting hyperplane to X.

Since b 0 < aTy < mixeK aTx, H is disjoint from K. Let T = H D X. Then,

T is a bounded closed convex set of H, which can be regarded as a space

in Rn_1. T ^ 0, since XQ € T. Hence, by induction hypothesis, T contains

extreme points; and by the previous Lemma, these are the extreme points

of X. Thus, we have found extreme points of X not in K, Contradiction.

Therefore, X C K, and hence X = K (since K C X, i.e. K is closed and

bounded). •

Remark 7.4.4 Let us investigate the implications of this theorem for convex

polytopes. A convex polytope is a bounded polyhedron. Being the intersection of

closed halfspaces, a convex polytope is closed. Thus, any convex polyhedron is

the closed convex hull of its extreme points. It can be shown that any polytope

has at most a finite number of extreme points, and hence a convex polytope is

equal to the convex hull of a finite number of points. The converse can also be

established, yielding the following two equivalent characterizations.

Theorem 7.4.5 A convex polytope can be described either as a bounded in-
tersection of a finite number of closed half spaces, or as the convex hull of a
finite number of points.

Problems

7.1. Characterize (draw, give an example, list extreme points and halfspaces)
the following polytopes:
a) zero dimensional polytopes.
b) one dimensional polytopes.
c) two dimensional polytopes.

7.2. d-simplex
d-simplex is the convex hull of any d+1 independent points in R™ (n > d).
Standard d — simplex with d+1 vertices in Rd+1 is

d+l

Ad = {x£ Rd+1 : ]T Xi = 1; x{ > 0, i = 1,..., d + 1}.

Characterize A2 in R^3.