Let $S=\{x:x_1+2x_2\le 4\}$.
Find the extreme points and directions of S.
Can you represent any point in $S$ as a convex combination of its extreme points
plus a nonnegative linear combination of its extreme directions?
This is what I've done:
I draw the region S and I saw that there was no extreme points. Then I took a particular point of S and check again that was not an extreme point.
So I could conclude that S has no extreme points. I actually tried to prove formally that S has no extreme points (but I got stuck as usually..)
However the question in the exercise made think that I might be wrong because it mention the existence of extreme points as a convex combination..
My question does it really has extreme points?
Best Answer
Define the Euclidean metric on $S$. Note that for every point of $S$ like $(x_1,x_2)$ such that $x_1+2x_2\le 4$ there exist two points $(x_1+2,x_2-1)$ and $(x_1-2,x_2+1)$ both belonging to $S$ (since $[x_1+2]+2[x_2-1]=x_1+2x_2\le 4$ and $[x_1-2]+2[x_2+1]=x_1+2x_2\le 4$). Since $S$ is convex then whole the line connecting these 2 points belongs to $S$. Now note that $$(x_1,x_2)=\dfrac{1}{2}(x_1-2,x_2+1)+\dfrac{1}{2}(x_1+2,x_2-1)$$which implies that $(x_1,x_2)$ is in the middle of that line and therefore is not an extreme point. Also refer to the following illusion for feasible directions: