How to prove a point in a set is an extreme point of the set ?
Def: an extreme point of a set $K$ is the point that cannot be expresssed as a convex combination of other points in $K$.
Apart from the definition, what else arguments can we use to prove that a point $x\in K$ is an extreme point of $K$ ?
Thank you in advance
$\endgroup$ 41 Answer
$\begingroup$A sufficient (but not necessary) condition is the existence of a strictly separating hyperplane from the rest of the set. That is, if there exists a direction $d$ such that $d^T(x-y)>0$ for all $y \in K \setminus \{x\}$, then we can conclude $x$ is an extreme point of $K$.
The proof is almost immediate. Suppose $x = \theta y_1 + (1-\theta) y_2$ with $y_1, y_2 \in K \setminus \{x\}$ and $\theta \in (0,1)$, then $$ 0 = d^T(x - (\theta y_1 + (1-\theta) y_2)) = \theta d^T(x - y_1) + (1-\theta)d^T(x - y_2)> 0. $$ Which is a contradiction.
On the other hand, a necessary (but not sufficient) condition is the the existence of a supporting hyperplane. That is, if $x$ is a extreme point of $K$, it is on the boundary, so by the supporting hyperplane theorem, there exists a direction $d$ such that $d^T(x-y)\ge 0$ for all $y \in K$.
$\endgroup$
