Principles of Mathematics in Operations Research

96 7 Convex Sets

Proof. Let xi 6 H, and translate by -x\ obtaining M = H — x\. Since H is

a hyperplane, M is an (n — 1)-dimensional space. Let a be any orthogonal to

M, i.e. a 6 ML. Thus, M = {y e M" : aTt/ = 0}. Let 6 = aTxi we see that

if x 2 E H, X2 — xi G M and therefore aTX2 - aTx\ = 0 => aTX2 = &• Hence,

H C {a; € K : aTx = 6}. Since i? is, by definition, of (n — 1) dimension, and

{xeR: aTx = b} is of dimension (n — 1) by the above proposition, these two

sets must be equal (see Figure 7.4). •

a

z-^ 7

^ 7 ' H

e

Fig. 7.4. Proof of Proposition 7.2.6

Definition 7.2.7 Let oel", fo e M. Corresponding to the hyperplane H =

{x : aTx = b}, there are positive and negative closed half spaces:

H+ = {x : aTx > b}, H- = {x : aTx < b}

and

H+ = {x : aTx > b}, #_ = {x : aTa; < &}.

ffa// spaces are convex sets and H+ U H- = W^1.

Definition 7.2.8 A set which can be expressed as the intersection of a finite

number of closed half spaces is said to be a convex polyhedron.

Convex polyhedra are the sets obtained as the family of solutions to a set

of linear inequalities of the form

a\x < b\

a\x < b<2

a-mX < bm
Since each individual entry defines a half space and the solution family is
the intersection of these half spaces.

Definition 7.2.9 A nonempty bounded polyhedron is called a polytope.