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 S in a real or complex vector space is a point in S that 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]

## 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 X is a real or complex vector space.

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

If K is a subset of X and p∈K, then p 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,y∈K and 0<t<1 such that x≠y and p=tx+(1−t)y. The set of all extreme points of K is denoted by extreme⁡(K).

Generalizations

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

### Characterizations

The midpoint[2] of two elements x and y in a vector space is the vector 12(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 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 [x,y] is equal to the convex hull of (x,y) if (and only if) 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.

Theorem[2] -- Let K be a non-empty convex subset of a vector space X and let p∈K. Then the following statements are equivalent:

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

## 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] Any open interval in ℝ has no extreme points while any non-degenerate closed interval not equal to ℝ does have extreme points (that is, the closed interval's endpoint(s)). More generally, any open subset of finite-dimensional Euclidean space ℝn has no extreme points.

The extreme points of the closed unit disk in ℝ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 ℝ2 are the extreme points of that polygon.

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(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 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 S is convex and compact in a locally convex topological vector space, then 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 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.[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 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 is immediate. 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 - 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.00 2.01 2.02 2.03 2.04 2.05 2.06 2.07 2.08 2.09 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=176779"
*[v]: View this template
*[t]: Discuss this template
*[e]: Edit this template