Show that $S=\{\mathbf x \in \mathbb R^n:\mathbf A \mathbf x=\mathbf b,\mathbf x \ge \mathbf 0\} \ne \emptyset$ has at least one extreme point

Question

Show that the standard polyhedron defined by $S=\{\mathbf x \in \mathbb R^n:\mathbf A \mathbf x=\mathbf b,\mathbf x \ge \mathbf 0\} \ne \emptyset $ has at least one extreme point and the set of its extreme points is a finite set.

---

I know that we need to find $\mathbf x \in S$ such that $$\forall \mathbf A,\mathbf B \in S, \forall \lambda \in (0,1):\mathbf x= \lambda \mathbf A+(1-\lambda)\mathbf B \implies \mathbf A=\mathbf B$$

And that shows that the set has at least one extreme point, I can find such $\mathbf x$ but unfortunately it depends on $\mathbf A$ and so it does not work for arbitrary $\mathbf A,\mathbf B \in S$.

I've seen the theorem in many sources, but could not find any proof of that.

Answer 1

We prove the result in two steps. First, we show that if the column vectors of $A$ associated with positive elements of $x$ are linearly independent, $x$ is an extreme point. Second, we use this result to show that there exists an extreme point.

Let $x=(x_1,\ldots,x_r,0,\ldots,0)$ with $x_i>0$ and let $a^1,\ldots,a^r$ be the corresponding column vectors of $A$ Assume that $a^1,\ldots,a^r$ are linearly independent. We show that $x$ is an extreme point.

Case 1: $r=0$. In this case $x=0$. Let $y,z\in S$ and $0=x=\lambda y + (1-\lambda) z$ with $\lambda \in (0,1)$. As $y,z \geq 0$, it follows directly $x=y=z=0$.

Case 2: $r>0$. It holds $\sum\limits_{i=1}^ra^ix_i=b$. Let $y,z\in S$ and $x=\lambda y + (1-\lambda) z$ with $\lambda \in (0,1)$. As $y,z \geq 0$, it follows $y_i=z_i=0$ for $i>r$. Moreover, as $y,z \in S$ we have $Ay=Az=b$, it follows $$A(y-z)=\sum_{i=1}^r a^i(y_i-z_i)=0.$$ As $a^1,\ldots,a^r$ are linearly independent, it follows $y=z$. Thus, $x$ is an extreme point.

Now the second step. Define by $r(x)$ the number of positive entries $x_i>0$ in $x \in S$. Define $z\in S$ by $r(z)=\min\{r(x):x\in S\}$. We show that $z$ is an extreme point. If $r(z)=0$, then $z=0$. Thus, an extreme point. Assume that $r(z)>0$. We show that $a^1,\ldots, a^{r(z)}$ are linearly independent. Assume to the contrary $a^1,\ldots, a^{r(z)}$ is linearly dependent. Then there exists $d_1,\ldots,d_{r(z)}\neq 0$ such that $$\sum_{i=1}^{r(z)}a^i d_i =0.$$ Define $$\mu:=\min\{\frac{z_i}{|d_i|}:d_i\neq 0\}=\frac{z_k}{|d_k|}>0$$ for some $k$. Without loss assume $d_k>0$. Define $$d=(d_1,\ldots,d_{r(z)},0,\ldots,0) \in \mathbb{R}^n$$ and $y=z-\mu d$. Due to $Ad=0$, it follows, $Ay=Az-\mu Ad =Az =b$. Therefore, $y\in S$. It holds, $$y_i=z_i-\frac{z_k}{d_k}d_i\geq 0$$ by definition of $\mu$. Moreover it holds, $$y_k=z_k-\frac{z_k}{d_k}d_k=0.$$ Thus, $r(y)<r(z)$, which is a contradiction. Thus, $a^1,\ldots, a^{r(z)}$ are linearly independent and $z$ an extreme point.

Answer 2

I think that I can prove the existence at least one extreme point if $A$ is a $n \times n$ matrix.
Proof:
I will do the proof by induction.
Case $n=1$:
If $A$ is not singular and $S \neq \emptyset$ then $S=\{a\}$ (consecuence of Rouche-Frobeniu´s theorem) for some $a \in \mathbb{R}$ and then $S$ has one extreme point. If $A$ is singular then $S=\mathbb{R}^{+} \cup \{0\}$ and then $\{0\}$ is the extreme point.
Case general:n=k
If $A$ is not singular and $S \neq \emptyset$ then $S=\{a\}$ (consecuence of Rouche-Frobeniu´s theorem) for some $a \in \mathbb{R}^{n}$ and then $S$ has one extreme point.
If $A$ is singular and $S \neq \emptyset$ then we have that $S=(a+V) \cap \{x \geq 0\}$ for some $a \in \mathbb{R}^{n}$ and a subespace $V \subseteq \mathbb{R}^{n}$.
How $A$ is singular, then exists $v=(v_{1},...,v_{n}) \in V : v \neq 0$ so exists $j \in \{1,...,n\} : v_{j} \neq 0$, and we can suppose that some index is negative (doing $\cdot (-1)$).
Then rearranging if necessary we can suppose that $a=(a_{1},...,a_{n})$, $v=(v_{1},...,v_{n})$ and $v_{n} < 0$ and $\frac{|v_{n}|}{|a_{n}|} \leq \frac{|v_{j}|}{|a_{j}|} \forall j \in \{1,...,n\}$.
Then we have that $a+\frac{v_{n}}{a_{n}}v=(a_{1}+\frac{v_{1}v_{n}}{a_{n}},...,a_{n-1}+\frac{v_{n-1}v_{n}}{a_{n}},0)$ and $a_{i}+\frac{v_{i}v_{n}}{a_{n}} \geq 0$ with $i \in \{1,...,n-1\}$, so $a+\frac{v_{n}}{a_{n}}v \in S$.
But $S \subseteq \{x \geq 0\}$ so if $a+\frac{v_{n}}{a_{n}}v=\lambda c + (1-\lambda) d$ with $\lambda \in (0,1)$ and $c,d \in S$ then $c_{n}=d_{n}=0$.
So $a+\frac{v_{n}}{a_{n}}v,c,d$ are solutions of the sistem:
$$ \begin{pmatrix} a_{11}& \cdots & a_{1n} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn} \\ \end{pmatrix} \begin{pmatrix} x_{1} \\ \vdots \\ x_{n-1}\\ 0 \end{pmatrix} = \begin{pmatrix} b_{1} \\ \vdots \\ b_{n} \end{pmatrix} $$ and how $x_{n}=0$ we can delete the last column of our matrix and our solutions are solutions of the sistem: $$ \begin{pmatrix} a_{11}& \cdots & a_{1n-1} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn-1} \\ \end{pmatrix} \begin{pmatrix} x_{1} \\ \vdots \\ x_{n-1} \end{pmatrix} = \begin{pmatrix} b_{1} \\ \vdots \\ b_{n} \end{pmatrix} $$ we denote $$A'= \begin{pmatrix} a_{11}& \cdots & a_{1n-1} \\ \vdots & \ddots & \vdots \\ a_{n1} & \cdots & a_{nn-1} \\ \end{pmatrix}, X'= \begin{pmatrix} x_{1}\\ \vdots\\ x_{n-1} \end{pmatrix}, B= \begin{pmatrix} b_{1}\\ \vdots\\ b_{n} \end{pmatrix} $$ then we have that $rg(A') \leq n-1$, and how $a+\frac{v_{n}}{a_{n}}v$ is solution of $A'X'=B$ we have that $rg(A')=rg(A'|B) \leq n-1$, so we can delete one row of $A'$ and $B$. We can suppose that we delete the $n$-row.
So our sistem is equivalent to the sistem: $$ \begin{pmatrix} a_{11}& \cdots & a_{1n-1} \\ \vdots & \ddots & \vdots \\ a_{n-11} & \cdots & a_{n-1n-1} \\ \end{pmatrix} \begin{pmatrix} x_{1} \\ \vdots \\ x_{n-1} \end{pmatrix} = \begin{pmatrix} b_{1} \\ \vdots \\ b_{n-1} \end{pmatrix} $$ and by induction hipotesis we have that this last sistem restricted to $\{x' \geq 0\}$ has at least one extreme point.

Answer 3

First, I prove existence of an extreme value:
Let $C$ be the set of points $\mathbf x \in \mathbb R^n$ that have norm $1$ and satisfy the equation $$\mathbf A \mathbf x = k\mathbf b.$$ for some real number $k$. This is closed because it is the inverse of a closed set ($\{\mathbf b\}$) under a continuous function ($\mathbf A$). By definition, $C$ is bounded. So, $C$ is compact. Then, by the Extreme Value Theorem, there exists a unique $\mathbf x_0 \in C$ that maximizes $\|\mathbf x\|$. Then the vector $$\frac{\|\mathbf b\|\mathbf x_0}{\|\mathbf x_0\|}$$ is an extreme value of $S$.

I now show that this value is unique:
If $|S| = 1$, this is obvious. Otherwise, $S$ contains some line. Then $S$ has no element with maximum norm. So, I only need to show that the minimum vector is unique. If $\mathbf b = 0$, then $\mathbf 0$ obviously is the unique element of $S$ with minimum norm. So, assume that $\mathbf b \ne 0$.

Suppose that $\mathbf x \in S$ and $\mathbf y \in S$ both have minimum norms. Then $\|\mathbf x\| = \|\mathbf y\|$. Consider the point $(\mathbf x + \mathbf y) / 2.$ This point is in $S$. Notice that $$\left\|\frac{\mathbf x + \mathbf y}{2}\right\|^2 = \frac14(\|\mathbf x\|^2 + \|\mathbf y\|^2 + 2\mathbf x \cdot \mathbf y) \le \frac14(\|\mathbf x\|^2 + \|\mathbf y\|^2 + 2\|\mathbf x\|\|\mathbf y\|) = \frac14(\|\mathbf x\| + \|\mathbf y\|)^2$$ by the Cauchy-Schwartz inequality. Equality occurs only when $\mathbf x$ is a multiple of $\mathbf y$. Taking square roots on both sides, $$\left\|\frac{\mathbf x + \mathbf y}{2}\right\| \le \frac12(\|\mathbf x \| + \|\mathbf y\|) = \|\mathbf x\|$$ with equality only when $\mathbf x$ is a multiple of $\mathbf y$. But we must have equality, because $\mathbf x$ has the minimum norm in all of $S$. So, $\mathbf x = k\mathbf y$ for some $k \in \mathbb R$. But because $$\mathbf b = \mathbf A \mathbf x = \mathbf A (k\mathbf y) = k\mathbf A \mathbf y = k\mathbf b,$$ $k = 1$. Thus, $\mathbf x = \mathbf y$, as desired.

Answer 4

Here's another approach, which is less quantitative and more geometric/combinatorial.

We can write $S = \{x^T : x(A^T,I) \leq (\mathbf{1},\mathbf{0})\}$ by adding the $d$ constraints $x_i \geqslant 0$ and normalizing the rows of $A$ by their inner product with $x$.

We prove this by induction on the number of rows of the constraint matrix. Consider $A$ a $(n+1) \times d$ matrix, and let $A'$ be $A$ without the first row. By induction, $S' = \{x^T : x((A')^T, I) \leqslant (\mathbf{1},\mathbf{0})\}$ has a finite nonempty set of extreme points, say of size $N$.

An extreme point of a polyhedron is found at the intersection of $d$ constraints, so $S$ has at most $N + {n \choose d}$ extreme points. Moreover, the set of extreme points of $S$ is nonempty, as there is some extreme point of $S$ which is in the (nonempty!) extreme point set of $S''$, where $S''$ removes a different constraint from $S$ than $S'$. Induction completes the proof.

Answer 5

Consider a lexicographic ordering $≺$ on $ℝ^n$, e.g. $x≺y$ if and only if $x_1 < y_1$ or $(x_1 = y_1) ∧ (x_2 < y_2)$, etc.

Claim: $z = \displaystyle\min_{≺} S$ exists, is unique and an extremal point.

Proof:

• existence: $z = \min_{x_n}(\min_{x_{n-1}}(… \min_{x_1}(S)))$, each of these minima exists since the set is always a convex and the objective function is bounded below.
• uniqueness: because $x⪯y$ and $y⪯x$ if and only if $x=y$.
• extremality: Assume $z = (1-λ)a + λb$ for some $a, b∈S$, $λ∈(0,1)$ then by construction $z_1 ≤ a_1, b_1$. But since $z_1 = (1-λ)a_1 + λb_1$ the only solution is $a_1 = b_1 = z_1$, etc.