Principles of Mathematics in Operations Research

7.2 Hyperplanes and Polytopes 95

Fig. 7.3. Cones

7.2 Hyperplanes and Polytopes

The most important type of convex set (aside from single points) is the hy-

perplane.

Remark 7.2.1 Hyperplanes dominate the entire theory of optimization; ap-
pearing in Lagrange multipliers, duality theory, gradient calculations, etc. The
most natural definition for a hyperplane is the generalization of a plane in R^3.

Definition 7.2.2 A set V in Rn is said to be linear variety, if, given any
x\,X2 £ V, we have ax\ + (1 — a)x2 £ V,Va £ R.
Remark 7.2.3 The only difference between a linear variety and a convex set
is that a linear variety is the entire line passing through any two points, rather
than a simple line segment.

Definition 7.2.4 A hyperplane in R™ is an (n—1)-dimensional linear variety.

It can be regarded as the largest linear variety in a space other than the entire

space itself.

Proposition 7.2.5 Let a £ R",a ^ 9 and b G R. The set

ff = {i£l": arx = b}

is a hyperplane in R".

Proof. Let x\ £ H. Translate H by — x\, we then obtain the set

M = H - Xi ={y€Rn:3xeH3y = x~ xx},

which is a linear subspace of Rn. M — {y G R™ : a? y = 0} is also the set of
all orthogonal vectors to a G Rn, which is clearly (n — 1) dimensional. D

Proposition 7.2.6 Let H be an hyperplane in R". Then,

3a G R" 3 H = {x G R : aTx = b}.

NON-COtWEX