Extreme point


In mathematics, an extreme point of a convex set S in a real vector space is a point in S which does not lie in any open line segment joining two points of S. In linear programming problems, an extreme point is also called vertex or corner point of S.

Definition

Throughout, we assume that is a real or complex vector space.

Characterizations

Note that is equal to the convex hull of so if is convex and, then.

Examples

The extreme points of a compact convex form a Baire space but this set may fail to be closed in.

Theorems

Krein–Milman theorem

The Krein–Milman theorem is arguably one of the most well-known theorems about 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..
Edgar's theorem implies Lindenstrauss's theorem.

''k''-extreme points

More generally, a point in a convex set S is k-extreme if it lies in the interior of a k-dimensional convex set within S, but not a k+1-dimensional convex set within S. Thus, an extreme point is also a 0-extreme point. If S is a polytope, then the k-extreme points are exactly the interior points of the k-dimensional faces of S. More generally, for any convex set S, the k-extreme points are partitioned into k-dimensional open faces.
The finite-dimensional Krein-Milman theorem, which is due to Minkowski, can be quickly proved using the concept of k-extreme points. If S is closed, bounded, and n-dimensional, and if p is a point in S, then p is k-extreme for some k < n. The theorem asserts that p is a convex combination of extreme points. If k = 0, then it's trivially true. Otherwise p lies on a line segment in S which can be maximally extended. If the endpoints of the segment are q and r, then their extreme rank must be less than that of p, and the theorem follows by induction.