Extreme point

Short description: Point not between two other points

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

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

## Contents

* 1 Definition
* 1.1 Characterizations
* 2 Examples
* 3 Properties
* 4 Theorems
* 4.1 Krein–Milman theorem
* 4.2 For Banach spaces
* 5 Related notions
* 5.1 k-extreme points
* 6 See also
* 7 Citations
* 8 Bibliography

## Definition

Throughout, it is assumed that [math]\displaystyle{ X }[/math] is a real or complex vector space.

For any [math]\displaystyle{ p, x, y \in X, }[/math] say that [math]\displaystyle{ p }[/math] lies between[2] [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] if [math]\displaystyle{ x \neq y }[/math] and there exists a [math]\displaystyle{ 0 \lt t \lt 1 }[/math] such that [math]\displaystyle{ p = t x + (1-t) y. }[/math]

If [math]\displaystyle{ K }[/math] is a subset of [math]\displaystyle{ X }[/math] and [math]\displaystyle{ p \in K, }[/math] then [math]\displaystyle{ p }[/math] is called an extreme point[2] of [math]\displaystyle{ K }[/math] if it does not lie between any two distinct points of [math]\displaystyle{ K. }[/math] That is, if there does not exist [math]\displaystyle{ x, y \in K }[/math] and [math]\displaystyle{ 0 \lt t \lt 1 }[/math] such that [math]\displaystyle{ x \neq y }[/math] and [math]\displaystyle{ p = t x + (1-t) y. }[/math] The set of all extreme points of [math]\displaystyle{ K }[/math] is denoted by [math]\displaystyle{ \operatorname{extreme}(K). }[/math]

Generalizations

If [math]\displaystyle{ S }[/math] is a subset of a vector space then a linear sub-variety (that is, an affine subspace) [math]\displaystyle{ A }[/math] of the vector space is called a support variety if [math]\displaystyle{ A }[/math] meets [math]\displaystyle{ S }[/math] (that is, [math]\displaystyle{ A \cap S }[/math] is not empty) and every open segment [math]\displaystyle{ I \subseteq S }[/math] whose interior meets [math]\displaystyle{ A }[/math] is necessarily a subset of [math]\displaystyle{ A. }[/math][3] A 0-dimensional support variety is called an extreme point of [math]\displaystyle{ S. }[/math][3]

### Characterizations

The midpoint[2] of two elements [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] in a vector space is the vector [math]\displaystyle{ \tfrac{1}{2}(x+y). }[/math]

For any elements [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] in a vector space, the set [math]\displaystyle{ [x, y] = \\{t x + (1-t) y : 0 \leq t \leq 1\\} }[/math] is called the closed line segment or closed interval between [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y. }[/math] The open line segment or open interval between [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] is [math]\displaystyle{ (x, x) = \varnothing }[/math] when [math]\displaystyle{ x = y }[/math] while it is [math]\displaystyle{ (x, y) = \\{t x + (1-t) y : 0 \lt t \lt 1\\} }[/math] when [math]\displaystyle{ x \neq y. }[/math][2] The points [math]\displaystyle{ x }[/math] and [math]\displaystyle{ y }[/math] 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 [math]\displaystyle{ [x, y] }[/math] is equal to the convex hull of [math]\displaystyle{ (x, y) }[/math] if (and only if) [math]\displaystyle{ x \neq y. }[/math] So if [math]\displaystyle{ K }[/math] is convex and [math]\displaystyle{ x, y \in K, }[/math] then [math]\displaystyle{ [x, y] \subseteq K. }[/math]

If [math]\displaystyle{ K }[/math] is a nonempty subset of [math]\displaystyle{ X }[/math] and [math]\displaystyle{ F }[/math] is a nonempty subset of [math]\displaystyle{ K, }[/math] then [math]\displaystyle{ F }[/math] is called a face[2] of [math]\displaystyle{ K }[/math] if whenever a point [math]\displaystyle{ p \in F }[/math] lies between two points of [math]\displaystyle{ K, }[/math] then those two points necessarily belong to [math]\displaystyle{ F. }[/math]

Theorem[2] -- Let [math]\displaystyle{ K }[/math] be a non-empty convex subset of a vector space [math]\displaystyle{ X }[/math] and let [math]\displaystyle{ p \in K. }[/math] Then the following statements are equivalent:

1. [math]\displaystyle{ p }[/math] is an extreme point of [math]\displaystyle{ K. }[/math]
2. [math]\displaystyle{ K \setminus \\{p\\} }[/math] is convex.
3. [math]\displaystyle{ p }[/math] is not the midpoint of a non-degenerate line segment contained in [math]\displaystyle{ K. }[/math]
4. for any [math]\displaystyle{ x, y \in K, }[/math] if [math]\displaystyle{ p \in [x, y] }[/math] then [math]\displaystyle{ x = p \text{ or } y = p. }[/math]
5. if [math]\displaystyle{ x \in X }[/math] is such that both [math]\displaystyle{ p + x }[/math] and [math]\displaystyle{ p - x }[/math] belong to [math]\displaystyle{ K, }[/math] then [math]\displaystyle{ x = 0. }[/math]
6. [math]\displaystyle{ \\{p\\} }[/math] is a face of [math]\displaystyle{ K. }[/math]

## Examples

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

The extreme points of the closed unit disk in [math]\displaystyle{ \R^2 }[/math] 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 [math]\displaystyle{ \R^2 }[/math] are the extreme points of that polygon.

An injective linear map [math]\displaystyle{ F : X \to Y }[/math] sends the extreme points of a convex set [math]\displaystyle{ C \subseteq X }[/math] to the extreme points of the convex set [math]\displaystyle{ F(X). }[/math][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 [math]\displaystyle{ X. }[/math][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 [math]\displaystyle{ S }[/math] is convex and compact in a locally convex topological vector space, then [math]\displaystyle{ S }[/math] 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 [math]\displaystyle{ E }[/math] be a Banach space with the Radon-Nikodym property, let [math]\displaystyle{ C }[/math] be a separable, closed, bounded, convex subset of [math]\displaystyle{ E, }[/math] and let [math]\displaystyle{ a }[/math] be a point in [math]\displaystyle{ C. }[/math] Then there is a probability measure [math]\displaystyle{ p }[/math] on the universally measurable sets in [math]\displaystyle{ C }[/math] such that [math]\displaystyle{ a }[/math] is the barycenter of [math]\displaystyle{ p, }[/math] and the set of extreme points of [math]\displaystyle{ C }[/math] has [math]\displaystyle{ p }[/math]-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 [math]\displaystyle{ S }[/math] is [math]\displaystyle{ k }[/math]-extreme if it lies in the interior of a [math]\displaystyle{ k }[/math]-dimensional convex set within [math]\displaystyle{ S, }[/math] but not a [math]\displaystyle{ k + 1 }[/math]-dimensional convex set within [math]\displaystyle{ S. }[/math] Thus, an extreme point is also a [math]\displaystyle{ 0 }[/math]-extreme point. If [math]\displaystyle{ S }[/math] is a polytope, then the [math]\displaystyle{ k }[/math]-extreme points are exactly the interior points of the [math]\displaystyle{ k }[/math]-dimensional faces of [math]\displaystyle{ S. }[/math] More generally, for any convex set [math]\displaystyle{ S, }[/math] the [math]\displaystyle{ k }[/math]-extreme points are partitioned into [math]\displaystyle{ k }[/math]-dimensional open faces.

The finite-dimensional Krein-Milman theorem, which is due to Minkowski, can be quickly proved using the concept of [math]\displaystyle{ k }[/math]-extreme points. If [math]\displaystyle{ S }[/math] is closed, bounded, and [math]\displaystyle{ n }[/math]-dimensional, and if [math]\displaystyle{ p }[/math] is a point in [math]\displaystyle{ S, }[/math] then [math]\displaystyle{ p }[/math] is [math]\displaystyle{ k }[/math]-extreme for some [math]\displaystyle{ k \leq n. }[/math] The theorem asserts that [math]\displaystyle{ p }[/math] is a convex combination of extreme points. If [math]\displaystyle{ k = 0 }[/math] then it is immediate. Otherwise [math]\displaystyle{ p }[/math] lies on a line segment in [math]\displaystyle{ S }[/math] which can be maximally extended (because [math]\displaystyle{ S }[/math] is closed and bounded). If the endpoints of the segment are [math]\displaystyle{ q }[/math] and [math]\displaystyle{ r, }[/math] then their extreme rank must be less than that of [math]\displaystyle{ p, }[/math] 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?". https://www.quora.com/What-is-the-difference-between-corner-points-and-extreme-points-in-linear-programming-problems.
2. ↑ 2.0 2.1 2.2 2.3 2.4 2.5 2.6 2.7 2.8 2.9 Narici & Beckenstein 2011, pp. 275-339.
3. ↑ 3.0 3.1 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.
5. ↑ Edgar GA. A noncompact Choquet theorem. Proceedings of the American Mathematical Society. 1975;49(2):354-8.
6. ↑ 6.0 6.1 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.

## Bibliography

* Adasch, Norbert; Ernst, Bruno; Keim, Dieter (1978). Topological Vector Spaces: The Theory Without Convexity Conditions. Lecture Notes in Mathematics. {3834. Berlin New York: Springer-Verlag. ISBN 978-3-540-08662-8. OCLC 297140003.
* Bourbaki, Nicolas (1987). Topological Vector Spaces: Chapters 1–5. Éléments de mathématique. 2. Berlin New York: Springer-Verlag. ISBN 978-3-540-42338-6. OCLC 17499190. http://www.numdam.org/item?id=AIF_1950__2__5_0.
* Paul E. Black, ed (2004-12-17). "extreme point". Dictionary of algorithms and data structures. US National institute of standards and technology. https://xlinux.nist.gov/dads/HTML/extremepoint.html.
* Borowski, Ephraim J.; Borwein, Jonathan M. (1989). "extreme point". Dictionary of mathematics. Collins dictionary. HarperCollins. ISBN 0-00-434347-6.
* Grothendieck, Alexander (January 1, 1973). Topological Vector Spaces. New York: Gordon and Breach Science Publishers. ISBN 978-0-677-30020-7. OCLC 886098. https://archive.org/details/topologicalvecto0000grot.
* Template:Halmos A Hilbert Space Problem Book 1982
* 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. New York: Springer Science & Business Media. ISBN 978-3-642-64988-2. 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 (January 1, 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. https://archive.org/details/functionalanalys00rudi.
* 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 (August 6, 2006). 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.

* v
* t
* e

Functional analysis (topics)

Topological vector spaces|

* Asplund
* Banach (list)
* Banach lattice
* Barrelled
* Bornological
* Brauner
* F-space
* Fréchet (tame)
* Hilbert (Inner product space
* Polarization identity)
* LF-space
* Locally convex (Seminorms/Minkowski functionals)
* Mackey
* Montel
* Nuclear
* Normed (norm)
* Quasinormed
* Reflexive
* Riesz
* Smith
* Stereotype
* Strictly convex
* Webbed
* Topological tensor product (of Hilbert spaces)

Topologies of function spaces|

* Dual
* Dual space (Dual norm)
* Operator
* Ultraweak
* Weak (polar
* operator)
* Mackey
* Strong (polar
* operator)
* Ultrastrong
* Uniform convergence

Linear operators|

* Adjoint
* Bilinear (form
* operator
* sesquilinear)
* (Un)Bounded
* Closed
* Compact (on Hilbert spaces)
* (Dis)Continuous
* Densely defined
* Fredholm
* Hilbert–Schmidt
* Functionals (positive)
* Normal
* Nuclear
* Self-adjoint
* Strictly singular
* Trace class
* Transpose
* Unitary

Operator theory|

* Banach algebras
* C*-algebras
* Spectrum (C*-algebra
* radius)
* Spectral theory (of ODEs
* Spectral theorem)
* Polar decomposition
* Singular value decomposition

Theorems|

* Banach–Alaoglu
* Banach–Mazur
* Banach–Saks
* Banach–Schauder (open mapping)
* Banach–Steinhaus (Uniform boundedness)
* Bessel's inequality
* Cauchy–Schwarz inequality
* Closed graph
* Closed range
* Eberlein–Šmulian
* Freudenthal spectral
* Gelfand–Mazur
* Gelfand–Naimark
* Goldstine
* Hahn–Banach (hyperplane separation)
* Kakutani fixed-point
* Krein–Milman
* Lomonosov's invariant subspace
* Mackey–Arens
* Mazur's lemma
* M. Riesz extension
* Riesz representation
* Parseval's identity
* Schauder fixed-point

Analysis|

* Abstract Wiener space
* Bochner space
* Differentiation in Fréchet spaces
* Derivatives (Fréchet
* Gateaux
* functional
* holomorphic)
* Integrals (Bochner
* Dunford
* Gelfand–Pettis
* regulated
* Paley–Wiener
* weak)
* Functional calculus (Borel
* continuous
* holomorphic)
* Inverse function theorem (Nash–Moser theorem)
* Measures (Lebesgue
* Projection-valued
* Vector)
* Weakly measurable function

Types of sets|

* Absolutely convex
* Absorbing
* Balanced
* Bounded
* Convex
* Convex cone (subset)
* Linear cone (subset)
* Radial
* Star-shaped
* Symmetric
* Zonotope

Subsets / set operations|

* Algebraic interior (core)
* Bounding points
* Convex hull
* Extreme point
* Interior
* Minkowski addition
* Polar

0.00

(0 votes)

Original source: https://en.wikipedia.org/wiki/Extreme point. Read more

|

Retrieved from "https://handwiki.org/wiki/index.php?title=Extreme_point&oldid=3358800"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template