Linear polyhedron ($P=\{u\in {\mathbb{R}}^n:Au\le b\}$)

A linear polyhedron is an intersection of finitely many closed affine half-spaces in finite-dimensional real space. It may be empty, unbounded, or lower-dimensional. This usage differs from a three-dimensional geometric polyhedron. The strict separation of disjoint linear polyhedra follows from linear programming duality.

For a linear polyhedron $P=\{x\in {\mathbb{R}}^n:Ax\le b\}$, a vertex of a linear polyhedron is a feasible point $p$ at which the normals of the active constraints span ${\mathbb{R}}^n$. Equivalently, $n$ linearly independent active constraints uniquely determine $p$. A linear polyhedron may be unbounded or lower-dimensional; the definition applies in those cases as well as to a convex polytope.

Such a point is an extreme point. Indeed, if $p=\lambda u+(1-\lambda )v$ with $u,v\in P$ and $0<\lambda <1$, every active constraint at $p$ must also be an equality at $u$ and $v$. Selecting $n$ independent active rows forces $u=v=p$. Conversely, if the active normals do not span ${\mathbb{R}}^n$, take a nonzero vector $h$ annihilated by all active rows. The finitely many inactive inequalities have positive slack, so both $p+\epsilon h$ and $p-\epsilon h$ remain feasible for sufficiently small $\epsilon >0$. Their midpoint is $p$, so $p$ is not an extreme point. Thus these notions coincide for a linear polyhedron.

A linear polyhedron in ${\mathbb{R}}^n$ is full-dimensional when its affine hull is all of ${\mathbb{R}}^n$. Equivalently, it contains an open Euclidean ball. An open Euclidean ball spans the ambient space. Conversely, a full-dimensional convex set contains $n+1$ affinely independent points; their convex hull is a simplex with nonempty interior, so the set contains an open Euclidean ball.

An inequality constraint which holds with equality at the point under consideration. For $Ax\ge b$, a direction annihilating every active row permits sufficiently small feasible moves of either sign. If the active rows have rank $n$, their common solution is a basic feasible solution; the independent equalities uniquely determine it.

At an extreme point of $\{x:Ax\ge b\}$, the active rows span the ambient dimension: otherwise a nonzero direction orthogonal to all active rows permits small feasible moves of both signs. Select $n$ independent active rows to form an integer matrix $B$. Its nonzero determinant has absolute value at least one. Cramer's rule and the determinant expansion bound each coordinate by $n!U^n$, where $U$ bounds the entries of $A$ and $b$. The vector $b$ may be real; only the denominator matrix needs to be integer.

Nonempty disjoint linear polyhedra $P=\{x:Ax\le b\}$ and $Q=\{y:Cy\le d\}$ admit $h$ with a strictly positive separation gap. A phase-I linear program minimizing common constraint violation has positive attained optimum. Its Lagrangian dual problem gives nonnegative $\lambda ,\mu$ with $A^T\lambda +C^T\mu =0$ and ${\lambda }^{T}b+{\mu }^{T}d<0$. Then $h=A^T\lambda$ satisfies $h^{T}x\le {\lambda }^{T}b<-{\mu }^{T}d\le h^{T}y$. The polyhedral hypothesis matters; arbitrary disjoint closed convex sets need not have a positive separation gap.