enter image description here


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?


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.


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.
  • $\begingroup$ how do you conclude that $\frac{ \lambda - 1 }{\lambda} x < 0$ ? Also, what is $x$ in the first line where you assumed $x_2 \neq x$? $\endgroup$ – James Sep 15 '18 at 21:45
  • $\begingroup$ those are unfortunately typos. sorry about those. $\endgroup$ – Siong Thye Goh Sep 16 '18 at 1:33
  • $\begingroup$ Im trying to find the extreme directions. I found out that the zero vector is the only extreme direction. Is this correct?? $\endgroup$ – James Sep 17 '18 at 3:50
  • $\begingroup$ not really, for example $e_1$, the vector with the first entry $1$ and the rest $0$ is an extreme direction. can you verify and find the other directions? $\endgroup$ – Siong Thye Goh Sep 17 '18 at 5:21
  • $\begingroup$ I think I got it! The direction vector are the canonical vectors $\endgroup$ – James Sep 17 '18 at 5:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.