Half-Spaces

LP and QP > Half-Spaces | Polyhedra | Standard Forms | Polyhedral Functions | Applications

Definition
Geometry
Link with linear functions

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}$ .

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 corresponding half-space 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 describe, is to look at where the origin is: if b ge 0 , then x=0 is in the half-space.