How to prove a point in a set is an extreme point of the set ?

2.5k Views Asked by At

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

1

There are 1 best solutions below

0
On

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$.