convex optimizationconvex-analysisoptimization
I´m having trouble proving the following:
Let $C\subset\mathbb{R}^n$. Prove $x \in C$ is an extreme point of $C$ if and only if $C\setminus {x}$ is convex.
For the sufficiency, I figured if $x$ is an extreme point then the result follows since any other point can be expressed as a convex combination.
The necessity part is where I´m stuck at, since I´m supposed to do it by contradiction.
Thanks for all help.
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:
Suppose $X \setminus \{x\}$ is convex and $x=\alpha x_1+(1-\alpha) x_2$ with $0<\alpha<1$ and $x_1,x_2 \in X$. If $x_1=x$ we get $(1-\alpha)x=(1-\alpha)x_2$ so $x_2=x$. Thus $x=x_1=x_2$. Similarly, $x=x_2$ implies $x=x_1=x_2$. If $x \neq x_1$ and $x \neq x_2$ then $x_1,x_2 \in X \setminus \{x\}$ contradicting convexity of $X \setminus \{x\}$. We have proved that $x$ is an extreme point of $X$.
Best Answer
Suppose $x$ is extreme and $C \setminus \{x\}$ is not convex. In particular, there are $a,b$ and $t \in (0,1)$ such that $a,b \in C$ but $tb+(1-t)a \notin C$. Then we must have $x=tb+(1-t)a$ but this contradicts $x$ being extreme. Hence $C \setminus \{x\}$ is convex.
If $ x$ is not extreme, then there are $a,b$ different from $x$ and $t \in (0,1)$ such that $x=tb+(1-t)a$. Hence $C \setminus \{x\}$ is not convex.