Extreme Points, Vertices, and Basic Feasible Solutions

A point $\mathbf{x}$ in a convex set $S$ is an extreme point of $S$ if it cannot be written as a strict convex combination of two distinct points of $S$. In symbols, $\mathbf{x}$ is an extreme point of $S$ if whenever

$$\mathbf{x} = \lambda \mathbf{y} + (1-\lambda)\mathbf{z}, \qquad \mathbf{y}, \mathbf{z} \in S, \qquad \lambda \in (0, 1),$$

we must have $\mathbf{y} = \mathbf{z} = \mathbf{x}$.

Geometrically, extreme points are the "corners" of $S$ -- the points that do not lie in the interior of any line segment contained in $S$.

For example, in the line segment $S = [0, 1] \subset \mathbb{R}$, only the endpoints $0$ and $1$ are extreme. For any interior point $x \in (0, 1)$, we can write

$$x = \tfrac{1}{2}(x - \epsilon) + \tfrac{1}{2}(x + \epsilon)$$

for a small enough $\epsilon > 0$, exhibiting $x$ as a strict convex combination of two distinct points of $S$.

For a polygon in $\mathbb{R}^2$, the extreme points are exactly its corner points. Points lying strictly between two corners along an edge, as well as points in the interior, are not extreme.