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

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

Definition

edit

Throughout, it is assumed that   is a real or complex vector space.

For any   say that   lies between[2]   and   if   and there exists a   such that  

If   is a subset of   and   then   is called an extreme point[2] of   if it does not lie between any two distinct points of   That is, if there does not exist   and   such that   and   The set of all extreme points of   is denoted by  

Generalizations

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

Characterizations

edit

The midpoint[2] of two elements   and   in a vector space is the vector  

For any elements   and   in a vector space, the set   is called the closed line segment or closed interval between   and   The open line segment or open interval between   and   is   when   while it is   when  [2] The points   and   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   is equal to the convex hull of   if (and only if)   So if   is convex and   then  

If   is a nonempty subset of   and   is a nonempty subset of   then   is called a face[2] of   if whenever a point   lies between two points of   then those two points necessarily belong to  

Theorem[2] — Let   be a non-empty convex subset of a vector space   and let   Then the following statements are equivalent:

  1.   is an extreme point of  
  2.   is convex.
  3.   is not the midpoint of a non-degenerate line segment contained in  
  4. for any   if   then  
  5. if   is such that both   and   belong to   then  
  6.   is a face of  

Examples

edit

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

The extreme points of the closed unit disk in   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   are the extreme points of that polygon.

An injective linear map   sends the extreme points of a convex set   to the extreme points of the convex set  [2] This is also true for injective affine maps.

Properties

edit

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  [2]

Theorems

edit

Krein–Milman theorem

edit

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

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

For Banach spaces

edit

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

Edgar’s theorem implies Lindenstrauss’s theorem.

edit

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

edit

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

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

See also

edit

Citations

edit
  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.

Bibliography

edit