An extreme point of a polyhedron is a vertex.

Question

I have run into a problem relative to linear progamming. This problem is about extreme point and vetices of a polyheron. The question is that an extreme point and a vertex of a polyhedron is equivalent. I guess the answer is yes and I have proved a vertex is an extreme point. However, I have difficulty in proving an extreme point is a vertex.

I know one way to prove is using basic feasible solutions but my lecturer asked to prove not using that convention.

The definition of an extreme point of a polyheron is

Let $P$ be a polyhedron. A vector $x \in P$ is an extreme point of $P$ if we cannot find two vectors $y, z \in P$, both different from $x$, and a scalar $\lambda \in [0,1]$, such that $x=\lambda y +(1-\lambda) z$.

For a vertex, this following definition is know

Let $P$ be a polyhedron. A vector $x \in P$ is a vertex of $P$ of there exists some $c$ such that $c'x < c'y$ for all $y$ satisfying $y \in P$ and $y \neq x$.

Both two definitions come from the book "Introduction to Linear Optimization" by Dimistris Bertsimas.

Any help would be greatly appreciated.

Answer 1

For these kinds of problems, the geometry should guide you. There is an answer below, but first consider the following hint:

The definition of a vertex says that we can find a $c$ so that the entire polytope is in the strict half space defined by $c$, and $x$ alone is in the hyperplane defined by $c$. So if $x$ is not a vertex, we can find a $c$ and $y,z \in P$ so that $y$ and $z$ not $x$ are on parallel hyperplanes normal to $c$, with $x$ sandwiched between them. Draw a picture. Does this give you information about $x$ with respect to $y$ and $z$?

Below is a solution.

---

Suppose that $x$ is not a vertex. Then there is no such $c$; in particular, there are $x \neq y,z \in P$ and $0 \neq c \in \mathbb{R}^n$ so that $c^Tx < c^Ty$ and $c^Tx \geqslant c^Tz$. I claim this implies that $x \in \text{conv}(y,z)$.

Notice that $c^Tx$ is in $[c^Ty, c^Tz] \subset \mathbb{R}$. Then there is some $\lambda \geqslant 0$ so that:

$$\lambda c^Ty + (1-\lambda)c^Tz = c^Tx$$

By multilinearity of the dot product (alternatively, properties of matrix multiplication):

\begin{align*} \lambda c^Ty + (1-\lambda)c^Tz = c^Tx &\Longrightarrow c^T(\lambda y) + c^T ((1-\lambda)z) = c^T x\\ &\Longrightarrow c^T(\lambda y + (1-\lambda)z) = c^T x \end{align*}

Since $c \neq 0$, this implies $\lambda y + (1-\lambda)z = x$ for $y,z\neq x$ in $P$, so $x$ is not an extreme point.

Hence if $x$ is an extreme point, $x$ is a vertex.