This blog is talking about the when there exists extreme points. The key idea of solving LP problem is optimal solution will be at basic feasible solution. But, some polyhedron have no extreme point. This blog will introduce how to tell a polyhedron processes at least one extreme point.
Definition: A polyhedron ${ P \subset \mathbb{R}^n }$ contains a line if there exists a vector ${ \bar{x} \in P }$ and a nonzero vector ${ \bar{d} \in \mathbb{R}^n }$ such that ${ \bar{x} + \lambda \bar{d} \in P }$ for all scalars ${ \lambda \in \mathbb{R} }$.
Theorem: For a nonempty polyhedron ${ P = \{ \bar{x} \in \mathbb{R}^n \mid \bar{a}^\top \bar{x} \geq \bar{b}, i=1,2,\cdots,m \} }$, the following assertions are equivalent:
-
${ P }$ has at least one extreme point.
-
${ P }$ contains no line.
-
${ \text{span } \{ \bar{a}_1, \bar{a}_2, \cdots, \bar{a}_m \} = \mathbb{R}^n }$ (In other words, one can find $n$ linear independent vectors in the family ${\{ \bar{a}_1,\bar{a}_2,\cdots,\bar{a}_m\}}$).
Proof.
- (2) $\Rightarrow$ (1)
Now, we know $P$ does not contain a line. Since $P$ is not empty, we can pick a point $\bar{p} \in P$. Let ${I_{\bar{p}} = \{ i \mid \bar{a}_i^{\top} \bar{p} \geq b_i \}}$ be the set of indices of constraints active at $\bar{p}$. Since $\bar{a}_1, \bar{a}_2, …, \bar{a}_m \in \mathbb{R}^n$, we have ${\text{dim span}\{\bar{a}_i \mid i \in I_{\bar{p}}\} \leq n}$. If $\text{dim span}{\bar{a}_i \mid i \in I_{\bar{p}}} = n$, then $\bar{p}$ is, by definition, a basic feasible solution and hence an extreme point of $P$.
On the other hand, if ${\text{dim span}\{\bar{a}_i \mid i \in I_{\bar{p}}\} < n}$, then ${\text{span}\{\bar{a}_i \mid i \in I_{\bar{p}}\}}$ is a proper subspace of $\mathbb{R}^n$ and we can choose a nonzero vector $\bar{d}$ orthogonal to ${\text{span}\{\bar{a}_i \mid i \in I_{\bar{p}}\}}$. Consider the line consisting of all points of the form $\bar{y} = \bar{p} + \lambda \bar{d}$ for all $\lambda \in \mathbb{R}$. For all $i \in I_{\bar{p}}$, we have
\[\bar{a}_i^{\top}\bar{y} = \bar{a}_i^{\top}(\bar{p} + \lambda \bar{d}) = \bar{a}_i^{\top}\bar{p} + \lambda \bar{a}_i^{\top}\bar{d} = \bar{a}_i^{\top}\bar{p} = b_i\]Thus those constraints that were active at $\bar{p}$ remain active at all points on the line. However, since the polyhedron $P$ contains no lines, as we vary $\lambda$, some constraint $\bar{a}_j^{\top}\bar{y} \geq b_j$ with $j \not\in I_{\bar{p}}$ will eventually be violated.
At the point where that constraint is about to be violated, that constraint will become active. Thus there exists some $\lambda^* \in \mathbb{R}$ and some $j \not\in I_{\bar{p}}$ such that
\[\bar{a}_j^{\top}(\bar{p} + \lambda^* \bar{d}) = b_j\]Note that $I_{\bar{p}} \subsetneq I_{\bar{p}+\lambda^*\bar{d}}$ and $j \in I_{\bar{p}+\lambda^*\bar{d}} \setminus I_{\bar{p}}$. Thus, we have
\[\bar{a}_j^{\top} \bar{p} \neq b_j \text{ (because } j \not\in I_{\bar{p}})\] \[\bar{a}_j^{\top}(\bar{p} + \lambda^* \bar{d}) = b_j\]The above two formulae imply that $\bar{a}_j^\top \bar{d} \neq 0$. And, we have ${\bar{d} \in (\text{span}\{\bar{a}_i \mid i \in I_{\bar{p}}\})^\perp \iff \bar{a}_i^{\top} \bar{d} = 0}$ for all $i \in I_{\bar{p}}$. Hence, we know $\bar{a}_j$ is not a linear combination of $\bar{a}_i, i\in I_{\bar{p}}$, that is ${\bar{a}_j \notin \text{span} \{\bar{a}_i \mid i \in I_{\bar{p}}\}}$.
Thus, by moving from $\bar{p}$ to $\bar{p} + \lambda^* \bar{d}$, the number of linearly independent active constraints has been increased by (at least) one.
Case 1: If ${\text{dim span}\{\bar{a}_i \mid i \in I_{\bar{p}+\lambda^*\bar{d}}\} = n}$, then $\bar{p} + \lambda^* \bar{d}$ is an extreme point of the polyhedron $P$.
Case 2: If not, then ${\text{dim span}\{\bar{a}_i \mid i \in I_{\bar{p}+\lambda^*\bar{d}}\} < n}$ and we can repeat the same argument starting from $\bar{q} = \bar{p} + \lambda^* \bar{d}$ rather than $\bar{p}$.
By repeating the same argument as many times as needed, we eventually end up with a point at which there are $n$ linearly independent active constraints. Such a point is, by definition, a basic solution; it is also basic feasible solution since we always stay within the feasible set. Then, we have found an extreme point by theorem of the polyhedron!
- (1) $\Rightarrow$ (3)
We know $x_0$ is an extreme point of $P$, then by theorem $x_0$ is a basic feasible solution of $P$. By definition, ${\text{dim span}\{\bar{a}_i \mid i \in I_{x_0}\} = n}$, which means we can find $n$ linearly independent vectors among the vectors $\bar{a}_i,i \in I_{x_0}$. So, we have
\[\mathbb{R}^n = \text{span}\{\bar{a}_i \mid i \in I_{x_0}\} \subseteq \text{span}\{\bar{a}_1, \bar{a}_2, ..., \bar{a}_n\} \subseteq \mathbb{R}^n\]Therefore, we have ${\text{span}\{\bar{a}_1, \bar{a}_2, …, \bar{a}_n\} = \mathbb{R}^n}$.
- (3) $\Rightarrow$ (2)
Suppose $P$ contains a line ${\{\bar{p}+\lambda \bar{d} \mid \lambda \in \mathbb{R} \}}$ (with $\bar{d} \neq \bar{0}$). Since $\bar{p} + \lambda \bar{d} \in P, \forall \lambda \in \mathbb{R}$, we have
\[\bar{a}_i^{\top} (\bar{p} + \lambda \bar{d}) \geq b_i, \forall \lambda \in \mathbb{R}, \forall i \in \{1,2,...,m\}\] \[(\bar{a}_i^{\top} \bar{p} - b_i) + \bar{a}_i^{\top} \bar{d} \cdot \lambda \geq 0, \forall \lambda \in \mathbb{R}, \forall i \in \{1,2,...,m\}\]We know $(\bar{a}_i^{\top} \bar{p} - b_i), \bar{a}_i^{\top} \bar{d}$ are both constants, so if $f(\lambda) \geq 0, \forall \lambda \in \mathbb{R}$, that implies ${\bar{a}_i^{\top} \bar{d} = 0, \forall i \in \{1,2,…,m\}}$. Thus, we have ${\bar{d} \in (\text{span}\{\bar{a}_1, \bar{a}_2, …, \bar{a}_n\})^\perp, \bar{d} \neq {0} }$. Therefore, ${\text{span}\{\bar{a}_1, \bar{a}_2, …, \bar{a}_n\}}$ is a proper subspace of $\mathbb{R}^n$, which contradicts to ${ \text{span } \{ \bar{a}_1, \bar{a}_2, \cdots, \bar{a}_m \} = \mathbb{R}^n }$. $\square$
Corollary:
(1) Every nonempty bounded polyhedron has at least one basic feasible solution / extreme point.
(2) Every nonempty polyhedron in standard form has at least one basic feasible solution / extreme point. (Because polyhedron in standard form contains no line.)
Proof. Bounded polyhedron $P$ implies containing no line. Then by above theorem, we know $P$ has at least one basic feasible solution / extreme point. Similarly, we know polyhedron in standard form contains no line, which leads to that $P$ has at least one basic feasible solution / extreme point. $\square$