Extreme point explained

S in a real or complex vector space is a point in S that 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. ^[1]

Definition

Throughout, it is assumed that

X is a real or complex vector space.

For any

p, x, y \in X, say that p x and y if x ≠ y and there exists a 0 < t < 1 such that p = t x + ( 1- t) y.

If

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

Generalizations

If

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

Characterizations

The of two elements

x and y in a vector space is the vector \tfrac{ 1 }{ 2 }(x + y).

For any elements

x and y in a vector space, the set [x, y] = \{t x + ( 1- t) y : 0 \leq t \leq 1 \} is called the or between x and y. The or between x and y is (x, x) = \varnothing when x = y while it is (x, y) = \{t x + ( 1- t) y : 0 < t < 1 \} when x ≠ y. The points x and y are called the of these interval. An interval is said to be a or a if its endpoints are distinct. The is the midpoint of its endpoints.

The closed interval

[x, y] is equal to the convex hull of (x, y) if (and only if) x ≠ y. So if K is convex and x, y \in K, then [x, y] \subseteq K.

If

K is a nonempty subset of X and F is a nonempty subset of K, then F is called a of K if whenever a point p \in F lies between two points of K, then those two points necessarily belong to F.

Examples

If

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

The extreme points of the closed unit disk in

\R ^{2} is the unit circle.

The perimeter of any convex polygon in the plane is a face of that polygon. The vertices of any convex polygon in the plane

\R ^{2} are the extreme points of that polygon.

An injective linear map

F : X \to Y sends the extreme points of a convex set C \subseteq X to the extreme points of the convex set F(X). 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 to be closed in

X.

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. (In infinite-dimensional spaces, the property of compactness is stronger than the joint properties of being closed and being bounded.^[2])

Edgar’s theorem implies Lindenstrauss’s theorem.

Related notions

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

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 \leq n. The theorem asserts that p is a convex combination of extreme points. If k = 0 then it is immediate. Otherwise p lies on a line segment in S which can be maximally extended (because S is closed and bounded). 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.

See also

• • Bang–bang control^[3]

Bibliography

• • • Web site: Paul E. Black. 2004-12-17. extreme point. Dictionary of algorithms and data structures. US National institute of standards and technology. 2011-03-24.
• Encyclopedia: Borowski. Ephraim J.. Borwein. Jonathan M.. 1989. extreme point. Dictionary of mathematics. Collins dictionary. HarperCollins. 0-00-434347-6.

Notes and References

1. Web site: What is the difference between corner points and extreme points in linear programming problems?. Saltzman. Matthew.
2. Artstein. Zvi. Discrete and continuous bang-bang and facial spaces, or: Look for the extreme points. SIAM Review. 22. 1980. 2. 172–185. 10.1137/1022026. 564562. 2029960.
3. Artstein. Zvi. Discrete and continuous bang-bang and facial spaces, or: Look for the extreme points. SIAM Review. 22. 1980. 2. 172–185. 10.1137/1022026. 2029960 . 564562.