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 certain combinatorial optimization problems.
Theorem 9.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. The convex hull of a finite number of elements of \(\mathbb{R}^n\) is clearly 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\). Applying the Fourier-Motzkin elimination method to eliminate \(\lambda_1,\ldots, \lambda_k\), we obtain a system that involves only \(x_1,\ldots,x_n\) which defines all the \(\mathbf{x}\) that can be written as a convex combination of \(\mathbf{u}^1,\ldots,\mathbf{u}^k\).
Example. 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.
Theorem 9.2 states 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. Theorem 9.5 above says that the convex hull is in fact a polytope. Combining these two results, we can recast the problem of opimizing a linear objective over a finite set of points in \(\mathbb{R}^n\) as a linear progrmaming problem provided that we can easily generate the inequalities describing the polytope; i.e. obtain the H-representation of the polytope.
To illustrate the main ideas, let us revisit 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\).
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. As the Binary Knapsack Problem is NP-hard, a simple description of all these inequalities probably does not exist. Furthermore, the number of inequalities will be exponential in \(n\). 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\).