Polytopes

Bounded polyhedron

A set \(S \subseteq \mathbb{R}^n\) is said to be bounded if there exists \(M \gt 0\) such that \(\|\mathbf{x} \| \leq M\) for all \(\mathbf{x} \in S\).

A bounded polyhedron is called a polytope.

Example. The polyhedron \(P = \left \{\begin{bmatrix} x_1 \\ x_2\end{bmatrix} : -x_1-x_2\geq -1, x_1,x_2 \geq 0\right\}\) is a polytope in \(\mathbb{R}^2\).

One can see this in one of two ways. The first way is to sketch \(P\) and make the observation that it is indeed bounded. Unfortunately, sketching a polyhedron is not always possible, especially when the polyhedron is in dimensions higher than 3.

The second way is to show that if \(\mathbf{x} \in P\), then \(\lvert x_i\rvert \leq \gamma\) for \(i = 1,\ldots,n\) for some positive real number \(\gamma\). Then \(\|\mathbf{x}\| = \sqrt{\sum_{i=1}^n x_i^2 } \leq \sqrt{n\gamma^2} = \sqrt{n} \gamma\), implying that \(P\) is bounded. Here, we already have the inequalities \(x_1,x_2 \geq 0\). Hence, \(x_1\) and \(x_2\) are bounded below by 0. Now, adding the inequalities \(-x_1-x_2 \geq -1\) and \(x_2 \geq 0\) gives \(-x_2\geq -1\), which is equivalent to \(x_2 \leq 1\). Finally, adding the inequalities \(-x_1-x_2 \geq -1\) and \(x_1 \geq 0\) gives \(-x_1\geq -1\), which is equivalent to \(x_1 \leq 1\). Thus, \(\|\mathbf{x}\| \leq \sqrt{2}\) for all \(\mathbf{x} \in P\) and so \(P\) is a polytope.

As a bounded set cannot contain any line, by Theorem 8.6, every nonempty polytope is pointed. In fact, more can be said.

Theorem 9.3. If \(P\) is a nonempty polytope in \(\mathbb{R}^n\), then \(P\) is the convex hull of its extreme points.

Our proof will use the following lemma.

Lemma 9.4. Let \(\mathbf{v},\mathbf{u}^1,\ldots, \mathbf{u}^k \in \mathbb{R}^n\) where \(n\) is a positive integer. If \(\mathbf{v}\notin \operatorname{conv}(\{ \mathbf{u}^1,\ldots, \mathbf{u}^k \}),\) then there exist \(\mathbf{a} \in \mathbb{R}^n\) and \(\beta \in \mathbb{R}\) such that \(\mathbf{a}^\mathsf{T}\mathbf{v} \lt \beta\) and \(\mathbf{a}^\mathsf{T}\mathbf{u}^i \geq \beta\) for \(i = 1,\ldots, k\). (This lemma is a special case of the Separating Hyperplane Theorem.)

Proof. Because \(\mathbf{v}\notin \operatorname{conv}(\{ \mathbf{u}^1,\ldots, \mathbf{u}^k \})\), the following system has no solution: \begin{align*} \begin{bmatrix} 1 & \cdots & 1 \\ \mathbf{u}^1 & \cdots & \mathbf{u}^k \end{bmatrix} \begin{bmatrix} \lambda_1 \\ \vdots \\ \lambda_k \end{bmatrix} & = \begin{bmatrix} 1 \\ \mathbf{v} \end{bmatrix} \\ \lambda_1,\ldots, \lambda_k & \geq 0. \end{align*} By Corollary 2.2, there exist \(y_0,y_1,\ldots,y_n\) satisfying \(y_0 + \begin{bmatrix} y_1 & \cdots & y_n\end{bmatrix}\mathbf{u}^i \geq 0\), \(i = 1,\ldots,k\) and \(y_0 + \begin{bmatrix} y_1 & \cdots & y_n\end{bmatrix}\mathbf{v} \lt 0\). Setting \(\mathbf{a} = \begin{bmatrix} y_1 \\ \vdots \\ y_n\end{bmatrix}\) and \(\beta = -y_0\) gives the desired result.

Proof of Theorem 9.3. Let \(Q\) denote the convex hull of the extreme points of \(P\). Note that \(Q\) is nonempty because \(P\) has at least one extreme point. As \(P\) is convex, \(P \supseteq Q\).

Suppose that there exists \(\mathbf{v} \in P \backslash Q\). By Corollary 8.5, the number of extreme points of \(P\) is finite. Hence, by Lemma 9.4, there exist \(\mathbf{a} \in \mathbb{R}^n\) and \(\beta \in \mathbb{R}\) such that \(\mathbf{a}^\mathsf{T}\mathbf{u} \geq \beta\) for every extreme point \(\mathbf{u}\) of \(P\) but \(\mathbf{a}^\mathsf{T}\mathbf{v} \lt \beta\). Let \((LP)\) denote the linear programming problem \(\min \{ \mathbf{a}^\mathsf{T} \mathbf{x} : \mathbf{x} \in P\}\). Since \(P\) is a nonempty polytope, \((LP)\) is not infeasible and is not unbounded. By the Fundamental Theorem of Linear Programming, it has an optimal solution. By Theorem 8.7, it has an optimal solution that is an extreme point of \(P\). But \(\mathbf{a}^\mathsf{T}\mathbf{u} \geq \beta\) for every extreme point of \(P\). Thus, the optimal value must be at least \(\beta\). However, \(\mathbf{v}\) is a feasible solution with objective function value \(\mathbf{a}^\mathsf{T}\mathbf{v} \lt \beta\), a contradiction.

Worked examples

Is \(P = \left\{ \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} : \begin{array}{c} x_1 - x_2 + 2x_3 \geq 2\\ -x_1+2x_2-3x_3 \geq 0\\ x_2+x_3 \geq 1\\ x_3 \geq 0 \end{array}\right\}\) a polytope? Justify your answer.

Let \(P = \left \{ \begin{bmatrix} x_1 \\ x_2 \\ x_3 \end{bmatrix} : \begin{array}{c} -x_1 - 2x_2 - 3x_3 \geq -6 \\ x_1, x_2, x_3 \geq 0 \end{array} \right \}\). Write \(P\) as the convex hull of its extreme points.

First, it is easy to see that \(P\) is bounded. Hence, \(P\) is a polytope.

We could look at a sketch of \(P\) to determine all its extreme points. But we need a method that works with polytopes that cannot be sketched.

A previous exercise states that if \(P = \left \{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b} \right \}\) and \(\mathbf{x}^* \in P\), then, where \(\mathbf{A}^= \mathbf{x} \geq \mathbf{b}^=\) is the subsystem of \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) consisting of the inequalities satisfied with equality by \(\mathbf{x}^*\), \(\mathbf{x}^*\) is an extreme point of \(P\) if and only if \(\operatorname{rank}(\mathbf{A}^=) = n\).

This result gives us a way to enumerate all extreme points of \(P\): we go through all possible subsystems of \(P\) containing \(n\) inequalities from \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) and see if the coefficient matrix has rank \(n\). If it does, solve the system of equations by setting the inequalities to equalities and see if the solution is an element of \(P\). If it is, then we have found an extreme point of \(P\). Otherwise, we move on.

For our \(P\), we have only four subsystems to consider.

Setting \(x_1,x_2,x_3\geq 0\) to equalities gives the unique solution \(\begin{bmatrix} 0\\0\\0\end{bmatrix}\) which is in \(P\). Hence, \(\begin{bmatrix} 0\\0\\0\end{bmatrix}\) is an extreme point of \(P\).

Setting \(-x_1-2x_2-3x_3\geq -6, x_1,x_2\geq 0\) to equalities gives the unique solution \(\begin{bmatrix} 0\\0\\2\end{bmatrix}\) which is in \(P\). Hence, \(\begin{bmatrix} 0\\0\\2\end{bmatrix}\) is an extreme point of \(P\).

Setting \(-x_1-2x_2-3x_3\geq -6, x_1,x_3\geq 0\) to equalities gives the unique solution \(\begin{bmatrix} 0\\3\\0\end{bmatrix}\) which is in \(P\). Hence, \(\begin{bmatrix} 0\\3\\0\end{bmatrix}\) is an extreme point of \(P\).

Setting \(-x_1-2x_2-3x_3\geq -6, x_2,x_3\geq 0\) to equalities gives the unique solution \(\begin{bmatrix} 6\\0\\0\end{bmatrix}\) which is in \(P\). Hence, \(\begin{bmatrix} 6\\0\\0\end{bmatrix}\) is an extreme point of \(P\).

Thus \(P = \operatorname{conv}\left (\left\{ \begin{bmatrix} 0\\0\\0\end{bmatrix}, \begin{bmatrix} 0\\0\\2\end{bmatrix}, \begin{bmatrix} 0\\3\\0\end{bmatrix}, \begin{bmatrix} 6\\0\\0\end{bmatrix}\right\}\right)\).

Let \(P\) be the convex hull of \( \left\{ \begin{bmatrix} 0 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} -1 \\ -2 \\ 0 \end{bmatrix}, \begin{bmatrix} 1 \\ 1 \\ -2 \end{bmatrix} \right \}\). Let \(\mathbf{u} = \begin{bmatrix} 1 \\ 1 \\ 1\end{bmatrix}\). Show that \(\mathbf{u} \notin P\) by giving \(\mathbf{a} \in \mathbb{R}^3\) and \(\beta \in \mathbb{R}\) such that \(\mathbf{a}^\mathsf{T}\mathbf{u} \lt \beta\) but \(\mathbf{a}^\mathsf{T}\mathbf{x} \geq \beta\) for all \(\mathbf{x} \in P\).