Extreme point

For other uses, see Extreme point (disambiguation).

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]

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

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<t<1}$  such that ${\displaystyle p=tx+(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<t<1}$  such that ${\displaystyle x\neq y}$  and ${\displaystyle p=tx+(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]=\{tx+(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)=\{tx+(1-t)y:0<t<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<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 \mathbb {R} }$  has no extreme points while any non-degenerate closed interval not equal to ${\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 ${\displaystyle \mathbb {R} ^{n}}$  has no extreme points.

The extreme points of the closed unit disk in ${\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 ${\displaystyle \mathbb {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.

See also

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

Citations

1. Saltzman, Matthew. "What is the difference between corner points and extreme points in linear programming problems?".
2. Narici & Beckenstein 2011, pp. 275–339.
3. 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. 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

• Adasch, Norbert; Ernst, Bruno; Keim, Dieter (1978). Topological Vector Spaces: The Theory Without Convexity Conditions. Lecture Notes in Mathematics. Vol. 639. Berlin New York: Springer-Verlag. ISBN 978-3-540-08662-8. OCLC 297140003.
• Bourbaki, Nicolas (1987) [1981]. Topological Vector Spaces: Chapters 1–5. Éléments de mathématique. Translated by Eggleston, H.G.; Madan, S. Berlin New York: Springer-Verlag. ISBN 3-540-13627-4. OCLC 17499190.
• Paul E. Black, ed. (2004-12-17). "extreme point". Dictionary of algorithms and data structures. US National institute of standards and technology. Retrieved 2011-03-24.
• Borowski, Ephraim J.; Borwein, Jonathan M. (1989). "extreme point". Dictionary of mathematics. Collins dictionary. HarperCollins. ISBN 0-00-434347-6.
• Grothendieck, Alexander (1973). Topological Vector Spaces. Translated by Chaljub, Orlando. New York: Gordon and Breach Science Publishers. ISBN 978-0-677-30020-7. OCLC 886098.
• Halmos, Paul R. (8 November 1982). A Hilbert Space Problem Book. Graduate Texts in Mathematics. Vol. 19 (2nd ed.). New York: Springer-Verlag. ISBN 978-0-387-90685-0. OCLC 8169781.
• Jarchow, Hans (1981). Locally convex spaces. Stuttgart: B.G. Teubner. ISBN 978-3-519-02224-4. OCLC 8210342.
• Köthe, Gottfried (1983) [1969]. Topological Vector Spaces I. Grundlehren der mathematischen Wissenschaften. Vol. 159. Translated by Garling, D.J.H. New York: Springer Science & Business Media. ISBN 978-3-642-64988-2. MR 0248498. OCLC 840293704.
• Köthe, Gottfried (1979). Topological Vector Spaces II. Grundlehren der mathematischen Wissenschaften. Vol. 237. New York: Springer Science & Business Media. ISBN 978-0-387-90400-9. OCLC 180577972.
• Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.
• Robertson, Alex P.; Robertson, Wendy J. (1980). Topological Vector Spaces. Cambridge Tracts in Mathematics. Vol. 53. Cambridge England: Cambridge University Press. ISBN 978-0-521-29882-7. OCLC 589250.
• Rudin, Walter (1991). Functional Analysis. International Series in Pure and Applied Mathematics. Vol. 8 (Second ed.). New York, NY: McGraw-Hill Science/Engineering/Math. ISBN 978-0-07-054236-5. OCLC 21163277.
• Schaefer, Helmut H.; Wolff, Manfred P. (1999). Topological Vector Spaces. GTM. Vol. 8 (Second ed.). New York, NY: Springer New York Imprint Springer. ISBN 978-1-4612-7155-0. OCLC 840278135.
• Schechter, Eric (1996). Handbook of Analysis and Its Foundations. San Diego, CA: Academic Press. ISBN 978-0-12-622760-4. OCLC 175294365.
• Trèves, François (2006) [1967]. Topological Vector Spaces, Distributions and Kernels. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1. OCLC 853623322.
• Wilansky, Albert (2013). Modern Methods in Topological Vector Spaces. Mineola, New York: Dover Publications, Inc. ISBN 978-0-486-49353-4. OCLC 849801114.