# 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 pointsEdit

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 alsoEdit

## NotesEdit

**^**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.

## ReferencesEdit

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