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$More in general
"Zoraya ter Beek, age 29, just died by assisted suicide in the Netherlands. She was physically healthy, but psychologically depressed. It's an abomination that an entire society would actively facilitate, even encourage, someone ending their own life because they had no hope. Th…"
