Extreme point

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

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.^[1]

Definition

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

For any x, x₁, x₂ ∈ S, say that x lies between^[2] x₁ and x₂ if x₁ ≠ x₂ and there exists a 0 < t < 1 such that x = tx₁ + (1 − t)x₂.

If K is a subset of X and x ∈ K, then x is called an extreme point^[2] of K if it does not lie between any two distinct points of K. That is, if there does not exist x₁, x₂ ∈ K and 0 < t < 1 such that x₁ ≠ x₂ and x = tx₁ + (1 − t) x₂. The set of all extreme points of K is denoted by extreme(K).

Characterizations

The midpoint^[2] of two elements x and y in a vector space is the vector 1/2(x + y).

For any elements x and y in a vector space, the set [x, y] := {tx + (1 − t)y : 0 ≤ t ≤ 1} is called the closed line segment or closed interval between x and y. The open line segment or open interval between x and y is (x, x) := ∅ when x = y while it is (x, y) := {tx + (1 − t)y : 0 < t < 1} when x ≠ y.^[2] The points x and y are called the endpoints of these interval. An interval is said to be non-degenerate or proper if its endpoints are distinct. The midpoint of an interval is the midpoint of its endpoints.

Note that [x, y] is equal to the convex hull of {x, y} so if K is convex and x, y ∈ K, then [x, y] ⊆ K.

If K is a nonempty subset of X and F is a nonempty subset of K, then F is called a face^[2] of K if whenever a point p ∈ 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.^[2]
• An injective linear map F : X → Y sends the extreme points of a convex set C ⊆ X to the extreme points of the convex set F(C).^[2] This is also true for injective affine maps.
• 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.
• The extreme points of the closed unit disk in ℝ² is the unit circle.
• Any open interval in ℝ has no extreme points while any non-degenerate closed interval not equal to ℝ does have extreme points (i.e. the closed interval's endpoint(s)). More generally, any open subset of finite-dimensional Euclidean space ℝⁿ has no extreme points.

Properties

The extreme points of a compact convex form a Baire space (with the subspace topology) but this set may fail to be closed in X.^[2]

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).^[3]

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 (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

• Choquet theory

Citations

Bibliography

• Adasch, Norbert; Ernst, Bruno; Keim, Dieter (1978). Topological Vector Spaces: The Theory Without Convexity Conditions. Lecture Notes in Mathematics. 639. Berlin New York: Springer-Verlag. ISBN 978-3-540-08662-8. OCLC 297140003.
• Bourbaki, Nicolas (1987) [1981]. Sur certains espaces vectoriels topologiques [Topological Vector Spaces: Chapters 1–5]. Annales de l'Institut Fourier. Éléments de mathématique. 2. Translated by Eggleston, H.G.; Madan, S. Berlin New York: Springer-Verlag. ISBN 978-3-540-42338-6. 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. Harper Collins. 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.
• Jarchow, Hans (1981). Locally convex spaces. Stuttgart: B.G. Teubner. ISBN 978-3-519-02224-4. OCLC 8210342.
• Köthe, Gottfried (1969). Topological Vector Spaces I. Grundlehren der mathematischen Wissenschaften. 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. 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. 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. 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. 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.