Extreme point (original) (raw)

From Wikipedia, the free encyclopedia

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 S {\displaystyle S} {\displaystyle S} in a real or complex vector space is a point in S {\displaystyle S} {\displaystyle S} that does not lie in any open line segment joining two points of S . {\displaystyle S.} {\displaystyle S.} In linear programming problems, an extreme point is also called vertex or corner point of S . {\displaystyle S.} {\displaystyle S.}[1]

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

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

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

Generalizations

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

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

For any elements x {\displaystyle x} {\displaystyle x} and y {\displaystyle y} {\displaystyle y} in a vector space, the set [ x , y ] = { t x + ( 1 − t ) y : 0 ≤ t ≤ 1 } {\displaystyle [x,y]=\{tx+(1-t)y:0\leq t\leq 1\}} {\displaystyle [x,y]=\{tx+(1-t)y:0\leq t\leq 1\}} is called the closed line segment or closed interval between x {\displaystyle x} {\displaystyle x} and y . {\displaystyle y.} {\displaystyle y.} The open line segment or open interval between x {\displaystyle x} {\displaystyle x} and y {\displaystyle y} {\displaystyle y} is ( x , x ) = ∅ {\displaystyle (x,x)=\varnothing } {\displaystyle (x,x)=\varnothing } when x = y {\displaystyle x=y} {\displaystyle x=y} while it is ( x , y ) = { t x + ( 1 − t ) y : 0 < t < 1 } {\displaystyle (x,y)=\{tx+(1-t)y:0<t<1\}} {\displaystyle (x,y)=\{tx+(1-t)y:0<t<1\}} when x ≠ y . {\displaystyle x\neq y.} {\displaystyle x\neq y.}[2] The points x {\displaystyle x} {\displaystyle x} and y {\displaystyle y} {\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 [ x , y ] {\displaystyle [x,y]} {\displaystyle [x,y]} is equal to the convex hull of ( x , y ) {\displaystyle (x,y)} {\displaystyle (x,y)} if (and only if) x ≠ y . {\displaystyle x\neq y.} {\displaystyle x\neq y.} So if K {\displaystyle K} {\displaystyle K} is convex and x , y ∈ K , {\displaystyle x,y\in K,} {\displaystyle x,y\in K,} then [ x , y ] ⊆ K . {\displaystyle [x,y]\subseteq K.} {\displaystyle [x,y]\subseteq K.}

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

If a < b {\displaystyle a<b} {\displaystyle a<b} are two real numbers then a {\displaystyle a} {\displaystyle a} and b {\displaystyle b} {\displaystyle b} are extreme points of the interval [ a , b ] . {\displaystyle [a,b].} {\displaystyle [a,b].} However, the open interval ( a , b ) {\displaystyle (a,b)} {\displaystyle (a,b)} has no extreme points.[2]Any open interval in R {\displaystyle \mathbb {R} } {\displaystyle \mathbb {R} } has no extreme points while any non-degenerate closed interval not equal to R {\displaystyle \mathbb {R} } {\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 R n {\displaystyle \mathbb {R} ^{n}} {\displaystyle \mathbb {R} ^{n}} has no extreme points.

The extreme points of the closed unit disk in R 2 {\displaystyle \mathbb {R} ^{2}} {\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 R 2 {\displaystyle \mathbb {R} ^{2}} {\displaystyle \mathbb {R} ^{2}} are the extreme points of that polygon.

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

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 X . {\displaystyle X.} {\displaystyle X.}[2]

Krein–Milman theorem

[edit]

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

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

Edgar’s theorem implies Lindenstrauss’s theorem.

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]

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

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

  1. ^ Saltzman, Matthew. "What is the difference between corner points and extreme points in linear programming problems?".
  2. ^ a b c d e f g h i j Narici & Beckenstein 2011, pp. 275–339.
  3. ^ a b Grothendieck 1973, p. 186.
  4. ^ 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. JSTOR 2029960. MR 0564562.
  5. ^ Edgar GA. A noncompact Choquet theorem. Proceedings of the American Mathematical Society. 1975;49(2):354–8.
  6. ^ a b Halmos 1982, p. 5.
  7. ^ 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. JSTOR 2029960. MR 0564562.