22.3 Convex Polyhedra, Geometrically

Chapter 18 built the theory of convex sets and proved its main theorems: that a compact convex set is the hull of its extreme points, that a bounded polyhedron and a polytope are the same thing, and that a feasible, bounded linear program and its dual have the same optimal value. This section proves none of that again. It reads those theorems as statements about the geometry of a solid with flat sides: what its faces are, how they fit together, and what a linear program looks like when the objective is a family of parallel hyperplanes sliding across it. Everything here is a corollary of Chapter 18 or a short argument on top of it, and every citation points back there.

Throughout, the field is $\mathbb{R}$ and the space is $\mathbb{R}^n$ with the dot product, as in Chapter 18. A polyhedron is a set $P = \{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \le \mathbf{b}\}$ (Definition 18.9.2), with $\mathbf{A} \in M_{m \times n}(\mathbb{R})$ whose rows we write $\mathbf{a}_1^{\top}, \dots, \mathbf{a}_m^{\top}$ , so that $\mathbf{A}\mathbf{x} \le \mathbf{b}$ is the list of inequalities $\mathbf{a}_i^{\top}\mathbf{x} \le b_i$ . A vertex of $P$ is an extreme point of it (Definition 18.8.1), and $\operatorname{ext} P$ is the set of them. We use Chapters 16 and 18’s topological words — closed, bounded, compact — only inside the results we cite; nothing here develops them further.

22.3.1. Faces, cut by a supporting hyperplane

A cube has six square sides, twelve edges and eight corners, and each of them is the part of the cube touched by a plane that has the whole cube on one side. That is the picture to formalize. The tool is Chapter 18’s supporting hyperplane (Theorem 18.3.6): a hyperplane through a point of a convex set with the set in one of its closed half-spaces.

A face of a polyhedron is the part of it touched by a hyperplane that does not cut into it.

Definition 22.3.1 (Face of a Polyhedron)

Let $P \subseteq \mathbb{R}^n$ be a polyhedron. A face of $P$ is a set of the form $F = \{\mathbf{x} \in P : \mathbf{c}^{\top}\mathbf{x} = \beta\}$ for some $\mathbf{c} \in \mathbb{R}^n$ and $\beta \in \mathbb{R}$ such that $\mathbf{c}^{\top}\mathbf{x} \le \beta$ for every $\mathbf{x} \in P$ . A face other than $P$ itself is called proper.

Clause by clause. The pair $(\mathbf{c}, \beta)$ must be a valid inequality for $P$ : the whole polyhedron lies in the closed half-space $\{\mathbf{c}^{\top}\mathbf{x} \le \beta\}$ . The face is then what the boundary hyperplane $\{\mathbf{c}^{\top}\mathbf{x} = \beta\}$ actually touches. Note that $\mathbf{c}$ is allowed to be $\mathbf{0}$ .

Two faces come free. Taking $\mathbf{c} = \mathbf{0}$ and $\beta = 0$ makes the inequality $0 \le 0$ , valid everywhere, and $F = P$ : the whole polyhedron is a face of itself. Taking $\mathbf{c} = \mathbf{0}$ and $\beta = 1$ makes the inequality $0 \le 1$ , again valid, and $F = \emptyset$ : the empty set is a face. These two are the degenerate cases, and they are kept because the theorems below are cleaner with them than without.

Chapter 18 §08 already has a notion of face for an arbitrary convex set, Definition 18.8.2: a convex subset $F \subseteq C$ that swallows every segment of $C$ passing through it at an inner point. The two agree here in one direction at once.

Remark. Every face in the sense of Definition 22.3.1 is a face in the sense of Definition 18.8.2. That is exactly Proposition 18.8.4 (a), applied with $\mathbf{w} = \mathbf{c}$ and $\alpha = \beta$ , since on $\mathbb{R}^n$ the inner product $\langle \mathbf{c}, \mathbf{x} \rangle$ is $\mathbf{c}^{\top}\mathbf{x}$ . So everything Chapter 18 proves about faces applies to ours; in particular Lemma 18.8.3 gives $\operatorname{ext} F = F \cap \operatorname{ext} P$ . The converse — that every face of a polyhedron in Chapter 18’s sense is cut out by a supporting hyperplane — is also true, and Exercise (C2: The two notions of face agree for a polyhedron) proves it. It uses flatness: the same exercise ends with a round convex set having a one-point face in the sense of Definition 18.8.2 that no supporting hyperplane isolates, so the converse fails for general convex sets.

Examples, in $\mathbb{R}^2$ , with $P$ the triangle $\{x_1 \ge 0,\ x_2 \ge 0,\ x_1 + x_2 \le 3\}$ of Chapter 18 §09.

$\mathbf{c} = (1,1)$ , $\beta = 3$ . The inequality is valid by the third row, and the face is the slanted edge from $(3,0)$ to $(0,3)$ .
$\mathbf{c} = (1,0)$ , $\beta = 3$ . Valid, since $x_1 \le x_1 + x_2 \le 3$ on $P$ . The face is the single point $(3, 0)$ : the hyperplane $x_1 = 3$ touches the triangle at one corner.
$\mathbf{c} = (-1, 0)$ , $\beta = 0$ . Valid by the first row, and the face is the vertical edge $\{0\} \times [0,3]$ .
$\mathbf{c} = (1, 1)$ , $\beta = 4$ . Valid, but never attained: the face is $\emptyset$ .

A non-example by minimal change. In example 1 replace $\beta = 3$ by $\beta = 2$ . The set $\{\mathbf{x} \in P : x_1 + x_2 = 2\}$ is still a segment inside $P$ , still convex, and still a slice by a hyperplane. What fails is the one clause the definition insists on: $x_1 + x_2 \le 2$ is not valid for $P$ , since $(3,0) \in P$ violates it. The hyperplane cuts through the triangle instead of resting against it, and the slice is not a face. It also fails Definition 18.8.2: the segment from $(0,0)$ to $(3,0)$ passes through $(2,0)$ at an inner point but is not contained in the slice.

The reason faces are useful is that there are only finitely many of them, and each is again a polyhedron described by the same rows, some of them turned into equations.

Proposition 22.3.1 (Faces Are Polyhedra, and There Are Finitely Many)

Let $P = \{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \le \mathbf{b}\}$ with $m$ rows. For $J \subseteq \{1, \dots, m\}$ put $P_J = \{\mathbf{x} \in P : \mathbf{a}_i^{\top}\mathbf{x} = b_i \text{ for every } i \in J\} .$ Then:

(a) every $P_J$ is a face of $P$ , and it is a polyhedron;
(b) every non-empty face of $P$ equals $P_J$ for some $J$ ;
(c) consequently $P$ has at most $2^m$ non-empty faces, and every face of $P$ is a polyhedron.

Idea. For (a), add up the rows indexed by $J$ : the sum $\sum_{i \in J}\mathbf{a}_i^{\top}\mathbf{x}$ is at most $\sum_{i \in J}b_i$ on $P$ , and a sum of numbers each at most its bound hits the total bound only if every one of them does. So one valid inequality encodes all of $J$ at once.

For (b), let $F$ be a non-empty face and let $J$ collect the rows that are tight at every point of $F$ . Certainly $F \subseteq P_J$ . For the other inclusion we need a point $\mathbf{x}^{*}$ of $F$ at which every row outside $J$ is slack; averaging finitely many points of $F$ , one per slack row, produces it. Then, given $\mathbf{y} \in P_J$ with $\mathbf{c}^{\top}\mathbf{y} < \beta$ , step from $\mathbf{x}^{*}$ away from $\mathbf{y}$ . The rows in $J$ are equations satisfied by both points, so they survive the step exactly; the rows outside $J$ have room at $\mathbf{x}^{*}$ , so they survive a short step. But the step raises $\mathbf{c}^{\top}\mathbf{x}$ above $\beta$ , which no point of $P$ may do.

Proof.

(a) Put $\mathbf{c} = \sum_{i \in J}\mathbf{a}_i$ and $\beta = \sum_{i \in J}b_i$ , with the empty sums $\mathbf{0}$ and $0$ . For $\mathbf{x} \in P$ , $\mathbf{c}^{\top}\mathbf{x} = \sum_{i \in J}\mathbf{a}_i^{\top}\mathbf{x} \le \sum_{i \in J}b_i = \beta ,$ so the inequality is valid. If $\mathbf{x} \in P$ and $\mathbf{c}^{\top}\mathbf{x} = \beta$ , then $\sum_{i \in J}(b_i - \mathbf{a}_i^{\top}\mathbf{x}) = 0$ is a sum of non-negative numbers, so each is zero and $\mathbf{x} \in P_J$ ; conversely every $\mathbf{x} \in P_J$ has $\mathbf{c}^{\top}\mathbf{x} = \beta$ . Hence $P_J = \{\mathbf{x} \in P : \mathbf{c}^{\top}\mathbf{x} = \beta\}$ is a face. It is a polyhedron because each equation $\mathbf{a}_i^{\top}\mathbf{x} = b_i$ is the pair of inequalities $\mathbf{a}_i^{\top}\mathbf{x} \le b_i$ and $-\mathbf{a}_i^{\top}\mathbf{x} \le -b_i$ , so $P_J$ is cut out by $m + \lvert J\rvert$ inequalities.
(b) Let $F = \{\mathbf{x} \in P : \mathbf{c}^{\top}\mathbf{x} = \beta\}$ be non-empty, with $\mathbf{c}^{\top}\mathbf{x} \le \beta$ on $P$ . Put $J = \{i : \mathbf{a}_i^{\top}\mathbf{x} = b_i \text{ for every } \mathbf{x} \in F\} .$ Then $F \subseteq P_J$ by the definition of $J$ , and it remains to prove $P_J \subseteq F$ .

First note that $F$ is convex: it is the intersection of the convex set $P$ (Proposition 18.9.1) with the solution set of a linear equation, which is convex as the preimage of a point under $\mathbf{x} \mapsto \mathbf{c}^{\top}\mathbf{x}$ (Proposition 18.1.1 (b)); an intersection of convex sets is convex by Proposition 18.1.1 (a).

Step 1: a point of $F$ with every row outside $J$ slack. For each $i \notin J$ choose, by the definition of $J$ , a point $\mathbf{x}_i \in F$ with $\mathbf{a}_i^{\top}\mathbf{x}_i < b_i$ . If $J = \{1, \dots, m\}$ let $\mathbf{x}^{*}$ be any point of $F$ . Otherwise let $k \ge 1$ be the number of indices outside $J$ and let $\mathbf{x}^{*} = \frac1k\sum_{i \notin J}\mathbf{x}_i$ , which lies in $F$ by convexity. For each $i \notin J$ , every term of $\mathbf{a}_i^{\top}\mathbf{x}^{*} = \frac1k\sum_{j \notin J}\mathbf{a}_i^{\top}\mathbf{x}_j$ is at most $b_i$ and the term $j = i$ is strictly less, so $\mathbf{a}_i^{\top}\mathbf{x}^{*} < b_i$ .

Step 2: the step away from $\mathbf{y}$ . Let $\mathbf{y} \in P_J$ and suppose, for a contradiction, that $\mathbf{c}^{\top}\mathbf{y} < \beta$ . For $t > 0$ put $\mathbf{z}_t = \mathbf{x}^{*} + t(\mathbf{x}^{*} - \mathbf{y})$ . For $i \in J$ we have $\mathbf{a}_i^{\top}\mathbf{x}^{*} = b_i$ , because $\mathbf{x}^{*} \in F \subseteq P_J$ , and $\mathbf{a}_i^{\top}\mathbf{y} = b_i$ , because $\mathbf{y} \in P_J$ ; hence $\mathbf{a}_i^{\top}\mathbf{z}_t = b_i + t(b_i - b_i) = b_i \le b_i .$ For $i \notin J$ put $\delta = \min_{i \notin J}(b_i - \mathbf{a}_i^{\top}\mathbf{x}^{*}) > 0$ and $M = \max_{i \notin J}\lvert\mathbf{a}_i^{\top}\mathbf{x}^{*} - \mathbf{a}_i^{\top}\mathbf{y}\rvert$ ; both are minima and maxima of finitely many numbers. Choose $t > 0$ with $tM < \delta$ , which is possible (any $t$ will do if $M = 0$ ). Then for $i \notin J$ , $\mathbf{a}_i^{\top}\mathbf{z}_t = \mathbf{a}_i^{\top}\mathbf{x}^{*} + t\bigl(\mathbf{a}_i^{\top}\mathbf{x}^{*} - \mathbf{a}_i^{\top}\mathbf{y}\bigr) \le \mathbf{a}_i^{\top}\mathbf{x}^{*} + tM < \mathbf{a}_i^{\top}\mathbf{x}^{*} + \delta \le b_i .$ So $\mathbf{z}_t \in P$ . But $\mathbf{c}^{\top}\mathbf{z}_t = \mathbf{c}^{\top}\mathbf{x}^{*} + t(\mathbf{c}^{\top}\mathbf{x}^{*} - \mathbf{c}^{\top}\mathbf{y}) = \beta + t(\beta - \mathbf{c}^{\top}\mathbf{y}) > \beta ,$ since $t > 0$ and $\beta - \mathbf{c}^{\top}\mathbf{y} > 0$ . This contradicts the validity of $\mathbf{c}^{\top}\mathbf{x} \le \beta$ on $P$ . Hence $\mathbf{c}^{\top}\mathbf{y} = \beta$ and $\mathbf{y} \in F$ , so $P_J \subseteq F$ and $F = P_J$ .
(c) There are $2^m$ subsets $J$ , so by (b) at most that many non-empty faces. Each of them is a polyhedron by (a), and the empty face is the polyhedron $\{\mathbf{x} : 0 \le -1\}$ . This proves the proposition.

The map $J \mapsto P_J$ is onto the non-empty faces but is very far from injective: adding to $J$ a row that is already tight everywhere on $P_J$ changes nothing, and adding two incompatible rows gives $\emptyset$ .

Warning. A row of the system need not be a side of the solid. In $P = \{\mathbf{x} \in \mathbb{R}^2 : x_1 \le 1,\ x_2 \le 1,\ x_1 + x_2 \le 3\}$ the third row is implied by the first two, since $x_1 + x_2 \le 2$ on $P$ . It defines no face except the empty one: $P_{\{3\}} = \{\mathbf{x} \in P : x_1 + x_2 = 3\} = \emptyset$ . So a polyhedron with $m$ rows can have far fewer than $m$ sides, and counting rows is not counting geometry. Conversely, Definition 22.3.1 never mentions the rows at all, which is why Proposition 22.3.1 has to prove that the faces can be read off them.

A non-empty face $F$ is a non-empty convex set, so it has a dimension: $\dim F = \dim \operatorname{aff} F$ , as in Chapter 18 §01, and $\operatorname{aff} F$ is the flat $\mathbf{p} + U$ of Proposition 18.1.4 — a flat in the sense of Definition 22.2.1. The graded vocabulary follows.

Proposition 22.3.2 (Three Descriptions of a Corner)

Let $P = \{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \le \mathbf{b}\}$ and $\mathbf{v} \in P$ . The following are equivalent.

(a) $\mathbf{v}$ is a vertex of $P$ , that is, an extreme point.
(b) $\{\mathbf{v}\}$ is a face of $P$ .
(c) Among the rows active at $\mathbf{v}$ there are $n$ linearly independent ones, that is, $\mathbf{v}$ is a basic feasible point.

Idea.

(a) and (c) are Theorem 18.9.2, already proved. A one-point face is an extreme point by Proposition 18.8.4 (b). For the remaining implication, take $J$ to be the active set: if the active rows have rank $n$ , the system $\mathbf{A}_J\mathbf{x} = \mathbf{b}_J$ has $\mathbf{v}$ as its only solution, so $P_J = \{\mathbf{v}\}$ , and Proposition 22.3.1 makes that a face.

Proof.

(a) $\Leftrightarrow$ (c) is Theorem 18.9.2.
(b) $\Rightarrow$ (a). Write $\{\mathbf{v}\} = \{\mathbf{x} \in P : \mathbf{c}^{\top}\mathbf{x} = \beta\}$ with $\mathbf{c}^{\top}\mathbf{x} \le \beta$ on $P$ . By Proposition 18.8.4 (b), applied with $\mathbf{w} = \mathbf{c}$ and $\alpha = \beta$ , $\mathbf{v} \in \operatorname{ext} P$ .
(c) $\Rightarrow$ (b). Let $I = I(\mathbf{v})$ be the active set and $\mathbf{A}_I$ the matrix of active rows, of rank $n$ by hypothesis. Its null space is $\{\mathbf{0}\}$ by Theorem 3.5.7, so $\mathbf{A}_I\mathbf{x} = \mathbf{b}_I$ has at most one solution; since $\mathbf{v}$ is one, it is the only one. Hence $P_I = \{\mathbf{x} \in P : \mathbf{A}_I\mathbf{x} = \mathbf{b}_I\} = \{\mathbf{v}\} ,$ and $P_I$ is a face by Proposition 22.3.1 (a). This proves the equivalence.

So a corner of a polyhedron can be recognized three ways: by convexity (it is not an average), by geometry (a hyperplane touches $P$ there and nowhere else), or by algebra (enough constraints are tight). The three are used interchangeably from here on.

Bounded polyhedra are the ones with enough corners to rebuild them. This is the bounded half of the Minkowski–Weyl theorem, and it is the sentence this whole section is arranged around.

Theorem 22.3.3 (A Bounded Polyhedron Is the Hull of Its Vertices)

Let $P \subseteq \mathbb{R}^n$ be a bounded polyhedron. Then $\operatorname{ext} P$ is finite and $P = \operatorname{conv}(\operatorname{ext} P) .$ Conversely, every polytope is a bounded polyhedron.

Proof. If $P = \emptyset$ , both sides are $\emptyset$ and $\operatorname{ext}P = \emptyset$ . Otherwise $P$ is closed and convex by Proposition 18.9.1, and bounded by hypothesis, so it is compact by Corollary 16.2.5. By Theorem 18.8.5, $P = \operatorname{conv}(\operatorname{ext} P)$ , and $\operatorname{ext} P$ is finite by Corollary 18.9.3. The converse is Theorem 18.9.5 (a).

The same theorem applied to a face is what makes an edge a segment between two corners — the statement that lets one speak of walking along the edges of a solid.

Proposition 22.3.4 (An Edge Joins Two Vertices)

Let $P \subseteq \mathbb{R}^n$ be a bounded polyhedron and $F$ an edge of $P$ . Then $F = [\mathbf{v}, \mathbf{w}]$ for two distinct vertices $\mathbf{v}, \mathbf{w}$ of $P$ .

Idea. An edge is itself a bounded polyhedron, so it is the hull of its own vertices; those are vertices of $P$ because a face passes extremeness upwards. Being $1$ -dimensional, it sits on a line, and the hull of finitely many points of a line is the segment between the outermost two.

Proof. By Proposition 22.3.1, $F$ is a polyhedron, and it is bounded because $F \subseteq P$ . By Theorem 22.3.3, $F = \operatorname{conv}(\operatorname{ext} F)$ with $\operatorname{ext} F$ finite, and $F \ne \emptyset$ since it has a dimension. By the remark after Definition 22.3.1, $F$ is a face of $P$ in the sense of Definition 18.8.2, so Lemma 18.8.3 gives $\operatorname{ext} F = F \cap \operatorname{ext} P$ : every vertex of $F$ is a vertex of $P$ .

Fix $\mathbf{p} \in F$ . By Proposition 18.1.4, $\operatorname{aff} F = \mathbf{p} + U$ with $U = \operatorname{span}\{\mathbf{x} - \mathbf{p} : \mathbf{x} \in F\}$ , and $\dim U = \dim F = 1$ , so $U = \operatorname{span}(\mathbf{u})$ for some $\mathbf{u} \ne \mathbf{0}$ . Every point of $F$ lies in $\operatorname{aff}F$ , hence is $\mathbf{p} + t\mathbf{u}$ for exactly one $t \in \mathbb{R}$ , the map $t \mapsto \mathbf{p} + t\mathbf{u}$ being injective because $\mathbf{u} \ne \mathbf{0}$ . Let $t_1 \le \dots \le t_k$ be the parameters of the points of $\operatorname{ext} F$ , a non-empty finite list. A convex combination $\sum_j s_j(\mathbf{p} + t_j\mathbf{u})$ equals $\mathbf{p} + (\sum_j s_jt_j)\mathbf{u}$ , and $\sum_j s_jt_j$ lies in $[t_1, t_k]$ ; conversely each $t \in [t_1, t_k]$ is $(1-\lambda)t_1 + \lambda t_k$ for some $\lambda \in [0,1]$ . Hence, writing $[\mathbf{v}, \mathbf{w}]$ for the segment of Chapter 18 §01, $F = \{\mathbf{p} + t\mathbf{u} : t_1 \le t \le t_k\} = [\mathbf{v}, \mathbf{w}], \qquad \mathbf{v} = \mathbf{p} + t_1\mathbf{u},\ \ \mathbf{w} = \mathbf{p} + t_k\mathbf{u} .$ If $t_1 = t_k$ then $F$ is a single point and $\dim F = 0$ , contrary to hypothesis; so $\mathbf{v} \ne \mathbf{w}$ , and both are vertices of $P$ . This proves the proposition.

22.3.3. Two face lattices, computed

Faces are ordered by inclusion, and the resulting picture — which face lies in which — is the face lattice of the polyhedron. It is the combinatorial skeleton of the solid. Here it is in full for the two standard examples.

Example (The faces of a cube)

Let $B_\infty = [-1, 1]^n$ , described by the $2n$ rows $\mathbf{e}_i^{\top}\mathbf{x} \le 1$ and $-\mathbf{e}_i^{\top}\mathbf{x} \le 1$ . Find all faces of $B_\infty$ and their dimensions.

Solution. By Proposition 22.3.1 (b) every non-empty face is some $P_J$ . A set $J$ of rows says, for each coordinate $i$ , either nothing, or $x_i = 1$ , or $x_i = -1$ , or both; the last makes $P_J = \emptyset$ . So the non-empty faces are indexed by sign vectors $\mathbf{s} \in \{-1, 0, 1\}^n$ : $F_{\mathbf{s}} = \{\mathbf{x} \in B_\infty : x_i = s_i \text{ for every } i \text{ with } s_i \ne 0\} .$ Each $F_{\mathbf{s}}$ is non-empty: the point with $x_i = s_i$ where $s_i \ne 0$ and $x_i = 0$ elsewhere lies in it. Distinct sign vectors give distinct faces, because $s_i = \pm 1$ exactly when the coordinate $x_i$ is constantly $\pm 1$ on $F_{\mathbf{s}}$ . So $B_\infty$ has exactly $3^n$ non-empty faces, one for each sign vector, together with $\emptyset$ .

Let $Z = \{i : s_i = 0\}$ and $z = \lvert Z\rvert$ . Then $\operatorname{aff} F_{\mathbf{s}}$ is the flat $\{\mathbf{x} : x_i = s_i \text{ for } i \notin Z\}$ , a coset of $\operatorname{span}\{\mathbf{e}_i : i \in Z\}$ : it contains $F_{\mathbf{s}}$ , and conversely $F_{\mathbf{s}}$ contains the point $\mathbf{p}$ with $p_i = s_i$ for $i \notin Z$ and $p_i = 0$ for $i \in Z$ , together with $\mathbf{p} + \mathbf{e}_i$ for every $i \in Z$ , whose differences from $\mathbf{p}$ span $\operatorname{span}\{\mathbf{e}_i : i \in Z\}$ . By Proposition 18.1.4, $\dim F_{\mathbf{s}} = z$ .

So the faces of dimension $k$ are the sign vectors with exactly $k$ zeros, and there are $\binom{n}{k}2^{n-k}$ of them. For $n = 3$ : $8$ vertices ( $k = 0$ ), $12$ edges ( $k = 1$ ), $6$ facets ( $k = 2$ ) and the cube itself, and $8 + 12 + 6 + 1 = 27 = 3^3$ . Every vertex is a sign vector $\pm 1$ in each coordinate, matching what Example (The cube and the cross-polytope) found by the rank test.

Here is the resulting lattice for the square $B_\infty \subseteq \mathbb{R}^2$ , with $\emptyset$ at the bottom and the square at the top, and a line drawn when the lower face is contained in the upper one.

$Diagram. Labels: (-1,-1), (1,-1), (-1,1), (1,1), x_2 = -1, x_1 = -1, x_1 = 1, x_2 = 1, B_infty, The face lattice of the square: one empty face, four vertices,\\ four edges, and the square itself. Nine non-empty faces, 3^2$

Example (The faces of a simplex)

Let $\Delta_n = \{\mathbf{t} \in \mathbb{R}^n : t_i \ge 0,\ \sum_i t_i = 1\}$ be the standard simplex (Definition 18.1.2), described by the $n$ rows $-t_i \le 0$ together with $\mathbf{1}^{\top}\mathbf{t} \le 1$ and $-\mathbf{1}^{\top}\mathbf{t} \le -1$ . Find all faces of $\Delta_n$ .

Solution. The last two rows are tight at every point of $\Delta_n$ , so including them in $J$ changes nothing. A face is therefore $P_J$ for $J$ determined by a set $S \subseteq \{1, \dots, n\}$ of coordinates forced to zero: $F_S = \{\mathbf{t} \in \Delta_n : t_i = 0 \text{ for every } i \in S\} .$ Write $T = \{1, \dots, n\} \setminus S$ . If $T = \emptyset$ the conditions $\mathbf{t} = \mathbf{0}$ and $\sum_i t_i = 1$ clash, so $F_S = \emptyset$ . If $T \ne \emptyset$ , then $F_S$ consists of the vectors $\mathbf{t} \ge \mathbf{0}$ supported in $T$ with $\sum_{i \in T}t_i = 1$ , which by Theorem 18.1.3 is exactly $\operatorname{conv}\{\mathbf{e}_i : i \in T\}$ , a copy of $\Delta_{\lvert T\rvert}$ . Its dimension is $\lvert T\rvert - 1$ , by the computation of $\dim\Delta_k$ after Proposition 18.1.4. Distinct non-empty $T$ give distinct faces, since $\mathbf{e}_i \in F_S$ exactly for $i \in T$ .

So the non-empty faces of $\Delta_n$ are indexed by the non-empty subsets $T \subseteq \{1, \dots, n\}$ , and there are $2^n - 1$ of them: $n$ vertices, $\binom n2$ edges, and so on up to $\Delta_n$ itself. For $n = 4$ , the tetrahedron $\Delta_4 \subseteq \mathbb{R}^4$ of dimension $3$ has $4 + 6 + 4 + 1 = 15 = 2^4 - 1$ non-empty faces.

The contrast is the point. The cube’s lattice is the set of sign vectors; that of the simplex is the set of non-empty subsets. A cube in dimension $n$ has $2^n$ vertices and $2n$ facets; a simplex has $n$ vertices and $n$ facets. The cube’s corners grow exponentially with $n$ , those of the simplex only linearly.

Quick check. How many faces does a triangle in $\mathbb{R}^2$ have, counting the empty face and the triangle itself?

Solution. Eight: $\emptyset$ , three vertices, three edges, and the triangle. Count directly from Proposition 22.3.1 (b), writing the triangle as the polyhedron cut out by its three sides: $P_{\emptyset}$ is the triangle, each single row gives one side, each pair of rows gives the corner where those two sides meet, and all three rows together give $\emptyset$ . That is $1 + 3 + 3$ non-empty faces, plus $\emptyset$ . The count matches Example (The faces of a simplex) with $n = 3$ , whose $2^3 - 1 = 7$ non-empty faces are indexed by the non-empty subsets of the three corners.

22.3.4. A linear program, seen

Fix $\mathbf{c} \in \mathbb{R}^n$ with $\mathbf{c} \ne \mathbf{0}$ . The level sets $\{\mathbf{x} : \mathbf{c}^{\top}\mathbf{x} = \gamma\}$ of the objective are parallel affine hyperplanes, one for each $\gamma$ , and they sweep across $\mathbb{R}^n$ as $\gamma$ grows, moving in the direction $\mathbf{c}$ . Maximizing $\mathbf{c}^{\top}\mathbf{x}$ over a polyhedron $P$ means pushing the sweeping hyperplane as far as it will go while still touching $P$ . Two things can happen: it escapes to infinity, and the program is unbounded; or there is a last hyperplane that touches, and what it touches is a face.

Proposition 22.3.5 (The Optimal Set Is a Face)

Let $P \subseteq \mathbb{R}^n$ be a polyhedron, $\mathbf{c} \in \mathbb{R}^n$ , and suppose $\mathbf{c}^{\top}\mathbf{x}$ attains a maximum $\gamma^{\star}$ on $P$ . Then the set $F^{\star}$ of maximizers is a non-empty face of $P$ . If $P$ is bounded, $F^{\star}$ contains a vertex of $P$ .

Proof. By the definition of a maximum, $\mathbf{c}^{\top}\mathbf{x} \le \gamma^{\star}$ for every $\mathbf{x} \in P$ , and $F^{\star} = \{\mathbf{x} \in P : \mathbf{c}^{\top}\mathbf{x} = \gamma^{\star}\}$ is non-empty. That is Definition 22.3.1 verbatim, so $F^{\star}$ is a face.

Suppose $P$ is bounded. Then $F^{\star} \subseteq P$ is a bounded polyhedron by Proposition 22.3.1, and non-empty, so $\operatorname{ext} F^{\star} \ne \emptyset$ by Theorem 22.3.3 (a non-empty set is not the hull of the empty set). By the remark after Definition 22.3.1 and Lemma 18.8.3, $\operatorname{ext} F^{\star} = F^{\star} \cap \operatorname{ext} P$ , so any point of $\operatorname{ext} F^{\star}$ is a vertex of $P$ lying in $F^{\star}$ .

The last sentence is Corollary 18.8.6 read geometrically, and it says a little more than that corollary: not only is some maximizer a vertex, but the whole set of maximizers is a face — a single vertex when the optimum is unique, and otherwise an edge or a larger face, up to all of $P$ when $\mathbf{c} = \mathbf{0}$ . A linear program with a non-unique optimum has a positive-dimensional optimal face, and every point of it is optimal.

An algorithm now suggests itself: start at a vertex, and as long as some edge leaving it increases the objective, walk along that edge to the vertex at its other end (Proposition 22.3.4 guarantees there is one, when $P$ is bounded). That is the idea of the simplex method, sketched in Chapter 18 §09 after Corollary 18.9.3. No algorithm is developed here or anywhere in this book: Chapter 24 is where this book’s algorithms live, and it treats the numerical linear algebra of elimination, least squares and eigenvalues, not linear programming. What this section supplies is the geometry an algorithm would exploit.

Example (A linear program and its picture)

Maximize $3x_1 + 2x_2$ over $P = \{\mathbf{x} \in \mathbb{R}^2 : x_1 \ge 0,\ x_2 \ge 0,\ x_1 + x_2 \le 5,\ 2x_1 + x_2 \le 8\} .$ Find the vertices, the optimum, the optimal face, and the dual optimal solution.

Solution. Number the rows (1) $-x_1 \le 0$ , (2) $-x_2 \le 0$ , (3) $x_1 + x_2 \le 5$ , (4) $2x_1 + x_2 \le 8$ . No two rows are multiples of each other, so each of the $\binom42 = 6$ pairs gives one basic point, which we test against the other two rows: $\begin{array}{c|c|l} \text{pair} & \text{basic point} & \text{verdict} \\ \hline (1),(2) & (0, 0) & \text{feasible} \\ (1),(3) & (0, 5) & (4)\colon 5 \le 8 \text{: feasible} \\ (1),(4) & (0, 8) & (3)\colon 8 \le 5 \text{ fails} \\ (2),(3) & (5, 0) & (4)\colon 10 \le 8 \text{ fails} \\ (2),(4) & (4, 0) & (3)\colon 4 \le 5 \text{: feasible} \\ (3),(4) & (3, 2) & \text{feasible} \end{array}$ For the last pair, subtracting (3) from (4) gives $x_1 = 3$ , hence $x_2 = 2$ . By Proposition 22.3.2 the vertices are $(0,0)$ , $(0,5)$ , $(4,0)$ and $(3,2)$ . $P$ is bounded, since $0 \le x_1, x_2 \le 5$ on it, so by Theorem 22.3.3 it is the quadrilateral $\operatorname{conv}\{(0,0), (4,0), (3,2), (0,5)\}$ .

The objective takes the value $0$ at $(0,0)$ , $10$ at $(0,5)$ , $12$ at $(4,0)$ and $13$ at $(3,2)$ , so by Proposition 22.3.5 the maximum is $13$ , at $\mathbf{x}^{\star} = (3,2)$ , and the optimal face is $\{\mathbf{x} \in P : 3x_1 + 2x_2 = 13\}$ . Since only one vertex achieves $13$ and the face is the hull of its vertices, the optimal face is the single point $\{(3,2)\}$ : the optimum is unique.

The rows active at $\mathbf{x}^{\star}$ are (3) and (4), with outer normals $\mathbf{a}_3 = (1,1)$ and $\mathbf{a}_4 = (2,1)$ . And $\mathbf{c} = (3, 2) = 1\cdot(1,1) + 1\cdot(2,1) = 1\cdot\mathbf{a}_3 + 1\cdot\mathbf{a}_4 ,$ so $\mathbf{y} = (1, 1)$ is a candidate for the dual. In the notation of Definition 18.6.2, with $\mathbf{A}$ the rows $(1,1)$ and $(2,1)$ and $\mathbf{b} = (5, 8)$ , the dual asks to minimize $5y_1 + 8y_2$ subject to $y_1 + 2y_2 \ge 3$ , $y_1 + y_2 \ge 2$ , $\mathbf{y} \ge \mathbf{0}$ . At $\mathbf{y} = (1,1)$ both constraints are equalities and the value is $5 + 8 = 13$ , which matches. By Corollary 18.6.2 (a), $\mathbf{x}^{\star}$ and $\mathbf{y}$ are both optimal, and no further checking is needed.

$Diagram. Labels: x_1, x_2, mathbf a_4, mathbf c, mathbf a_3, x_1 + x_2 = 5, 2x_1 + x_2 = 8, 3x_1 + 2x_2 = 13, mathbf x^star, The feasible quadrilateral, the level line of the objective through\\ the optimum, and the two active outer normals whose non-negative\\ combination is mathbf c = mathbf a_3 + mathbf a_4$

22.3.5. What the dual variables are, geometrically

The example ended with an identity worth isolating: the objective vector was a non-negative combination of the outer normals of the constraints active at the optimum, and the coefficients were the dual optimal solution. That is the geometric content of duality, and Chapter 18 has already done all the work.

Recall Chapter 18 §06’s pair of programs, with $\mathbf{A} \in M_{m\times n}(\mathbb{R})$ , $\mathbf{b} \in \mathbb{R}^m$ , $\mathbf{c} \in \mathbb{R}^n$ : $\begin{aligned} \text{(P)}\quad &\text{maximize } \mathbf{c}^{\top}\mathbf{x} \ \text{ subject to } \mathbf{A}\mathbf{x} \le \mathbf{b},\ \mathbf{x} \ge \mathbf{0} ; \\ \text{(D)}\quad &\text{minimize } \mathbf{b}^{\top}\mathbf{y} \ \text{ subject to } \mathbf{A}^{\top}\mathbf{y} \ge \mathbf{c},\ \mathbf{y} \ge \mathbf{0} . \end{aligned}$ The feasible region of (P) is the polyhedron with the $m$ rows $\mathbf{a}_i^{\top}\mathbf{x} \le b_i$ and the $n$ rows $(-\mathbf{e}_j)^{\top}\mathbf{x} \le 0$ . The outer normal of a row is the vector on its left-hand side: $\mathbf{a}_i$ for the $i$ -th constraint and $-\mathbf{e}_j$ for the sign constraint on $x_j$ .

Proposition 22.3.6 (Dual Variables Are the Weights of the Active Normals)

Let $\mathbf{x}^{\star}$ be an optimal solution of (P). Then there are $\mathbf{y} \in \mathbb{R}^m$ and $\mathbf{s} \in \mathbb{R}^n$ with $\mathbf{y} \ge \mathbf{0}$ and $\mathbf{s} \ge \mathbf{0}$ such that $\mathbf{c} = \sum_{i=1}^{m} y_i\mathbf{a}_i + \sum_{j=1}^{n} s_j(-\mathbf{e}_j) ,$ where $y_i = 0$ whenever $\mathbf{a}_i^{\top}\mathbf{x}^{\star} < b_i$ , and $s_j = 0$ whenever $x^{\star}_j > 0$ . That is, $\mathbf{c}$ is a non-negative combination of the outer normals of the constraints active at $\mathbf{x}^{\star}$ , and the weights are an optimal solution of (D).

Idea. Strong duality hands over an optimal $\mathbf{y}$ for (D); the slack $\mathbf{s} = \mathbf{A}^{\top}\mathbf{y} - \mathbf{c}$ is non-negative because $\mathbf{y}$ is dual feasible, and rearranging is the displayed identity. Complementary slackness is exactly the statement that the weights vanish on the inactive constraints.

Proof. Since $\mathbf{x}^{\star}$ is feasible, (P) is feasible, and $\mathbf{c}^{\top}\mathbf{x} \le \mathbf{c}^{\top}\mathbf{x}^{\star}$ for every feasible $\mathbf{x}$ , so (P) is not unbounded. By Theorem 18.6.3 (b), (D) is therefore feasible, and by Theorem 18.6.3 (a) both programs have optimal solutions with equal optimal values; let $\mathbf{y}$ be an optimal solution of (D). Then $\mathbf{y} \ge \mathbf{0}$ and $\mathbf{A}^{\top}\mathbf{y} \ge \mathbf{c}$ , so $\mathbf{s} \mathrel{:=} \mathbf{A}^{\top}\mathbf{y} - \mathbf{c} \ge \mathbf{0}$ . Reading the $j$ -th coordinate of $\mathbf{A}^{\top}\mathbf{y}$ as $\sum_i y_ia_{ij}$ , we get $\mathbf{A}^{\top}\mathbf{y} = \sum_i y_i\mathbf{a}_i$ , and hence $\mathbf{c} = \mathbf{A}^{\top}\mathbf{y} - \mathbf{s} = \sum_{i=1}^{m}y_i\mathbf{a}_i + \sum_{j=1}^{n}s_j(-\mathbf{e}_j) .$ Both $\mathbf{x}^{\star}$ and $\mathbf{y}$ are optimal, so Theorem 18.6.5 applies: its condition (i) says $y_i > 0$ forces $(\mathbf{A}\mathbf{x}^{\star})_i = b_i$ , which is the contrapositive of “ $\mathbf{a}_i^{\top}\mathbf{x}^{\star} < b_i$ forces $y_i = 0$ ”; its condition (ii) says $x^{\star}_j > 0$ forces $(\mathbf{A}^{\top}\mathbf{y})_j = c_j$ , that is $s_j = 0$ . This proves the proposition.

So a dual optimal solution is a certificate written in normals. The hyperplane $\{\mathbf{x} : \mathbf{c}^{\top}\mathbf{x} = \mathbf{b}^{\top}\mathbf{y}\}$ supports the feasible region at $\mathbf{x}^{\star}$ , by Theorem 18.6.1 and equality of the optimal values, and Proposition 22.3.6 says how its normal $\mathbf{c}$ is assembled from the normals of the facets meeting at $\mathbf{x}^{\star}$ . Increasing $b_i$ loosens the $i$ -th constraint, and $y_i$ bounds the gain: the dual feasible region $\{\mathbf{y} \ge \mathbf{0} : \mathbf{A}^{\top}\mathbf{y} \ge \mathbf{c}\}$ does not mention $\mathbf{b}$ at all, so $\mathbf{y}$ stays dual feasible when $b_i$ is raised to $b_i + \varepsilon$ , and Theorem 18.6.1 then caps the objective of every point feasible for the loosened program at $\mathbf{b}^{\top}\mathbf{y} + \varepsilon y_i$ , the old optimal value plus $\varepsilon y_i$ . That $y_i$ is also the exact rate of gain, its shadow price in the economists’ phrase, says more, and this book does not prove it; nothing here uses it, and it can fail. Take $n = 1$ , $m = 2$ , $\mathbf{A} = \begin{psmallmatrix} 1 \\ 1\end{psmallmatrix}$ , $\mathbf{b} = (1,1)$ and $\mathbf{c} = 1$ , so that (P) maximizes $x$ subject to $x \le 1$ written twice and $x \ge 0$ . Its optimum is $1$ , and $\mathbf{y} = (1,0)$ is dual feasible with $\mathbf{b}^{\top}\mathbf{y} = 1$ , hence dual optimal by Corollary 18.6.2 (a); but raising $b_1$ leaves the second copy binding and the optimum at $1$ , a gain of $0$ against $y_1 = 1$ . The same pair shows which half of complementary slackness is available: Theorem 18.6.5 (i) says $y_i > 0$ forces row $i$ tight, so a constraint slack at the optimum has $y_i = 0$ , and that is what Proposition 22.3.6 records. The converse is the trap — here $y_2 = 0$ while row $2$ is tight.

22.3.6. Polyhedra without corners

Boundedness is doing real work in Theorem 22.3.3, and the failures are worth seeing.

Example (A slab, and a quadrant)

(a) Find the faces of the slab $S = \{\mathbf{x} \in \mathbb{R}^3 : 0 \le x_3 \le 1\}$ , and its vertices.
(b) Show that $\max\{x_1 + x_2 : \mathbf{x} \in Q\}$ does not exist for the quadrant $Q = \{\mathbf{x} \in \mathbb{R}^2 : x_1 \ge 0,\ x_2 \ge 0\}$ , although $Q$ has a vertex.

Solution.

(a) $S$ has the two rows $-x_3 \le 0$ and $x_3 \le 1$ . By Proposition 22.3.1 the non-empty faces are among $P_\emptyset = S$ , $P_{\{1\}} = \{x_3 = 0\}$ , $P_{\{2\}} = \{x_3 = 1\}$ and $P_{\{1,2\}} = \emptyset$ . So there are three non-empty faces: $S$ and two parallel planes, of dimensions $3$ , $2$ , $2$ . There is no face of dimension $0$ or $1$ . In particular $S$ has no vertices: at any $\mathbf{x} \in S$ the active rows are among $\pm\mathbf{e}_3$ , of rank at most $1 < 3$ , so Theorem 18.9.2 denies a vertex. Hence $\operatorname{conv}(\operatorname{ext}S) = \operatorname{conv}\emptyset = \emptyset \ne S$ , and Theorem 18.8.5 indeed needs compactness. Note also that $\max\{-x_3 : \mathbf{x} \in S\} = 0$ is attained, on the whole face $\{x_3 = 0\}$ , which contains no vertex: the last sentence of Proposition 22.3.5 needs boundedness too.
(b) The point $(0,0)$ is a vertex of $Q$ : the two active rows $-\mathbf{e}_1, -\mathbf{e}_2$ are independent, so Theorem 18.9.2 applies. It is the only one, since at any other point of $Q$ at most one row is active. But $(t, t) \in Q$ for every $t \ge 0$ and $x_1 + x_2 = 2t$ there, so the objective is unbounded above and no maximum exists. A polyhedron can have corners and still have no optimum.

Warning. “Vertex” and “corner of the picture” can both be empty words for an unbounded polyhedron. The slab above is a perfectly ordinary convex solid, closed, with a genuine boundary, and it has no vertices, no edges, and no bounded face. Nothing in this section rebuilds it from finitely many points, and nothing should: by Theorem 18.9.5 (a) a polyhedron is a polytope exactly when it is bounded. The general finite description of an unbounded polyhedron needs directions as well as points — every non-empty polyhedron is a polytope plus a finitely generated cone — which Chapter 18 derives from Theorem 18.9.5 (b) in Exercise (C1: Unbounded polyhedra), and which is not pursued here.

22.3.7. Exercises

A. Check your understanding

Exercise (A1)

(a) State Definition 22.3.1, and say which pair $(\mathbf{c}, \beta)$ exhibits $P$ itself as a face and which exhibits $\emptyset$ .
(b) True or false: a polyhedron given by $m$ inequalities in $\mathbb{R}^n$ has exactly $2^m$ non-empty faces. Justify your answer.
(c) Give the three equivalent descriptions of a vertex from Proposition 22.3.2.
(d) True or false: if a linear program over a bounded non-empty polyhedron has two distinct optimal solutions, it has infinitely many. Justify your answer.
(e) How many faces of dimension $2$ does the cube $[-1,1]^4$ have?

Solution.

(a) A face of a polyhedron $P$ is a set $\{\mathbf{x} \in P : \mathbf{c}^{\top}\mathbf{x} = \beta\}$ for some $\mathbf{c}, \beta$ with $\mathbf{c}^{\top}\mathbf{x} \le \beta$ valid on all of $P$ . The pair $(\mathbf{0}, 0)$ gives $F = P$ ; the pair $(\mathbf{0}, 1)$ gives $F = \emptyset$ .
(b) False; $2^m$ is only an upper bound (Proposition 22.3.1 (c)). The map $J \mapsto P_J$ need not be injective, and some $P_J$ may be empty. The warning after that proposition has $m = 3$ rows in $\mathbb{R}^2$ and only four non-empty faces: the polyhedron, two edges and one vertex.
(c) $\mathbf{v} \in P$ is a vertex when: it is an extreme point of $P$ ; or $\{\mathbf{v}\}$ is a face of $P$ ; or among the rows active at $\mathbf{v}$ there are $n$ linearly independent ones.
(d) True. The optimal set is a face (Proposition 22.3.5), hence convex, so it contains the whole segment joining the two optimal points, and a segment with distinct ends has infinitely many points.
(e) By Example (The faces of a cube) with $n = 4$ , $k = 2$ : $\binom42 2^{4-2} = 6\cdot 4 = 24$ .

B. Practice

Exercise (B1: Vertices and faces of a region)

Let $P = \{\mathbf{x} \in \mathbb{R}^2 : x_1 \ge 0,\ x_2 \ge 0,\ x_1 + 2x_2 \le 8,\ 2x_1 + x_2 \le 10\} .$ Find all vertices of $P$ , list all of its faces, and maximize $x_1 + 3x_2$ over $P$ .

Solution. Number the rows (1) $-x_1 \le 0$ , (2) $-x_2 \le 0$ , (3) $x_1 + 2x_2 \le 8$ , (4) $2x_1 + x_2 \le 10$ . No two are multiples, so each of the six pairs gives a basic point: $\begin{array}{c|c|l} \text{pair} & \text{point} & \text{verdict} \\ \hline (1),(2) & (0,0) & \text{feasible} \\ (1),(3) & (0,4) & (4)\colon 4 \le 10 \text{: feasible} \\ (1),(4) & (0,10) & (3)\colon 20 \le 8 \text{ fails} \\ (2),(3) & (8,0) & (4)\colon 16 \le 10 \text{ fails} \\ (2),(4) & (5,0) & (3)\colon 5 \le 8 \text{: feasible} \\ (3),(4) & (4,2) & \text{feasible} \end{array}$ For the last pair, twice (3) minus (4) gives $3x_2 = 6$ , so $x_2 = 2$ and $x_1 = 8 - 4 = 4$ . By Proposition 22.3.2 the vertices are $(0,0)$ , $(0,4)$ , $(5,0)$ and $(4,2)$ , so $P$ is a quadrilateral, not a pentagon; two of the six basic points are infeasible. $P$ is bounded ( $0 \le x_1 \le 5$ , $0 \le x_2 \le 4$ on it), so $P = \operatorname{conv}\{(0,0), (5,0), (4,2), (0,4)\}$ by Theorem 22.3.3.

By Proposition 22.3.1 (b) every non-empty face is some $P_J$ . The four singletons give the four edges, computed directly: $P_{\{1\}} = \{x_1 = 0,\ 0 \le x_2 \le 4\}$ ; $P_{\{2\}} = \{x_2 = 0,\ 0 \le x_1 \le 5\}$ ; $P_{\{3\}} = \{x_1 + 2x_2 = 8\} \cap P$ , where $x_1 = 8 - 2x_2 \ge 0$ gives $x_2 \le 4$ and $2x_1 + x_2 = 16 - 3x_2 \le 10$ gives $x_2 \ge 2$ , a segment from $(4,2)$ to $(0,4)$ ; and $P_{\{4\}} = \{2x_1 + x_2 = 10\} \cap P$ , which in the same way is the segment from $(4,2)$ to $(5,0)$ . The six pairs give $P_{\{1,2\}} = \{(0,0)\}$ , $P_{\{1,3\}} = \{(0,4)\}$ , $P_{\{2,4\}} = \{(5,0)\}$ , $P_{\{3,4\}} = \{(4,2)\}$ , and $P_{\{1,4\}} = P_{\{2,3\}} = \emptyset$ , the two infeasible basic points; every $J$ with three or more rows gives $\emptyset$ , since no point of $P$ has three rows active. So $P$ has ten faces in all: $\emptyset$ , four vertices, four edges and $P$ itself.

The objective $x_1 + 3x_2$ takes the values $0$ , $5$ , $10$ , $12$ at $(0,0)$ , $(5,0)$ , $(4,2)$ , $(0,4)$ . By Proposition 22.3.5 the maximum is $12$ , attained at $(0,4)$ alone.

Exercise (B2: Reading the dual off the normals)

For the program of Exercise (B1: Vertices and faces of a region) with objective $x_1 + 3x_2$ , use Proposition 22.3.6 to write $\mathbf{c} = (1,3)$ as a non-negative combination of the outer normals of the constraints active at the optimum, and check the resulting dual solution against Corollary 18.6.2.

Solution. The optimum is $\mathbf{x}^{\star} = (0,4)$ . The active rows there are (1), with outer normal $-\mathbf{e}_1 = (-1, 0)$ , and (3), with outer normal $\mathbf{a}_3 = (1,2)$ . In the notation of Definition 18.6.2 the rows of $\mathbf{A}$ are (3) and (4) in that order, so the weight on $\mathbf{a}_3$ is $y_1$ . Writing $\mathbf{c} = y_1\mathbf{a}_3 + s_1(-\mathbf{e}_1)$ with $\mathbf{a}_3 = (1,2)$ : $(1,3) = y_1(1,2) + s_1(-1, 0)$ gives $2y_1 = 3$ , so $y_1 = \tfrac32$ , and $1 = \tfrac32 - s_1$ , so $s_1 = \tfrac12$ . Both are non-negative, as Proposition 22.3.6 requires. Row (4) is inactive at $\mathbf{x}^{\star}$ , so its weight is $y_2 = 0$ ; and $x^{\star}_2 = 4 > 0$ , so the slack on the second sign constraint is $s_2 = 0$ .

So $\mathbf{A}$ has rows $(1,2)$ and $(2,1)$ , with $\mathbf{b} = (8, 10)$ and $\mathbf{c} = (1,3)$ . The dual solution read off is $\mathbf{y} = (\tfrac32, 0)$ , which satisfies $\mathbf{y} \ge \mathbf{0}$ and $\mathbf{A}^{\top}\mathbf{y} = \tfrac32(1,2) = \bigl(\tfrac32, 3\bigr) \ge (1,3) = \mathbf{c} ,$ so it is dual feasible, with value $\mathbf{b}^{\top}\mathbf{y} = 8\cdot\tfrac32 = 12$ . Since the primal value at $(0,4)$ is also $12$ , Corollary 18.6.2 (a) confirms that both are optimal.

Exercise (B3: Faces of the cross-polytope)

Let $B_1 = \{\mathbf{x} \in \mathbb{R}^n : \mathbf{s}^{\top}\mathbf{x} \le 1 \text{ for every sign vector } \mathbf{s} \in \{-1,1\}^n\}$ , the cross-polytope of Example (The cube and the cross-polytope). Determine the face $P_J$ for $J$ a single sign vector $\mathbf{s}$ , and its dimension. How many facets does $B_1$ have?

Solution. For a single sign vector $\mathbf{s}$ , $P_{\{\mathbf{s}\}} = \{\mathbf{x} \in B_1 : \mathbf{s}^{\top}\mathbf{x} = 1\}$ . Now $\mathbf{s}^{\top}\mathbf{x} = \sum_i s_ix_i \le \sum_i\lvert x_i\rvert = \left\| \mathbf{x} \right\|_1$ , term by term, so equality holds exactly when $s_ix_i = \lvert x_i\rvert$ for every $i$ ; and $\left\| \mathbf{x} \right\|_1 = \max_{\mathbf{s}}\mathbf{s}^{\top}\mathbf{x} \le 1$ on $B_1$ , as Example (The cube and the cross-polytope) records. So $\mathbf{s}^{\top}\mathbf{x} = 1$ forces $\left\| \mathbf{x} \right\|_1 = 1$ and $s_ix_i = \lvert x_i\rvert \ge 0$ for every $i$ ; conversely those conditions give $\mathbf{s}^{\top}\mathbf{x} = \left\| \mathbf{x} \right\|_1 = 1$ . Writing $\mathbf{x} = \sum_i x_i\mathbf{e}_i$ with $x_i = s_i\lvert x_i\rvert$ , we get $P_{\{\mathbf{s}\}} = \Bigl\{\sum_i t_i(s_i\mathbf{e}_i) : t_i \ge 0,\ \sum_i t_i = 1\Bigr\} = \operatorname{conv}\{s_1\mathbf{e}_1, \dots, s_n\mathbf{e}_n\} ,$ using Theorem 18.1.3. This is a copy of $\Delta_n$ , of dimension $n - 1$ by the computation after Proposition 18.1.4. Since $\dim B_1 = n$ — it contains $\mathbf{0}$ and every $\pm\mathbf{e}_i$ , and the differences $\mathbf{e}_i - \mathbf{0}$ span $\mathbb{R}^n$ , so Proposition 18.1.4 gives $\operatorname{aff}B_1 = \mathbb{R}^n$ — each $P_{\{\mathbf{s}\}}$ is a facet. Distinct $\mathbf{s}$ give distinct facets, since $\mathbf{s}$ is recovered from $P_{\{\mathbf{s}\}}$ by the signs of the vertices $s_i\mathbf{e}_i$ .

There are no others. Every non-empty face is $P_J$ for a set $J$ of sign vectors, by Proposition 22.3.1 (b), and if $\mathbf{s} \ne \mathbf{s}'$ both lie in $J$ then $P_J \subseteq P_{\{\mathbf{s}\}} \cap P_{\{\mathbf{s}'\}}$ . A point of that intersection has $x_i = s_i\lvert x_i\rvert = s'_i\lvert x_i\rvert$ , so $x_i = 0$ whenever $s_i \ne s'_i$ ; hence the intersection is $\operatorname{conv}\{s_i\mathbf{e}_i : s_i = s'_i\}$ , of dimension at most $n - 2$ , since at least one index is missing. So $B_1$ has exactly $2^n$ facets: in $\mathbb{R}^n$ it has $2n$ vertices and $2^n$ facets, exactly the reverse of the cube.

C. Going deeper

Exercise (C1: A face of a face)

Let $P$ be a polyhedron and $F$ a face of $P$ .

(a) Prove that every face of $F$ is a face of $P$ .
(b) Deduce that the faces of $P$ contained in a fixed face $F$ are exactly the faces of $F$ .

Hint: for (a), use Proposition 22.3.1 to write both $F$ and the face of $F$ in the form $P_J$ .

Solution.

(a) We may assume the face $G$ of $F$ is non-empty, since $\emptyset$ is a face of $P$ . Fix a system $\mathbf{A}\mathbf{x} \le \mathbf{b}$ with $P = \{\mathbf{x} : \mathbf{A}\mathbf{x} \le \mathbf{b}\}$ and rows $\mathbf{a}_i^{\top}\mathbf{x} \le b_i$ , $i = 1, \dots, m$ . By Proposition 22.3.1 (b), $F = P_J$ for some $J$ . By part (a) of the same proposition, $F$ is cut out by the $m$ original rows together with the rows $-\mathbf{a}_i^{\top}\mathbf{x} \le -b_i$ for $i \in J$ . By (b) applied to $F$ with this system, $G = F_K$ for some set $K$ of those rows; since the rows $-\mathbf{a}_i^{\top}\mathbf{x} \le -b_i$ with $i \in J$ are tight everywhere on $F$ , including them in $K$ changes nothing, so we may take $K \subseteq \{1, \dots, m\}$ . Then $G = \{\mathbf{x} \in F : \mathbf{a}_i^{\top}\mathbf{x} = b_i \text{ for } i \in K\} = \{\mathbf{x} \in P : \mathbf{a}_i^{\top}\mathbf{x} = b_i \text{ for } i \in J \cup K\} = P_{J \cup K} ,$ which is a face of $P$ by Proposition 22.3.1 (a).
(b) By (a), every face of $F$ is a face of $P$ , and it is contained in $F$ . Conversely let $G$ be a face of $P$ with $G \subseteq F$ , say $G = \{\mathbf{x} \in P : \mathbf{c}^{\top}\mathbf{x} = \beta\}$ with $\mathbf{c}^{\top}\mathbf{x} \le \beta$ on $P$ . Then $\mathbf{c}^{\top}\mathbf{x} \le \beta$ holds in particular on $F \subseteq P$ , and $\{\mathbf{x} \in F : \mathbf{c}^{\top}\mathbf{x} = \beta\} = \{\mathbf{x} \in P : \mathbf{c}^{\top}\mathbf{x} = \beta\} \cap F = G \cap F = G ,$ so $G$ is a face of $F$ .

Exercise (C2: The two notions of face agree for a polyhedron)

Let $P = \{\mathbf{x} \in \mathbb{R}^n : \mathbf{A}\mathbf{x} \le \mathbf{b}\}$ and let $F \subseteq P$ be a non-empty face in the sense of Definition 18.8.2: $F$ is convex, and whenever $t\mathbf{y} + (1-t)\mathbf{z} \in F$ with $\mathbf{y}, \mathbf{z} \in P$ and $0 < t < 1$ , both $\mathbf{y}$ and $\mathbf{z}$ lie in $F$ .

(a) Let $J = \{i : \mathbf{a}_i^{\top}\mathbf{x} = b_i \text{ for every } \mathbf{x} \in F\}$ . Prove that $F = P_J$ .
(b) Deduce that $F$ is a face in the sense of Definition 22.3.1, so the two notions agree for polyhedra.

Hint: for (a), Step 1 of the proof of Proposition 22.3.1 produces a point of $F$ at which every row outside $J$ is slack; use it as the midpoint of a short segment.

Solution.

(a) $F \subseteq P_J$ by the definition of $J$ . For the reverse inclusion, note first that $F$ is convex, so Step 1 of the proof of Proposition 22.3.1 applies verbatim and yields $\mathbf{x}^{*} \in F$ with $\mathbf{a}_i^{\top}\mathbf{x}^{*} < b_i$ for every $i \notin J$ .
Let $\mathbf{y} \in P_J$ . If $\mathbf{y} = \mathbf{x}^{*}$ we are done, so assume $\mathbf{y} \ne \mathbf{x}^{*}$ and put $\mathbf{z}_t = \mathbf{x}^{*} + t(\mathbf{x}^{*} - \mathbf{y})$ for $t > 0$ . Exactly as in Step 2 of that proof, $\mathbf{a}_i^{\top}\mathbf{z}_t = b_i$ for $i \in J$ and, for small enough $t > 0$ , $\mathbf{a}_i^{\top}\mathbf{z}_t < b_i$ for $i \notin J$ ; so $\mathbf{z}_t \in P$ . Fix such a $t$ . Then $\mathbf{x}^{*} = \frac{t}{1+t}\,\mathbf{y} + \frac{1}{1+t}\,\mathbf{z}_t ,$ a combination with positive coefficients adding to $1$ : indeed the right side is $\frac{t\mathbf{y} + \mathbf{x}^{*} + t\mathbf{x}^{*} - t\mathbf{y}}{1+t} = \mathbf{x}^{*}$ . Both $\mathbf{y}$ and $\mathbf{z}_t$ lie in $P$ and $\mathbf{x}^{*} \in F$ , so the face property of Definition 18.8.2 forces $\mathbf{y} \in F$ . Hence $P_J \subseteq F$ and $F = P_J$ .
(b) By Proposition 22.3.1 (a), $P_J$ is a face in the sense of Definition 22.3.1. Together with the remark after Definition 22.3.1, which gives the other direction for every face, the two notions coincide on polyhedra.

They do not coincide for general convex sets, and one round set shows it. Let $D = \{\mathbf{x} \in \mathbb{R}^2 : \left\| \mathbf{x} \right\| \le 1\}$ , let $\mathbf{q} = (2,0)$ , let $C = \operatorname{conv}(D \cup \{\mathbf{q}\})$ , and put $\mathbf{p} = \bigl(\tfrac12, \tfrac{\sqrt3}{2}\bigr)$ , so that $\left\| \mathbf{p} \right\| = 1$ and $\langle \mathbf{p}, \mathbf{q} \rangle = 1$ . Since $D$ is convex, Theorem 18.1.3 writes every point of $C$ as $(1-s)\mathbf{d} + s\mathbf{q}$ with $\mathbf{d} \in D$ and $s \in [0,1]$ , whence $\langle \mathbf{p}, (1-s)\mathbf{d} + s\mathbf{q} \rangle = (1-s)\langle \mathbf{p}, \mathbf{d} \rangle + s \le (1-s)\left\| \mathbf{d} \right\| + s \le 1 ,$ the first inequality by Theorem 11.1.5. Equality with $s < 1$ forces $\langle \mathbf{p}, \mathbf{d} \rangle = \left\| \mathbf{d} \right\| = 1$ , hence $(\mathbf{p}, \mathbf{d})$ dependent and $\mathbf{d} = \mathbf{p}$ ; so $\{\mathbf{x} \in C : \langle \mathbf{p}, \mathbf{x} \rangle = 1\} = [\mathbf{p}, \mathbf{q}]$ . Now $\{\mathbf{p}\}$ is a face of $C$ in the sense of Definition 18.8.2: if $\mathbf{p} = t\mathbf{y} + (1-t)\mathbf{z}$ with $\mathbf{y}, \mathbf{z} \in C$ and $0 < t < 1$ , then $1 = t\langle \mathbf{p}, \mathbf{y} \rangle + (1-t)\langle \mathbf{p}, \mathbf{z} \rangle$ , and both inner products are at most $1$ , so both equal $1$ and $\mathbf{y} = \mathbf{p} + a(\mathbf{q} - \mathbf{p})$ , $\mathbf{z} = \mathbf{p} + b(\mathbf{q} - \mathbf{p})$ with $a, b \in [0,1]$ ; then $ta + (1-t)b = 0$ forces $a = b = 0$ . But no supporting hyperplane isolates $\mathbf{p}$ . If $\langle \mathbf{c}, \mathbf{x} \rangle \le \beta$ on $C$ with $\langle \mathbf{c}, \mathbf{p} \rangle = \beta$ , then $\mathbf{c} \ne \mathbf{0}$ , since $\mathbf{c} = \mathbf{0}$ gives the face $C$ or $\emptyset$ ; testing the inequality at the point $\mathbf{c}/\left\| \mathbf{c} \right\|$ of $D$ gives $\left\| \mathbf{c} \right\| \le \beta = \langle \mathbf{c}, \mathbf{p} \rangle \le \left\| \mathbf{c} \right\|$ , so equality holds in Theorem 11.1.5 and $\mathbf{c} = \left\| \mathbf{c} \right\|\mathbf{p}$ , $\beta = \left\| \mathbf{c} \right\|$ . Then $\langle \mathbf{c}, \mathbf{q} \rangle = \left\| \mathbf{c} \right\|\langle \mathbf{p}, \mathbf{q} \rangle = \beta$ , so $\mathbf{q}$ lies in the face too, and the face is not $\{\mathbf{p}\}$ .

Exercise (C3: The optimal face has no better vertex outside it)

Let $P \subseteq \mathbb{R}^n$ be a non-empty bounded polyhedron, $\mathbf{c} \in \mathbb{R}^n$ , and let $F^{\star}$ be the optimal face of Proposition 22.3.5.

(a) Prove that $F^{\star} = \operatorname{conv}(F^{\star} \cap \operatorname{ext} P)$ .
(b) Deduce that the optimal value of the program equals $\max\{\mathbf{c}^{\top}\mathbf{v} : \mathbf{v} \in \operatorname{ext}P\}$ , a maximum over a finite set, and that this finite maximum is attained exactly at the vertices lying in $F^{\star}$ .

Solution.

(a) $F^{\star}$ is a non-empty bounded polyhedron by Proposition 22.3.1, so Theorem 22.3.3 gives $F^{\star} = \operatorname{conv}(\operatorname{ext}F^{\star})$ . By the remark after Definition 22.3.1, $F^{\star}$ is a face of $P$ in the sense of Definition 18.8.2, so Lemma 18.8.3 gives $\operatorname{ext}F^{\star} = F^{\star} \cap \operatorname{ext}P$ . Substituting proves (a).
(b) By Corollary 18.9.3, $\operatorname{ext}P$ is finite, and it is non-empty by Theorem 22.3.3 since $P \ne \emptyset$ . Write $\gamma^{\star}$ for the optimal value. Every vertex lies in $P$ , so $\mathbf{c}^{\top}\mathbf{v} \le \gamma^{\star}$ for $\mathbf{v} \in \operatorname{ext}P$ ; and by (a) $F^{\star}$ contains a vertex, at which $\mathbf{c}^{\top}\mathbf{v} = \gamma^{\star}$ . So the finite maximum equals $\gamma^{\star}$ . A vertex $\mathbf{v}$ attains it exactly when $\mathbf{c}^{\top}\mathbf{v} = \gamma^{\star}$ , which is exactly the condition $\mathbf{v} \in F^{\star}$ defining the optimal face.

22.3.1. Faces, cut by a supporting hyperplane

22.3.2. Vertices, edges, facets

22.3.3. Two face lattices, computed

22.3.4. A linear program, seen

22.3.5. What the dual variables are, geometrically

22.3.6. Polyhedra without corners

22.3.7. Exercises

A. Check your understanding

B. Practice

C. Going deeper