Extreme point
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].
- The Krein–Milman theorem states that if S is convex and compact in a locally convex space, then S is the closed convex hull of its extreme points: In particular, such a set has extreme points.
The Krein–Milman theorem is stated for locally convex topological vector spaces. The next theorems are stated 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]
- A theorem of Gerald Edgar states that, in a Banach space with the Radon–Nikodym property, a closed and bounded set is the closed convex hull of its extreme points:
Let E be a Banach space with the Radon-Nikodym property, let C be a separable, closed, bounded, convex subset of E, and let a be a point in C. Then there is a probability measure p on the universally measurable sets in C such that a is the barycenter of p, and the set of extreme points of C has p-measure 1.[3]
Edgar's theorem implies Lindenstrauss's theorem.
Contents
k-extreme points[edit]
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[edit]
Notes[edit]
- ^ Saltzman, Matthew. "What is the difference between corner points and extreme points in linear programming problems?".
- ^ Artstein (1980, p. 173): 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.
- ^ Edgar GA. A noncompact Choquet theorem. Proceedings of the American Mathematical Society. 1975;49(2):354-8.
References[edit]
- 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.
