# Extreme point

In mathematics, an extreme point of a convex set ${\displaystyle S}$ in a real or complex vector space is a point in ${\displaystyle S}$ that does not lie in any open line segment joining two points of ${\displaystyle S.}$ In linear programming problems, an extreme point is also called vertex or corner point of ${\displaystyle S.}$[1]

## Definition

Throughout, it is assumed that ${\displaystyle X}$ is a real or complex vector space.

For any ${\displaystyle p,x,y\in X,}$ say that ${\displaystyle p}$ lies between[2] ${\displaystyle x}$ and ${\displaystyle y}$ if ${\displaystyle x\neq y}$ and there exists a ${\displaystyle 0 such that ${\displaystyle p=tx+(1-t)y.}$

If ${\displaystyle K}$ is a subset of ${\displaystyle X}$ and ${\displaystyle p\in K,}$ then ${\displaystyle p}$ is called an extreme point[2] of ${\displaystyle K}$ if it does not lie between any two distinct points of ${\displaystyle K.}$ That is, if there does not exist ${\displaystyle x,y\in K}$ and ${\displaystyle 0 such that ${\displaystyle x\neq y}$ and ${\displaystyle p=tx+(1-t)y.}$ The set of all extreme points of ${\displaystyle K}$ is denoted by ${\displaystyle \operatorname {extreme} (K).}$

Generalizations

If ${\displaystyle S}$ is a subset of a vector space then a linear sub-variety (that is, an affine subspace) ${\displaystyle A}$ of the vector space is called a support variety if ${\displaystyle A}$ meets ${\displaystyle S}$ (that is, ${\displaystyle A\cap S}$ is not empty) and every open segment ${\displaystyle I\subseteq S}$ whose interior meets ${\displaystyle A}$ is necessarily a subset of ${\displaystyle A.}$[3] A 0-dimensional support variety is called an extreme point of ${\displaystyle S.}$[3]

### Characterizations

The midpoint[2] of two elements ${\displaystyle x}$ and ${\displaystyle y}$ in a vector space is the vector ${\displaystyle {\tfrac {1}{2}}(x+y).}$

For any elements ${\displaystyle x}$ and ${\displaystyle y}$ in a vector space, the set ${\displaystyle [x,y]=\{tx+(1-t)y:0\leq t\leq 1\}}$ is called the closed line segment or closed interval between ${\displaystyle x}$ and ${\displaystyle y.}$ The open line segment or open interval between ${\displaystyle x}$ and ${\displaystyle y}$ is ${\displaystyle (x,x)=\varnothing }$ when ${\displaystyle x=y}$ while it is ${\displaystyle (x,y)=\{tx+(1-t)y:0 when ${\displaystyle x\neq y.}$[2] The points ${\displaystyle x}$ and ${\displaystyle y}$ are called the endpoints of these interval. An interval is said to be a non−degenerate interval or a proper interval if its endpoints are distinct. The midpoint of an interval is the midpoint of its endpoints.

The closed interval ${\displaystyle [x,y]}$ is equal to the convex hull of ${\displaystyle (x,y)}$ if (and only if) ${\displaystyle x\neq y.}$ So if ${\displaystyle K}$ is convex and ${\displaystyle x,y\in K,}$ then ${\displaystyle [x,y]\subseteq K.}$

If ${\displaystyle K}$ is a nonempty subset of ${\displaystyle X}$ and ${\displaystyle F}$ is a nonempty subset of ${\displaystyle K,}$ then ${\displaystyle F}$ is called a face[2] of ${\displaystyle K}$ if whenever a point ${\displaystyle p\in F}$ lies between two points of ${\displaystyle K,}$ then those two points necessarily belong to ${\displaystyle F.}$

Theorem[2] — Let ${\displaystyle K}$ be a non-empty convex subset of a vector space ${\displaystyle X}$ and let ${\displaystyle p\in K.}$ Then the following statements are equivalent:

1. ${\displaystyle p}$ is an extreme point of ${\displaystyle K.}$
2. ${\displaystyle K\setminus \{p\}}$ is convex.
3. ${\displaystyle p}$ is not the midpoint of a non-degenerate line segment contained in ${\displaystyle K.}$
4. for any ${\displaystyle x,y\in K,}$ if ${\displaystyle p\in [x,y]}$ then ${\displaystyle x=p{\text{ or }}y=p.}$
5. if ${\displaystyle x\in X}$ is such that both ${\displaystyle p+x}$ and ${\displaystyle p-x}$ belong to ${\displaystyle K,}$ then ${\displaystyle x=0.}$
6. ${\displaystyle \{p\}}$ is a face of ${\displaystyle K.}$

## Examples

If ${\displaystyle a are two real numbers then ${\displaystyle a}$ and ${\displaystyle b}$ are extreme points of the interval ${\displaystyle [a,b].}$ However, the open interval ${\displaystyle (a,b)}$ has no extreme points.[2] Any open interval in ${\displaystyle \mathbb {R} }$ has no extreme points while any non-degenerate closed interval not equal to ${\displaystyle \mathbb {R} }$ does have extreme points (that is, the closed interval's endpoint(s)). More generally, any open subset of finite-dimensional Euclidean space ${\displaystyle \mathbb {R} ^{n}}$ has no extreme points.

The extreme points of the closed unit disk in ${\displaystyle \mathbb {R} ^{2}}$ is the unit circle.

The perimeter of any convex polygon in the plane is a face of that polygon.[2] The vertices of any convex polygon in the plane ${\displaystyle \mathbb {R} ^{2}}$ are the extreme points of that polygon.

An injective linear map ${\displaystyle F:X\to Y}$ sends the extreme points of a convex set ${\displaystyle C\subseteq X}$ to the extreme points of the convex set ${\displaystyle F(X).}$[2] This is also true for injective affine maps.

## Properties

The extreme points of a compact convex set form a Baire space (with the subspace topology) but this set may fail to be closed in ${\displaystyle X.}$[2]

## Theorems

### Krein–Milman theorem

The Krein–Milman theorem is arguably one of the most well-known theorems about extreme points.

Krein–Milman theorem — If ${\displaystyle S}$ is convex and compact in a locally convex topological vector space, then ${\displaystyle S}$ is the closed convex hull of its extreme points: In particular, such a set has extreme points.

### For Banach spaces

These theorems are for Banach spaces with the Radon–Nikodym property.

A theorem of Joram Lindenstrauss states that, in a Banach space with the Radon–Nikodym property, a nonempty closed and bounded set has an extreme point. (In infinite-dimensional spaces, the property of compactness is stronger than the joint properties of being closed and being bounded.[4])

Theorem  — Let ${\displaystyle E}$ be a Banach space with the Radon-Nikodym property, let ${\displaystyle C}$ be a separable, closed, bounded, convex subset of ${\displaystyle E,}$ and let ${\displaystyle a}$ be a point in ${\displaystyle C.}$ Then there is a probability measure ${\displaystyle p}$ on the universally measurable sets in ${\displaystyle C}$ such that ${\displaystyle a}$ is the barycenter of ${\displaystyle p,}$ and the set of extreme points of ${\displaystyle C}$ has ${\displaystyle p}$-measure 1.[5]

Edgar’s theorem implies Lindenstrauss’s theorem.

## Related notions

A closed convex subset of a topological vector space is called strictly convex if every one of its (topological) boundary points is an extreme point.[6] The unit ball of any Hilbert space is a strictly convex set.[6]

### k-extreme points

More generally, a point in a convex set ${\displaystyle S}$ is ${\displaystyle k}$-extreme if it lies in the interior of a ${\displaystyle k}$-dimensional convex set within ${\displaystyle S,}$ but not a ${\displaystyle k+1}$-dimensional convex set within ${\displaystyle S.}$ Thus, an extreme point is also a ${\displaystyle 0}$-extreme point. If ${\displaystyle S}$ is a polytope, then the ${\displaystyle k}$-extreme points are exactly the interior points of the ${\displaystyle k}$-dimensional faces of ${\displaystyle S.}$ More generally, for any convex set ${\displaystyle S,}$ the ${\displaystyle k}$-extreme points are partitioned into ${\displaystyle k}$-dimensional open faces.

The finite-dimensional Krein-Milman theorem, which is due to Minkowski, can be quickly proved using the concept of ${\displaystyle k}$-extreme points. If ${\displaystyle S}$ is closed, bounded, and ${\displaystyle n}$-dimensional, and if ${\displaystyle p}$ is a point in ${\displaystyle S,}$ then ${\displaystyle p}$ is ${\displaystyle k}$-extreme for some ${\displaystyle k\leq n.}$ The theorem asserts that ${\displaystyle p}$ is a convex combination of extreme points. If ${\displaystyle k=0}$ then it is immediate. Otherwise ${\displaystyle p}$ lies on a line segment in ${\displaystyle S}$ which can be maximally extended (because ${\displaystyle S}$ is closed and bounded). If the endpoints of the segment are ${\displaystyle q}$ and ${\displaystyle r,}$ then their extreme rank must be less than that of ${\displaystyle p,}$ and the theorem follows by induction.