Showing a point in a polyhedron is an extreme point

Question

Attempt

Suppose $x_1 \neq x_2$ are two points in $P$ such that $0 = \lambda x_1 + (1- \lambda) x_2$ for $\lambda \in (0,1)$. IF we make $\lambda = 1/2$ then we see that $0 = \frac{1}{2} x_1 + \frac{1}{2} x_2 \implies x_1+x_2= 0$. this implies that either $x_1$ or $x_2$ is negative meaning they are not in $P$ and this is a contradiction. Hence, $x=0$ is an extreme point.

Now, as for b) given an $x $ in $P$ with $x \neq 0$, we wish to find vectors $x_1,x_2$ so that we can write $x = \lambda x_1 + (1- \lambda) x_2 $ where $\lambda \in (0,1)$. Notice we can write $x$ as $x = \frac{1}{2} (3x) + \frac{1}{2} (-x)$ and so here we have a convex combination of $x$. IS this a valid approach?

As for c), what are extreme directions?

'Update:

c) finding extreme directions of $P$ is the same as finding extreme points of the set $D = \{ {\bf d} : \sum_{j=1}^n d_j = 1, d_j \geq 0 \}$. Now, we prove that the canonical vectors are the extreme points of $D$. Indeed, assume ${\bf e_j} = \lambda {\bf x_1} + (1 - \lambda) {\bf x_2}$ where ${\bf x_1, x_2} \in D$ and $0<\lambda<1$. Assume that both ${\bf x_1}$ and ${\bf x_1}$ are nonzero basis vectors which means that all their components are strictly less than $1$. In particular, the jth component of them $x_1^{(j)}$ and $x_2^{(j)}$ are strictly less than $1$ and therefore $x_1^{(j)}+x_2^{(j)} < 2$. Now, since ${\bf e_j} = \lambda {\bf x_1} + (1 - \lambda) {\bf x_2}$, we have that $1 = \lambda x_1^{(j)}+ (1-\lambda) x_2^{(j)}$. Put $\lambda = \frac{1}{2}$ which gives $1 = \frac{1}{2}(x_1^{(j)}+x_2^{(j)})$ and so $x_1^{(j)}+x_2^{(j)} =2 $, a contradiction. The result now follows.

Answer 1

For part $(a)$, suppose $x_1 \ne 0$ and $x_2 \ne 0,$ where $ x_1, x_2 \in P$, and $0 = \lambda x_1 + (1-\lambda )x_2$ for some $\lambda \in (0,1)$.

then $$x_1 = \frac{\lambda -1}{\lambda}x_2$$

Since $x_2 \ne 0$, there is a component $x_{2i} >0$, but for the corresponding entry in $x_1$, we have $x_{1i}=\frac{\lambda -1}{\lambda}x_{2i} < 0$ which contradicts that $x_1 \in P$. Notice that I didn't set $\lambda = \frac12$.

For part $(b)$, for your approach, notice that $-x \not \in P$.

We have $$x = \frac12 (2x) + \frac12(0).$$

Now for definition of extreme direction.

• Given a convex set, a nonzero vector $d$ is a direction of the set if for each $x_0$ in the set, the ray $\{x_0 +\lambda d:\lambda \ge 0\}$ also belongs to the set.
• An extreme direction of a convex set is a direction of the set that cannot be represented as a positive combination of two distinct directions of the set.