Polyhydra and Polytopes

When studying linear program, it necessary that we understand the structure of the feasible region. We investigate here some critical ideas of characterizing the feasible region.

1. Polyhedron: $P$ is a polyhedron in $R^n$ if it is the intersection of a set of linear constraints: $P = \{ x: Ax \le b \}$ for some $A \in R^{m \times n}, b \in R^n$. A polyhedron is a convex set.
2. Polytope: $P$ is a polytope if it consists of points that are convex combination of finite number of points $v_1, v_2, ..., v_k$, i.e., $P = \{ x: x = \sum_{i = 1}^k \mu_i v_i , \ s.t., \ \sum_{i =1}^k \mu_i = 1 \wedge \mu_i \in [0, 1] \quad \forall i \in [k] \}$.

Of interest are the vertices, or extreme points or basic feasible solution of a polyhedron $P$:

1. Vertex: $v \in P$ is called a vertex if $\exists c \in R^n$, s.t., $c^T v > c^T x$ $\forall x \neq v \wedge x\in R$.
2. Extreme Point: $v \in R$ is an extreme point of $P$ if $\nexists x, y \neq v, x, y \in P$, s.t., $v = \mu_1 x + \mu_2 y$, $\mu_1, \mu_2 \in [0, 1]$ and $\mu_1 + \mu_2 = 1$.
3. Basic Feasible Solution: $v \in P$ is a basic feasible solution of $P = \{ x: Ax \le b \}$, if the number of tight constraints $A v \le b$ equals to $n$. In particular, denote $A_{i, :}$ the $i$-th row of matrix $A$ and $b_i$ the $i$-th element of $b$. The constraint $A_{i, :} v \le b_i$ is called tight if equality holds. For convenience of discussion, denote $A_{=} x = b_{=}$ the set of tight constraints and $A_{<} x < b_{<}$ the set of non-tight constraints.

It turns out that the three definitions are equivalent. Here is the proof.

Proof:

$1 \rightarrow 2:$ $c^T(\mu_1 x + \mu_2 y) = \mu_1 c^T x + \mu_2 c^T y < \mu_1 c^T v + \mu_2 c^T v = c^T v$, it concludes that $\mu_1 x + \mu_2 y \neq v$.

$2 \rightarrow 3:$ suppose that $rank(A_{=}) \neq n$. There $\exists y \in R^n, y \neq 0$, and $A_{=} y = 0$. For inequality constraints, we can find small enough $\epsilon$, such that $A_{< } (x \pm \epsilon y) < b$. Hence $x \pm \epsilon y \in P$. But $\frac{1}{2} (x + \epsilon y) + \frac{1}{2} (x - \epsilon y) = x$, a contradiction.

$3 \rightarrow 1:$ just define $c^T = \sum_{i = 1}^m A_{i, :}$. If $x \in P$, then $\sum_{i = 1}^m A_{i, :} x \le \sum_{i = 1}^m b_i = \sum_{i = 1}^m A_{i, :} v$. As $A_{=}$ has rank $n$, when equality holds, it implies $x = y$.

The relationship between polyhedron and polytope is stated as follows:

Theorem: if a polyhedron $P$ is bounded, that is, $\exists M > 0$, $\forall x \in P$, we have $x^T x < M$, then $P$ is a polytope.

Proof: It suffice to show that every $x \in P$ is a convex combination of vertices of $P$. The proof is by induction on the rank of $A_{=}$, given $x \in A$.

1. If $rank(A_{=}) = n$, then by definition $x$ is a vertex.
2. Suppose the claim holds for all ranks $\ge k + 1$ for some $k < n$. We show it carries to $x \in P$ with $rank(A_{=}) = k$.
   • As $k < n$, $\exists y \in R^n, y \neq 0$, such that $A_{=} y = 0$.
   • We extend $x$ from the directions of $y$ and $-y$ as much as possible. We find the largest $\lambda_+ \in R, \lambda_+ > 0$, such that $x + \lambda_+ y \in P$. Since $A_{=} (x + \lambda_+ y) = b_{=}$, these constraints will never be violated. Hence some constraints $A_{< } x < b_{<}$ becomes tight for $A_{<} (x + \lambda_+ y)$. Which implies that the rank of $x + \lambda_+ y$ is at least $k + 1$ and thus can be expressed a convex combination of vertices. Similarly, we can find some $x - \lambda_- y$ that is a convex combination of vertices.
   • $x$ can now be express a convex combination of $x + \lambda_+ y$ and $x - \lambda_- y$, therefore a convex combination of vertices.

The reverse is also true:

Theorem: Let $P$ be a polytope, then $P$ is a bounded polyhedron.

To prove this, we need an intermediate definition--polar set. It means something on the opposite direction.

Definition: Given a set $P$, its polar set is defined as $\bar P = \{ y \in R^n, y^T x \le 1, \forall x \in P\}$.

Lemma: If $P$ is closed, convex and $0$ is the interior point of $P$, then $\overline{\bar P} = P$, that is the polar set of the polar set of $P$ is $P$ itself.

Proof of the Lemma:

1. $P \subset \overline{\bar P}$. If $x \in P$, then by definition of $\bar P$, $\forall y \in \overline{\bar P}$, we have $y^T x \le 1$, then $x \in P^{oo}$.
2. $(R^n - P) \cap \overline{\bar P} = \emptyset$, i.e., $\forall x \notin P$, we have $v \notin \overline{\bar P}$. Since $P$ is convex and closed, $\exists y \in R^n$, such that $y^T v > k$ and $y^T x < k$ for all $x \in P$. The fact that $0 \in P$ implies $k > 0$. Replace $y$ with $\bar y = y / k$, we have $\bar y^T x < 1$ for all $x \in P$. Hence $\bar y \in \bar P$. But now $\bar y^T v > 1$. By definition, $v$ does not belong to the polar set of $\bar P$.

Proof of the Theorem: We assume that $P$ contains the point $0$. Otherwise, we perform a translation $R^n \rightarrow R^n: f(x) = x + t, \forall x \in R^n$, such that $0 \in f(P)$. If we can show $f(P)$ is a polyhedron, then $f(P) = \{f(x) : A f(x) \le b \}$, then we have $P = \{ x : Ax \le b - At \}$.

Back to our proof. As $P$ is a polytope, then it can be written as $P = \{ x: x = \sum_{i = 1}^k \mu_i v_i , \ s.t., \ \sum_{i =1}^k \mu_i = 1 \wedge \mu_i \in [0, 1] \quad \forall i \in [k] \}$. A point $y$ belongs to the polar set of $P$ if and only if $y^T v_i \le 1, \forall i \in [k]$. Therefore, $\bar P = \{y : y^T v_i \le 1, \forall i \in [k] \}$, which is a polyhedron.

Next, we show that $\bar P$ is bounded. This results from the assumption that $0$ is an interior point of $P$. Therefore, $\exists \epsilon > 0$, such that $x \in P, \forall x \in R^n, |x|_2 < \epsilon$. For any $y \in \bar P$, with proper scaling, we have $\frac{\epsilon}{|y|_2} y \in P$. Which further implies that $y^T \frac{\epsilon}{|y|} y = \epsilon |y|_2 \le 1$, and $|y|_2 \le \frac{1}{\epsilon}$.

Now, $\bar P$ is a bounded polyhedron, hence a polytope. By previous lemma, $P = \overline{\bar P}$, hence a polyhedron.

Reference

1. David P. Williamson, ORIE 6300, Lecture 03, Polyhedra and polytopes.