Extreme point

Short description: Point not between two other points

A convex set in light blue, and its extreme points in red.

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 \lt t \lt 1 }$ such that $\displaystyle{ p = t x + (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 \lt t \lt 1 }$ such that $\displaystyle{ x \neq y }$ and $\displaystyle{ p = t x + (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] = \{t x + (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) = \{t x + (1-t) y : 0 \lt t \lt 1\} }$ 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 \lt b }$ 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{ \R }$ has no extreme points while any non-degenerate closed interval not equal to $\displaystyle{ \R }$ does have extreme points (that is, the closed interval's endpoint(s)). More generally, any open subset of finite-dimensional Euclidean space $\displaystyle{ \R^n }$ has no extreme points.

The extreme points of the closed unit disk in $\displaystyle{ \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{ \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 (Gerald Edgar) — 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.

• Choquet theory – Area of functional analysis and convex analysis
• Bang–bang control[7]

Citations

1. Narici & Beckenstein 2011, pp. 275-339.
2. Grothendieck 1973, p. 186.
3. Artstein, Zvi (1980). "Discrete and continuous bang-bang and facial spaces, or: Look for the extreme points". SIAM Review 22 (2): 172–185. doi:10.1137/1022026.
4. Edgar GA. A noncompact Choquet theorem. Proceedings of the American Mathematical Society. 1975;49(2):354-8.
5. Halmos 1982, p. 5.
6. Artstein, Zvi (1980). "Discrete and continuous bang-bang and facial spaces, or: Look for the extreme points". SIAM Review 22 (2): 172–185. doi:10.1137/1022026.