In the previous part, we showed that a polytope is the convex hull of its extreme points. We now consider the opposite question: Is the convex hull of a finite set of points a polytope? The answer to this question turns out to be an important ingredient for combinatorial optimization problems, thus serving as a preview to MATH 3802.
Theorem 12.5. Let \(\mathbf{u}^1,\ldots,\mathbf{u}^k \in \mathbb{R}^n\). Then \(\operatorname{conv}(\{\mathbf{u}^1,\ldots,\mathbf{u}^k\})\) is a polytope.
Proof. Note that the convex hull of a finite number of points is bounded. Let \(P = \operatorname{conv}(\{\mathbf{u}^1,\ldots,\mathbf{u}^k\})\). We show that \(P = \{ \mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b}\}\) for some \(\mathbf{A} \in \mathbb{R}^{m\times n}\) and \(\mathbf{b}\in \mathbb{R}^m\) where \(m\) is a positive integer.
Note that the convex hull is the set of \(\mathbf{x}\) satisfying \begin{eqnarray*} \lambda_1 \mathbf{u}^1 + \cdots + \lambda_k \mathbf{u}^k = \mathbf{x} \\ \lambda_1 + \cdots + \lambda_k = 1 \\ \lambda_1,\ldots, \lambda_k \geq 0. \end{eqnarray*}
The above system can be written as a system of inequalities with variables \(\lambda_1,\ldots,\lambda_k,x_1,\ldots,x_n\). Now, apply Fourier-Motzkin elimination method to eliminate \(\lambda_1,\ldots, \lambda_k\) to obtain a system that involves only \(x_1,\ldots,x_n\). Then this system is a desired system as it defines all the \(\mathbf{x}\) that can be written as a convex combination of \(\mathbf{u}^1,\ldots,\mathbf{u}^k \in \mathbb{R}^n\).
We use the process in the proof (with some short-cuts) to obtain the inequalities that define the convex hull of \(\left\{\begin{bmatrix} 1 \\1 \end{bmatrix}, \begin{bmatrix} 2\\ 3\end{bmatrix}\right\}\). The convex hull is given by \(\begin{bmatrix} x_1 \\ x_2\end{bmatrix}\) such that \begin{eqnarray*} \lambda_1 + 2\lambda_2 - x_1 = 0 \\ \lambda_1 + 3\lambda_2 - x_2 = 0 \\ \lambda_1 + \lambda_2 = 1 \\ \lambda_1, \lambda_2 \geq 0 \end{eqnarray*} Using \(\lambda_1 = 1-\lambda_2\), we obtain that \begin{eqnarray*} \lambda_2 = x_1 -1 \\ \lambda_2 = \frac{1}{2} x_2 - \frac{1}{2} \\ 0 \leq \lambda_2 \leq 1 \end{eqnarray*} Using, \(\lambda_2 = x_1 - 1\), we obtain \begin{eqnarray*} x_1 - 1 = \frac{1}{2} x_2 - \frac{1}{2} \\ 0 \leq x_1 - 1 \leq 1 \\ \end{eqnarray*} which simplifies to \begin{eqnarray*} 2x_1 - x_2 = 1 \\ 1 \leq x_1 \leq 2 \\ \end{eqnarray*} It can be seen that these constraints define the line segment between \(\begin{bmatrix} 1 \\1 \end{bmatrix}\) and \(\begin{bmatrix} 2\\ 3\end{bmatrix}\).
We now have two ways to represent a polytope. The first is to describe it as the solution set of a finite number of linear inequalities. Such a representation is often called the H-representation. The second is to describe it as the convex hull of a finite number of points. Such a representation is often called the V-representation.
Now, it can be shown that opimizing a linear objective over a finite set of points in \(\mathbb{R}^n\) is equivalent to optimizing over the convex hull of the set. The theorem above says that the convex hull is in fact a polytope. Combining these two facts, we see that we can recast the problem as a linear progrmaming problem provided that we can generate the inequalities describing the polytope; i.e. obtain the H-representation of the polytope.
To illustrate the main ideas, consider the Binary Knapsack Problem: Given a knapsack with weight capacity \(K\) and \(n\) items such that item \(i\) has value \(v_i\) and weight \(w_i\) for \(i = 1,\ldots, n\), find a subset of items maximizing total value such that the total weight does not exceed \(K\).
We first show how to encode selections of items as points in \(\mathbb{R}^n\). For a subset \(M\) of \(\{1,\ldots,n\}\), we define the characteristic vector (or incidence vector) of \(M\), denoted \(\chi^M\), as the \(n\)-tuple such that its \(i\)th component equals 1 if \(i \in M\) and equals 0 otherwise. For example, if \(n = 3\) and \(M = \{2,3\}\), then \(\chi^M = \begin{bmatrix} 0 \\1 \\ 1\end{bmatrix}\).
Let \({\cal F} = \{ I\subseteq\{1,\ldots,n\} : \displaystyle\sum_{i \in I} w_i \leq K\}\). Let \(S = \{ \chi^M : M \in {\cal F}\}\). Then the Binary Knapsack Problem can be formulated as the problem of maximizing \(\displaystyle\sum_{i=1}^n v_i x_i\) subject to \(\mathbf{x} \in S\). As remarked above, if we can find inequalities that define the polytope given by the convex hull of \(S\), we will have a linear programming problem. Of course, the difficulty is finding these inequalities. (The method described in the proof of the theorem above is incredibly inefficient as there are exponentially many elements in \(S\) and the Fourier-Motzkin elimination method itself is not entirely efficient either.) Fortunately, for some combinatorial optimization problems, complete descriptions of the inequalities are known. Polyhedral combinatorics is an area of mathematics that studies, among other things, ways to identify and obtain such inequalities.
Let \(P\) be the convex hull of \( \left\{ \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} 2 \\ 1 \\ 1 \end{bmatrix}, \begin{bmatrix} -1 \\ 0 \\ 1 \end{bmatrix} \begin{bmatrix} 1 \\ 1 \\ 0 \end{bmatrix} \right \}.\) Give a system of inequalities that defines \(P\).
Let \(M\) be a 2-element subset of \(\{1,2,3,4,5\}\) such that it contains a prime or the sum of its elements is a prime. List all possible characteristic vectors of \(M\).