Bounded polyhedron

A set $S\subseteq {\mathbb{R}}^n$ is said to be bounded if there exists $M>0$ such that $\Vert \mathbf{x}\Vert \le M$ for all $\mathbf{x}\in S$.

A polyhedron $P\subseteq {\mathbb{R}}^n$ is called a polytope if it is bounded. For example, the polyhedron $P=\{\left[\begin{array}{c}{x}_1\\ x_2\end{array}\right]:-x_1-x_2\ge -1,x_1,x_2\ge 0\}$ 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 $|x_i|\le \gamma$ for $i=1,\dots ,n$ for some positive real number $\gamma$. Then $\Vert \mathbf{x}\Vert =\sqrt{\sum _{i=1}^n{x}_i^2}\le \sqrt{n{\gamma }^2}=\sqrt{n}\gamma$, implying that $P$ is bounded.

In our example, we already have the inequalities $x_1,x_2\ge 0$. Hence, $x_1$ and $x_2$ are bounded below by 0. Now, adding the inequalities $-x_1-x_2\ge -1$ and $x_2\ge 0$ gives $-x_2\ge -1$, which is equivalent to $x_2\le 1$. Finally, adding the inequalities $-x_1-x_2\ge -1$ and $x_1\ge 0$ gives $-x_1\ge -1$, which is equivalent to $x_1\le 1$. Thus, $\Vert \mathbf{x}\Vert \le \sqrt{2}$ for all $\mathbf{x}\in P$ and so $P$ is a bounded polyhedron and thus a polytope.

Note that every nonempty polytope is pointed because as a bounded set, it cannot contain any line. Therefore, a polytope has at least one extreme point. In fact, we can say more.

Proposition 12.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 12.4. Let $\mathbf{v},{\mathbf{u}}^1,\dots ,{\mathbf{u}}^k\in {\mathbb{R}}^n$ where $n$ is a positive integer. If $\mathbf{v}\notin \mathrm{conv}(\{{\mathbf{u}}^1,\dots ,{\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}<\beta$ and ${\mathbf{a}}^{\mathsf{T}}{\mathbf{u}}^i\ge \beta$ for $i=1,\dots ,k$. (This lemma is a special case of the more general Separating Hyperplane Theorem.)

Worked Examples

1. Is $P=\{\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]:\begin{array}{c}{x}_1-x_2+2x_3\ge 2\\ -x_1+2x_2-3x_3\ge 0\\ x_2+x_3\ge 1\\ x_3\ge 0\end{array}\}$ a polytope? Justify your answer.

   Since $P$ is the intersection of halfspaces, $P$ is a polyhedron.

   Note that $P$ is bounded if and only if the linear programming problems $min\{x_i:\mathbf{x}\in P\}$ and $max\{x_i:\mathbf{x}\in P\}$ are bounded for each $i=1,2,3$. Hence, we might need to solve up to six linear programming problems using this method. (For larger problems, it is advisable to use a linear programming solver.) We start with $min\{x_1:\mathbf{x}\in P\}$. Using Fourier-Motzkin elimination method to eliminate $x_2$, we obtain $$\begin{array}{rl}\frac{1}{2}{x}_1+\frac{1}{2}{x}_3& \ge 2\\ x_1+3x_3& \ge 3\\ x_3& \ge 0.\end{array}$$ (The first inequality comes from adding $x_1-x_2+2x_3\ge 2$ and $\frac{1}{2}$ times $-x_1+2x_2-3x_3\ge 0$. The second inequality comes from adding $x_1-x_2+2x_3\ge 2$ and $x_2+x_3\ge 1$.)

   Now, eliminating $x_3$ results in no inequalities on $x_1$. Thus, the linear programming problem $min\{x_1:\mathbf{x}\in P\}$ is unbounded, implying that $P$ is an unbounded set and therefore not a polytope.

2. Let $P=\{\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right]:\begin{array}{c}-x_1-2x_2-3x_3\ge -6\\ x_1,x_2,x_3\ge 0\end{array}\}$. 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=\{\mathbf{x}\in {\mathbb{R}}^n:\mathbf{A}\mathbf{x}\ge \mathbf{b}\}$ and ${\mathbf{x}}^{\ast }\in P$, then, where ${\mathbf{A}}^{=}\mathbf{x}\ge {\mathbf{b}}^{=}$ is the subsystem of $\mathbf{A}\mathbf{x}\ge \mathbf{b}$ consisting of the inequalities satisfied with equality by ${\mathbf{x}}^{\ast }$, ${\mathbf{x}}^{\ast }$ is an extreme point of $P$ if and only if $\mathrm{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}\ge \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\ge 0$ to equalities gives the unique solution $\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$ which is in $P$. Hence, $\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right]$ is an extreme point of $P$.

   Setting $-x_1-2x_2-3x_3\ge -6,x_1,x_2\ge 0$ to equalities gives the unique solution $\left[\begin{array}{c}0\\ 0\\ 2\end{array}\right]$ which is in $P$. Hence, $\left[\begin{array}{c}0\\ 0\\ 2\end{array}\right]$ is an extreme point of $P$.

   Setting $-x_1-2x_2-3x_3\ge -6,x_1,x_3\ge 0$ to equalities gives the unique solution $\left[\begin{array}{c}0\\ 3\\ 0\end{array}\right]$ which is in $P$. Hence, $\left[\begin{array}{c}0\\ 3\\ 0\end{array}\right]$ is an extreme point of $P$.

   Setting $-x_1-2x_2-3x_3\ge -6,x_2,x_3\ge 0$ to equalities gives the unique solution $\left[\begin{array}{c}6\\ 0\\ 0\end{array}\right]$ which is in $P$. Hence, $\left[\begin{array}{c}6\\ 0\\ 0\end{array}\right]$ is an extreme point of $P$.

   Thus $P=\mathrm{conv}\left(\{\left[\begin{array}{c}0\\ 0\\ 0\end{array}\right],\left[\begin{array}{c}0\\ 0\\ 2\end{array}\right],\left[\begin{array}{c}0\\ 3\\ 0\end{array}\right],\left[\begin{array}{c}6\\ 0\\ 0\end{array}\right]\}\right)$.

3. Let $P$ be the convex hull of $\{\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}-1\\ -2\\ 0\end{array}\right],\left[\begin{array}{c}1\\ 1\\ -2\end{array}\right]\}$. Let $\mathbf{u}=\left[\begin{array}{c}1\\ 1\\ 1\end{array}\right]$. 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}<\beta$ but ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}\ge \beta$ for all $\mathbf{x}\in P$.

   Note that we can obtain $\mathbf{a}$ and $\beta$ by following the proof of the lemma and find a solution to the following problem with positive objective function value: $$\begin{array}{rl}max& y_0+y_1+y_2+y_3\\ \text{s.t.}& y_0+y_2+y_3\le 0\\ & y_0-y_1-2y_2\le 0\\ & y_0+y_1+y_2-2y_3\le 0\end{array}$$ The problem is small enough for trial and error. Note that setting $y_0=-\frac{1}{3}$, $y_1=1$, $y_2=0$, and $y_3=\frac{1}{3}$ gives a feasible solution with objective function value 1. Hence, we can set $\beta =-\frac{1}{3}$ and $\mathbf{a}=\left[\begin{array}{c}-1\\ 0\\ -\frac{1}{3}\end{array}\right]$.

   One can check that ${\mathbf{a}}^{\mathsf{T}}\mathbf{x}\ge \beta$ for each $\mathbf{x}\in \{\left[\begin{array}{c}0\\ 1\\ 1\end{array}\right],\left[\begin{array}{c}-1\\ -2\\ 0\end{array}\right],\left[\begin{array}{c}1\\ 1\\ -2\end{array}\right]\}$ and that ${\mathbf{a}}^{\mathsf{T}}\mathbf{u}<\beta$.