Extreme point of a convex set

Let S be a convex set in $\mathbb{R}^n$. A vector $x \in S$ is said to be a extreme point of S if $x= \lambda x_1+\left ( 1-\lambda \right )x_2$ with $x_1, x_2 \in S$ and $\lambda \in\left ( 0, 1 \right )\Rightarrow x=x_1=x_2$.

Example

Step 1 − $S=\left \{ \left ( x_1,x_2 \right ) \in \mathbb{R}^2:x_{1}^{2}+x_{2}^{2}\leq 1 \right \}$

Extreme point, $E=\left \{ \left ( x_1, x_2 \right )\in \mathbb{R}^2:x_{1}^{2}+x_{2}^{2}= 1 \right \}$

Step 2 − $S=\left \{ \left ( x_1,x_2 \right )\in \mathbb{R}^2:x_1+x_2< 2, -x_1+2x_2\leq 2, x_1,x_2\geq 0 \right \}$

Extreme point, $E=\left \{ \left ( 0, 0 \right), \left ( 2, 0 \right), \left ( 0, 1 \right), \left ( \frac{2}{3}, \frac{4}{3} \right) \right \}$

Step 3 − S is the polytope made by the points $\left \{ \left ( 0,0 \right ), \left ( 1,1 \right ), \left ( 1,3 \right ), \left ( -2,4 \right ),\left ( 0,2 \right ) \right \}$

Extreme point, $E=\left \{ \left ( 0,0 \right ), \left ( 1,1 \right ),\left ( 1,3 \right ),\left ( -2,4 \right ) \right \}$

Remarks

• Any point of the convex set S, can be represented as a convex combination of its extreme points.

• It is only true for closed and bounded sets in $\mathbb{R}^n$.

• It may not be true for unbounded sets.

k extreme points

A point in a convex set is called k extreme if and only if it is the interior point of a k-dimensional convex set within S, and it is not an interior point of a (k+1)- dimensional convex set within S. Basically, for a convex set S, k extreme points make k-dimensional open faces.