Back

Extreme points

Let \(C\subseteq \mathbb{R}^n\) be a convex set. Let \(\mathbf{z} \in \mathbb{R}^n\). We say that \(\mathbf{z}\) is an extreme point of \(C\) if \(\mathbf{z} \in C\) and there do not exist distinct \(\mathbf{x},\mathbf{y} \in C\) and \(\lambda\) with \(0 \lt \lambda \lt 1\) such that \(z = (1-\lambda) \mathbf{x} + \lambda \mathbf{y}\).

In other words, an extreme point is a point in \(C\) that is not in the interior of any line segment in \(C\). In two and three dimensions, the corners of a polyhedron are the extreme points. However, it would be a mistake to think that extreme points are always the “sharp ends” of a set. For example, every point on the boundary of the unit disc in \(\mathbb{R}^2\) is an extreme point.

In general, determining if a given point is an extreme point from first principle can be difficult. Fortunately, the following result makes identifying extreme points of a polyhedron rather straightforward. The proof is left as an exercise.

Proposition 8.4. Let \(P = \left \{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b} \right \}\). Let \(\mathbf{x}^* \in P\). Let \(\mathbf{A}^= \mathbf{x} \geq \mathbf{b}^=\) be the subsystem of \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) consisting of all the inequalities satisfied with equality by \(\mathbf{x}^*\). (The inequalities in \(\mathbf{A}^= \mathbf{x} \geq \mathbf{b}^=\) are said to be active at \(\mathbf{x}^*\).) Then \(\mathbf{x}^*\) is an extreme point of \(P\) if and only if \(\operatorname{rank}(\mathbf{A}^=) = n\).

Example. Let \(P = \left \{\mathbf{x} \in \mathbb{R}^3 : \mathbf{A}\mathbf{x} \geq \mathbf{b}\right \}\) where \(\mathbf{A} = \begin{bmatrix} 1 & 2 & -2 \\ 0 & 1 & -2 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1\end{bmatrix}\) and \(\mathbf{b} = \begin{bmatrix} 3 \\ 1 \\ 0 \\ 0 \\ 0 \end{bmatrix}\).

Consider \(\mathbf{x}^*=\begin{bmatrix} 1 \\ 1 \\ 0\end{bmatrix}\). Since \(\mathbf{A}\mathbf{x}^*=\begin{bmatrix} 3 \\ 1 \\ 1\\ 1 \\ 0 \end{bmatrix} \geq \mathbf{b}\), we see that \(\mathbf{x}^*\in P\) and \(\mathbf{A}^= =\begin{bmatrix} 1 & 2 & -2 \\0 & 1 & -2\\ 0& 0 &1\end{bmatrix}\) since the first, second, and last inequalities are active at \(\mathbf{x}^*\). As \(\operatorname{rank}(\mathbf{A}^=) =3\), \(\mathbf{x}^*\) is an extreme point of \(P\) by Proposition 8.4.
Consider \(\mathbf{x}^*=\begin{bmatrix} 0 \\ 3 \\ 1\end{bmatrix}\). Since \(\mathbf{A}\mathbf{x}^*=\begin{bmatrix} 4 \\ 1 \\ 0\\ 3 \\ 1 \end{bmatrix} \geq \mathbf{b}\), we see that \(\mathbf{x}^*\in P\) and \(\mathbf{A}^= =\begin{bmatrix} 0 & 1 & -2 \\ 1 & 0 & 0\end{bmatrix}\) since the second and the third inequalities are active at \(\mathbf{x}^*\). As \(\mathbf{A}^=\) has rank \(2\), As \(\operatorname{rank}(\mathbf{A}^=) = 2 \lt 3\), \(\mathbf{x}^*\) is not an extreme point of \(P\) by Proposition 8.4.

Corollary 8.5. The number of extreme points of a polyhedron is finite.

Proof. Consider a polyhedron \(P\). Let \(\mathbf{A}\) and \(\mathbf{b}\) be such that \(P = \left \{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b} \right \}\). Since every extreme point of \(P\) is the unique solution to a system of equations obtained from setting the inequalities of a subsystem of \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) to equalities, the number of extreme points of \(P\) must be finite as there are only be finitely many subsystems of \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\).

A nonempty polyhedron is said to be pointed if it contains at least one extreme point. The following is a useful result.

Theorem 8.6. A nonempty polyhedron is pointed if and only if it does not contain a line.

Proof. We prove the direction that if a nonempty polyhedron is pointed, then it does not contain a line. The other direction is left as an exercise.

Let \(P = \left \{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b} \right \}\) be a pointed polyhedron where \(\mathbf{A}\in \mathbb{R}^{m\times n}\) and \(\mathbf{b}\in \mathbb{R}^{m}\). Let \(\mathbf{x}^* \in P\) be an extreme point. Let \(\mathbf{A}^= \mathbf{x} \geq \mathbf{b}^=\) be the subsystem of \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) consisting of the inequalities active at \(\mathbf{x}^*\). By the above proposition, \(\operatorname{rank}(\mathbf{A}^=) = n\), implying that \(\operatorname{rank}(\mathbf{A}) = n\).

Observe that in order for \(P\) to contain the line \(\{\mathbf{u} + \lambda \mathbf{d} : \lambda \in \mathbb{R}\}\), where \(\mathbf{d} \neq \mathbf{0}\), we must have \(\mathbf{A}\mathbf{d} = \mathbf{0}\). However, this is not possible since the nullity of \(\mathbf{A}\) is zero. Hence, \(P\) does not contain any line.

Extreme point optimal solution

We now show the following important result in linear programming.

Theorem 8.7. Let \(\mathbf{c} \in \mathbb{R}^n\) and let \(P\) be a pointed polyhedron in \(\mathbb{R}^n\), where \(n\) is a positive integer. Consider the linear programming problem \((LP)\) given by \[\min\{ \mathbf{c}^\mathsf{T}\mathbf{x} : \mathbf{x} \in P\}.\] If \((LP)\) has an optimal solution, then it has an optimal solution that is an extreme point of \(P\).

Proof. Assume 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.

Let \(\mathbf{x}^*\) be an optimal solution to \((LP)\) having as many active inequalities from \(\mathbf{A}\mathbf{x}\geq \mathbf{b}\) as possible. Let \(\mathbf{A}^=\mathbf{x}\geq \mathbf{b}^=\) be the subsystem of \(\mathbf{A}\mathbf{x}\geq \mathbf{b}\) consisting of all the inequalities active at \(\mathbf{x}^*\). If \(\operatorname{rank}(\mathbf{A}^=) = n\), then \(\mathbf{x}^*\) is an extreme point of \(P\) by Proposition 8.4 and we are done.

Suppose that \(\operatorname{rank}(\mathbf{A}^=) \lt n\). Let \(\mathbf{d}\in \mathbb{R}^n\) be a nonzero vector in the nullspace of \(\mathbf{A}^=\). Note that for a sufficiently small \(\epsilon \gt 0\), \(\mathbf{x}^* \pm \epsilon \mathbf{d} \in P\). Since \(\mathbf{x}^*\) is optimal, we must have \(\mathbf{c}^\mathsf{T}(\mathbf{x}^* \pm \epsilon \mathbf{d}) \geq \mathbf{c}^\mathsf{T}\mathbf{x}^*\), implying that \(\mathbf{c}^\mathsf{T} \mathbf{d} = 0\).

As \(P\) is pointed, by Theorem 8.6, \(P\) does not contain the line \(\{ \mathbf{x}^* + \lambda \mathbf{d} : \lambda \in \mathbb{R} \}\). We may assume that there exists \(\lambda \gt 0\) such that \(\mathbf{x}^* + \lambda \mathbf{d}\notin P\). (Otherwise, we replace \(\mathbf{d}\) with its negation.) Let \(\lambda' \gt 0\) be the largest value such that \(\mathbf{x}' := \mathbf{x}^* + \lambda' \mathbf{d}\in P\). Then \(\mathbf{x}'\) is an optimal solution since \(\mathbf{c}^\mathsf{T}\mathbf{x}' = \mathbf{c}^\mathsf{T}( \mathbf{x}^* + \lambda' \mathbf{d}) = \mathbf{c}^\mathsf{T}\mathbf{x}^* + \lambda' \mathbf{c}^\mathsf{T}\mathbf{d} = \mathbf{c}^\mathsf{T}\mathbf{x}^*\) but it satisfies at least one more inequality in \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) with equality than \(\mathbf{x}^*\), contradicting our choice of \(\mathbf{x}^*\).

Worked examples

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

Suppose that \(\operatorname{rank}(\mathbf{A}^=) \lt n\). Then there exists nonzero \(\mathbf{d}\in \mathbb{R}^n\) such that \(\mathbf{A}^= \mathbf{d} = \mathbf{0}\). Since \(\mathbf{x}^*\) satisfies the nonactive inequalities in \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) strictly, for a sufficiently small \(\epsilon \gt 0\), \(\mathbf{x}^* \pm \epsilon \mathbf{d} \in P\). But \(\mathbf{x}^* = \frac{1}{2}(\mathbf{x}^* + \epsilon \mathbf{d}) + \frac{1}{2}(\mathbf{x}^* + \epsilon \mathbf{d})\) and \(\mathbf{x}^*,\mathbf{x}^* \pm \epsilon \mathbf{d}\) are distinct. Hence, \(\mathbf{x}^*\) is not an extreme point of \(P\).

Conversely, suppose that \(\operatorname{rank}(\mathbf{A}^=) = n\). Let \(\mathbf{u},\mathbf{v} \in P\) and \(\lambda \in (0,1)\) be such that \(\mathbf{x}^* = (1-\lambda)\mathbf{u} + \lambda \mathbf{v}\). It suffices to show that \(\mathbf{u} = \mathbf{v} = \mathbf{x}^*\).

Now, \( \mathbf{b}^= = (1-\lambda)\mathbf{b}^= +\lambda \mathbf{b}^= \leq (1-\lambda) \mathbf{A}^= \mathbf{u} + \lambda \mathbf{A}^=\mathbf{v} = \mathbf{A}^= ( (1-\lambda)\mathbf{u} + \lambda \mathbf{v}) = \mathbf{A}^=\mathbf{x}^* = \mathbf{b}^=\). Since \(\lambda, 1-\lambda \gt 0\), we must have \( \mathbf{A}^=\mathbf{u} = \mathbf{A}^=\mathbf{v} = \mathbf{b}^=\). But \(\operatorname{rank}(\mathbf{A}^=) = n\). So the system \(\mathbf{A}^=\mathbf{x} = \mathbf{b}^=\) has a unique solution, implying that \( \mathbf{u} = \mathbf{v} = \mathbf{x^*}\).
Prove that if a nonempty polyhedron is not pointed, then it contains a line.

Let \(P = \{ \mathbf{x}\in \mathbf{R}^n : \mathbf{A}\mathbf{x} \geq \mathbf{b}\}\) be a nonempty polyhedron where \(\mathbf{A} \in \mathbb{R}^{m \times n}\), \(\mathbf{b} \in \mathbb{R}^m\), and \(m\) is a positive integer.

Suppose that \(P\) has no extreme point. Let \(x^* \in P\) be such that the number of active inequalities is as large as possible. Let \(\mathbf{A}^=\mathbf{x}\geq \mathbf{b}^=\) be the subsystem of \(\mathbf{A}\mathbf{x}\geq \mathbf{b}\) consisting of all the inequalities active at \(\mathbf{x}^*\). Then \(\operatorname{rank}(\mathbf{A}^=) \lt n\) by the above proposition.

Let \(\mathbf{d}\in \mathbb{R}^n\) be a nonzero vector in the nullspace of \(\mathbf{A}^=\). We claim that \(P\) contains the line \(\{ \mathbf{x}^* + \lambda \mathbf{d} : \lambda \in \mathbb{R}\}\). Suppose not. Then there exists \(\lambda' \in \mathbb{R}\) such that \(\mathbf{x}^* + \lambda' \mathbf{d} \notin P\). We may assume that \(\lambda' \gt 0\). (Otherwise, replace \(\mathbf{d}\) with its negation.) Then \(\mathbf{A}\mathbf{d}\) has at least one negative component.

Let \({\mathbf{A}'} \mathbf{x} \geq \mathbf{b}'\) denote the inequalities in \(\mathbf{A}\mathbf{x} \geq \mathbf{b}\) that are not active at \(\mathbf{x}^*\). Then there exists a largest value \(\bar{\lambda}\) such that \(\mathbf{A}'(\mathbf{x}^* + \bar{\lambda} \mathbf{d}) \geq \mathbf{b}'\) but for all \(\lambda \gt \bar{\lambda}\), \(\mathbf{A}(\mathbf{x}^* + \lambda \mathbf{d}) \geq \mathbf{b}'\) fails to hold. As \(\mathbf{A}'\mathbf{x}^* \gt \mathbf{b}'\), \(\bar{\lambda} \gt 0\). Note that the inequalities in \(\mathbf{A}^= \mathbf{x} \geq \mathbf{b}^=\) are active at \(\mathbf{x}^* + \bar{\lambda} \mathbf{d}\). Then \(\mathbf{x}' := \mathbf{x}^* + \bar{\lambda} \mathbf{d} \in P\) but with at least one more active inequalities than \(\mathbf{x}^*\), contradicting our choice of \(\mathbf{x}^*\).
Let \(\mathbf{A}\in\mathbb{R}^{m \times n}\) with \(\operatorname{rank}( \mathbf{A}) = m\). Let \(\mathbf{b} \in \mathbb{R}^m\). Let \(P = \left \{ \mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} = \mathbf{b},~ \mathbf{x} \geq \mathbf{0}\right \}\). Prove that \(\mathbf{x^*} \in P\) is an extreme point of \(P\) if and only if \(\mathbf{x^*}\) is a basic feasible solution to \(\mathbf{A}\mathbf{x} = \mathbf{b},~\mathbf{x} \geq \mathbf{0}\).

Let \(\mathbf{x}^*\) be such that \(\mathbf{Ax^*} = \mathbf{b}, \mathbf{x}^* \geq \mathbf{0}\). Note that we can rewrite this as \(\begin{bmatrix} \mathbf{A} \\ -\mathbf{A} \\ \mathbf{I_n} \end{bmatrix} \mathbf{x}^* \geq \begin{bmatrix} \mathbf{b} \\ -\mathbf{b} \\ \mathbf{0} \end{bmatrix}\).

Let \(N = \{i : x^*_i = 0\}\). Let \(\mathbf{Z}\) denote the matrix consisting of the rows of the \(I_n\) indexed by elements in \(N\) . By Proposition 11.1, \(\mathbf{x}^*\) is an extreme point if and only if the matrix \(\begin{bmatrix} \mathbf{A} \\ -\mathbf{A} \\ \mathbf{Z}\end{bmatrix}\) has rank \(n\).

Note that the rank of \(\begin{bmatrix} \mathbf{A} \\ -\mathbf{A} \\ \mathbf{Z}\end{bmatrix}\) is the same as the rank of \(\begin{bmatrix} \mathbf{A} \\ Z\end{bmatrix}.\) Since the rank of \(\mathbf{Z}\) is \(|N|\) and one can eliminate the entries in columns of \(\mathbf{A}\) indexed by elements in \(N\) using elementary row operations, the rank of \(\begin{bmatrix} \mathbf{A} \\ Z\end{bmatrix}\) is \(n\) if and only if the columns of \(\mathbf{A}\) indexed by elements not in \(N\) are linearly independent. The result now follows from Proposition 6.1.
Let \(P = \left \{ \mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} = \mathbf{b},~ \mathbf{x} \geq \mathbf{0}\right \}\) where \(\mathbf{A} = \begin{bmatrix} 1 & 2 & 1 \\ 0 & 3 & -1\end{bmatrix}\) and \(\mathbf{b} = \begin{bmatrix} 3 \\ 2\end{bmatrix}\). How many extreme points does \(P\) have?

By the previous question, it suffices to count how many basic feasible solutions that system \(\mathbf{Ax} = \mathbf{b}, \mathbf{x} \geq \mathbf{0}\) has.

With basis \(B = \{1,2\}\), the basic solution to \(\mathbf{Ax} = \mathbf{b}\) is \(\begin{bmatrix} \frac{5}{3} \\ \frac{2}{3} \\ 0\end{bmatrix}\) which is a basic feasible solution and is therefore an extreme point.

With basis \(B = \{1,3\}\), the basic solution to \(\mathbf{Ax} = \mathbf{b}\) is \(\begin{bmatrix} 5 \\ 0 \\ -2\end{bmatrix}\) which is not a basic feasible solution.

With basis \(B = \{2,3\}\), the basic solution to \(\mathbf{Ax} = \mathbf{b}\) is \(\begin{bmatrix} 0 \\ 1 \\ 1\end{bmatrix}\) which is a basic feasible solution and is therefore an extreme point.

Hence, \(P\) has exactly two extreme points.