Polyhedra

LP and QP > Polyhedra | Standard forms | Polyhedral Functions | Min-Cardinality | Applications

Half-spaces
Polyhedra

Half-spaces

Definition

A half-space is a set defined by a single affine inequality. Precisely, a half-space in $mathbf{R}^n$ is a set of the form

$mathbf{H} = left{ x ~:~ a^Tx le b right},$

where $a in mathbf{R}^n$ , b in mathbf{R} . A half-space is a convex set, the boundary of which is a hyperplane.

A half-space separates the whole space in two halves. The complement of the half-space is the open half-space ${ x ::: a^Tx > b}$ .

Geometry

A half-space separates the whole space in two halves. The complement of the half-space is the open half-space ${ x ::: a^Tx > b}$ .

When b = 0 , the half-space

$mathbf{H} = left{ x ~:~ a^Tx le 0 right},$

is the set of points which form an obtuse angle (between 90^o and 270^o ) with the vector . The boundary of this set is a subspace, the hyperplane of vectors orthogonal to .

When bne 0 , the half-space mathbf{H} can be written as

$mathbf{H} = left{ x ~:~ a^T(x-x_0) le 0 right},$

where x_0 is chosen such that a^Tx_0 = b . For example, x_0 = b/|a|_2^2 is such a point on the boundary of the half-space (this particular choice corresponds to the minimum-norm solution to the equation a^Tx=b ). Thus, the half-space above corresponds to the set of points such that x-x_0 (shown in dotted) forms an obtuse angle with the vector . The vector points outwards from the boundary.

Example: A half-space in $mathbf{R}^2$ .

Link with linear functions

Hyperplanes correspond to level sets of linear functions.

Half-spaces represent sub-level sets of linear functions: the half-space above describes the set of points such that the linear function x rightarrow a^Tx achieves the value , or less. A quick way to check which half of the space the half-space describes is to look at where the origin is: if b ge 0 , then x=0 is in the half-space.

Polyhedra

Definition

A polyhedra is a set described finitely many affine inequalities. Precisely, a polyhedron is a set of the form

$mathbf{P} = left{ x ~:~ a_i^Tx le b_i, ;; i=1,ldots,m right},$

where $a_i in mathbf{R}^n$ , $b_i in mathbf{R}$ , i=1,ldots,m .

A polyhedron can be expressed as the intersection of (finitely many) half-spaces:

$mathbf{P} = bigcap_{i=}^m mathbf{H}_i, ;; mathbf{H}_i := left{ x ~:~ a_i^Tx le b_i right}, , ;; i=1,ldots,m .$

Geometry

A polyhedron is a convex set, with boundary made up of ‘‘flat’’ boundaries (the technical term is facet). Each facet corresponds to one of the hyperplanes defined by a_i^Tx = b_i . The vectors a_i are orthogonals to the facets, and point outside the polyhedra.

Note that not every set with flat boundaries can be represented as a polyhedron: the set has to be convex.

Matrix notation

It is often convenient to describe a half-space in matrix notation:

where $A in mathbf{R}^{m times n}$ and $b in mathbf{R}^m$ are defined as follows:

$A = left( begin{array}{c} a_1^T vdots a_m^T end{array}right), ;; b = left( begin{array}{c} b_1 vdots b_m end{array}right).$

Here, we adopted the component-wise inequality convention: the notation Ax le b means that for every i=1,ldots,m , the corresponding components of and are ordered: (Ax)_i = a_i^Tx le b_i .

Example: A polyhedron in $mathbf{R}^2$ .

Equality constraints are allowed

Sets defined by affine inequalities and equalities are also polyhedra.

Indeed, consider the set

mathbf{P} = left{ x ~:~ Ax le b, ;; Cx = d right},

where $A in mathbf{R}^{m times n}$ , $b in mathbf{R}^m$ define the (component-wise) inequalities, and $C in mathbf{R}^{p times n}$ , $d in mathbf{R}^p$ define the equalities.

The set above can be expressed as an ‘‘inequalities-only’’ polyhedron:

mathbf{P} = left{ x ~:~ Ax le b, ;; Cx le d, ;; -Cx le -d right},

which can be put in the standard form for polyhedra, with augmented matrices and right-hand side vector.

Example: The probability simplex.