View source for Extreme point

{{short description|Point not between two other points}}
{{Other uses}}

[[Image:Extreme points.svg|thumb|right|A convex set in light blue, and its extreme points in red.]]

In [[mathematics]], an '''extreme point''' of a [[convex set]] <math>S</math> in a [[Real number|real]] or [[Complex number|complex]] [[vector space]] is a point in <math>S</math> that does not lie in any open [[line segment]] joining two points of <math>S.</math> In [[linear programming]] problems, an extreme point is also called vertex or corner point of <math>S.</math><ref>{{Cite web|url=https://www.quora.com/What-is-the-difference-between-corner-points-and-extreme-points-in-linear-programming-problems|title=What is the difference between corner points and extreme points in linear programming problems?|last=Saltzman|first=Matthew}}</ref>

==Definition==

Throughout, it is assumed that <math>X</math> is a [[Real number|real]] or [[Complex number|complex]] [[vector space]]. 

For any <math>p, x, y \in X,</math> say that <math>p</math> '''{{visible anchor|lies between}}'''{{sfn|Narici|Beckenstein|2011|pp=275-339}} <math>x</math> and <math>y</math> if <math>x \neq y</math> and there exists a <math>0 < t < 1</math> such that <math>p = t x + (1-t) y.</math>

If <math>K</math> is a subset of <math>X</math> and <math>p \in K,</math> then <math>p</math> is called an '''{{visible anchor|extreme point}}'''{{sfn|Narici|Beckenstein|2011|pp=275-339}} of <math>K</math> if it does not lie between any two {{em|distinct}} points of <math>K.</math> That is, if there does {{em|not}} exist <math>x, y \in K</math> and <math>0 < t < 1</math> such that <math>x \neq y</math> and <math>p = t x + (1-t) y.</math> The set of all extreme points of <math>K</math> is denoted by <math>\operatorname{extreme}(K).</math>

'''Generalizations'''

If <math>S</math> is a subset of a vector space then a linear sub-variety (that is, an [[affine subspace]]) <math>A</math> of the vector space is called a {{em|{{visible anchor|support variety}}}} if <math>A</math> meets <math>S</math> (that is, <math>A \cap S</math> is not empty) and every open segment <math>I \subseteq S</math> whose interior meets <math>A</math> is necessarily a subset of <math>A.</math>{{sfn|Grothendieck|1973|p=186}} A 0-dimensional support variety is called an extreme point of <math>S.</math>{{sfn|Grothendieck|1973|p=186}}

===Characterizations===

The '''{{visible anchor|midpoint}}'''{{sfn|Narici|Beckenstein|2011|pp=275-339}} of two elements <math>x</math> and <math>y</math> in a vector space is the vector <math>\tfrac{1}{2}(x+y).</math>

For any elements <math>x</math> and <math>y</math> in a vector space, the set <math>[x, y] = \{t x + (1-t) y : 0 \leq t \leq 1\}</math> is called the '''{{visible anchor|closed line segment}}''' or '''{{visible anchor|closed interval}}''' between <math>x</math> and <math>y.</math> The '''{{visible anchor|open line segment}}''' or '''{{visible anchor|open interval}}''' between <math>x</math> and <math>y</math> is <math>(x, x) = \varnothing</math> when <math>x = y</math> while it is <math>(x, y) = \{t x + (1-t) y : 0 < t < 1\}</math> when <math>x \neq y.</math>{{sfn|Narici|Beckenstein|2011|pp=275-339}} The points <math>x</math> and <math>y</math> are called the '''{{visible anchor|endpoints}}''' of these interval. An interval is said to be a '''{{visible anchor|non−degenerate interval}}''' or a '''{{visible anchor|proper interval}}''' if its endpoints are distinct. The '''{{visible anchor|midpoint of an interval}}''' is the midpoint of its endpoints. 

The closed interval <math>[x, y]</math> is equal to the [[convex hull]] of <math>(x, y)</math> if (and only if) <math>x \neq y.</math> So if <math>K</math> is convex and <math>x, y \in K,</math> then <math>[x, y] \subseteq K.</math> 

If <math>K</math> is a nonempty subset of <math>X</math> and <math>F</math> is a nonempty subset of <math>K,</math> then <math>F</math> is called a '''{{visible anchor|face}}'''{{sfn|Narici|Beckenstein|2011|pp=275-339}} of <math>K</math> if whenever a point <math>p \in F</math> lies between two points of <math>K,</math> then those two points necessarily belong to <math>F.</math>

{{Math theorem|name=Theorem{{sfn|Narici|Beckenstein|2011|pp=275-339}}|math_statement=
Let <math>K</math> be a non-empty convex subset of a vector space <math>X</math> and let <math>p \in K.</math> 
Then the following statements are equivalent:
<ol>
<li><math>p</math> is an extreme point of <math>K.</math></li>
<li><math>K \setminus \{p\}</math> is convex.</li>
<li><math>p</math> is not the midpoint of a non-degenerate line segment contained in <math>K.</math></li>
<li>for any <math>x, y \in K,</math> if <math>p \in [x, y]</math> then <math>x = p \text{ or } y = p.</math></li>
<li>if <math>x \in X</math> is such that both <math>p + x</math> and <math>p - x</math> belong to <math>K,</math> then <math>x = 0.</math></li>
<li><math>\{p\}</math> is a face of <math>K.</math></li>
</ol>
}}

==Examples==

If <math>a < b</math> are two real numbers then <math>a</math> and <math>b</math> are extreme points of the interval <math>[a, b].</math> However, the open interval <math>(a, b)</math> has no extreme points.{{sfn |Narici|Beckenstein|2011|pp=275-339}} 
Any [[open interval]] in <math>\R</math> has no extreme points while any non-degenerate [[closed interval]] not equal to <math>\R</math> does have extreme points (that is, the closed interval's endpoint(s)).  More generally, any [[Open set|open subset]] of finite-dimensional [[Euclidean space]] <math>\R^n</math> has no extreme points.

The extreme points of the [[closed unit disk]] in <math>\R^2</math> is the [[unit circle]]. 

The perimeter of any convex polygon in the plane is a face of that polygon.{{sfn|Narici|Beckenstein|2011|pp=275-339}} 
The vertices of any convex polygon in the plane <math>\R^2</math> are the extreme points of that polygon. 

An injective linear map <math>F : X \to Y</math> sends the extreme points of a convex set <math>C \subseteq X</math> to the extreme points of the convex set <math>F(X).</math>{{sfn|Narici|Beckenstein|2011|pp=275-339}} 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 {{em|fail}} to be closed in <math>X.</math>{{sfn|Narici|Beckenstein|2011|pp=275-339}}

==Theorems==

===Krein–Milman theorem===

The [[Krein–Milman theorem]] is arguably one of the most well-known theorems about extreme points. 

{{Math theorem|name=[[Krein–Milman theorem]]|math_statement=
If <math>S</math> is convex and [[Compact space|compact]] in a [[locally convex topological vector space]], then <math>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 space]]s with the [[Radon–Nikodym property]]. 

A theorem of [[Joram Lindenstrauss]] states that, in a Banach space with the Radon–Nikodym property, a nonempty [[closed set|closed]] and [[bounded set]] has an extreme point. (In infinite-dimensional spaces, the property of [[compact space|compactness]] is stronger than the joint properties of being closed and being bounded.<ref>{{cite journal|last=Artstein|first=Zvi|title=Discrete&nbsp;and&nbsp;continuous bang-bang and facial&nbsp;spaces, or: Look for the extreme points|journal=SIAM Review|volume=22|year=1980|number=2|pages=172–185|doi=10.1137/1022026|mr=564562|jstor=2029960}}</ref>)

{{Math theorem|name=Theorem|note=[[Gerald Edgar]]|math_statement=
Let <math>E</math> be a Banach space with the Radon–Nikodym property, let <math>C</math> be a separable, closed, bounded, convex subset of <math>E,</math> and let <math>a</math> be a point in <math>C.</math> Then there is a [[probability measure]] <math>p</math> on the universally measurable sets in <math>C</math> such that <math>a</math> is the [[barycenter]] of <math>p,</math> and the set of extreme points of <math>C</math> has <math>p</math>-measure 1.<ref>Edgar GA. [https://www.ams.org/journals/proc/1975-049-02/S0002-9939-1975-0372586-2/S0002-9939-1975-0372586-2.pdf A noncompact Choquet theorem.] Proceedings of the American Mathematical Society. 1975;49(2):354–8.</ref>
}}

Edgar’s theorem implies Lindenstrauss’s theorem.

==Related notions==

A closed convex subset of a [[topological vector space]] is called {{em|[[Strictly convex set|strictly convex]]}} if every one of its [[Boundary (topology)|(topological) boundary points]] is an extreme point.{{sfn|Halmos|1982|p=5}} The [[unit ball]] of any [[Hilbert space]] is a strictly convex set.{{sfn|Halmos|1982|p=5}}

===''k''-extreme points===

More generally, a point in a convex set <math>S</math> is '''<math>k</math>-extreme''' if it lies in the interior of a <math>k</math>-dimensional convex set within <math>S,</math> but not a <math>k + 1</math>-dimensional convex set within <math>S.</math>  Thus, an extreme point is also a <math>0</math>-extreme point.  If <math>S</math> is a polytope, then the <math>k</math>-extreme points are exactly the interior points of the <math>k</math>-dimensional faces of <math>S.</math>  More generally, for any convex set <math>S,</math> the <math>k</math>-extreme points are partitioned into <math>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>k</math>-extreme points.  If <math>S</math> is closed, bounded, and <math>n</math>-dimensional, and if <math>p</math> is a point in <math>S,</math> then <math>p</math> is <math>k</math>-extreme for some <math>k \leq n.</math>  The theorem asserts that <math>p</math> is a convex combination of extreme points.  If <math>k = 0</math> then it is immediate.  Otherwise <math>p</math> lies on a line segment in <math>S</math> which can be maximally extended (because <math>S</math> is closed and bounded).  If the endpoints of the segment are <math>q</math> and <math>r,</math> then their extreme rank must be less than that of <math>p,</math> and the theorem follows by induction.

==See also==
* [[Extreme set]]
* [[Exposed point]]
* {{annotated link|Choquet theory}}
* [[Bang–bang control]]<ref>{{cite journal|last=Artstein|first=Zvi|title=Discrete&nbsp;and&nbsp;continuous bang-bang and facial&nbsp;spaces, or: Look for the extreme points|journal=SIAM Review|volume=22|year=1980|number=2|pages=172–185|doi=10.1137/1022026|jstor=2029960 |mr=564562}}</ref>

==Citations==

{{reflist|group=note}}

{{reflist}}

==Bibliography==

* {{Adasch Topological Vector Spaces|edition=2}} <!--{{sfn|Adasch|Ernst|Keim|1978|p=}}-->
* {{Bourbaki Topological Vector Spaces Part 1 Chapters 1–5}} <!--{{sfn|Bourbaki|1987|p=}}-->
* {{cite web|editor=Paul E. Black|date=2004-12-17|title=extreme point|url=https://xlinux.nist.gov/dads/HTML/extremepoint.html|work=[[Dictionary of algorithms and data structures]]|publisher=US [[National institute of standards and technology]]|access-date=2011-03-24}}
* {{cite encyclopedia|last1=Borowski|first1=Ephraim J.|last2=Borwein|first2=Jonathan M.|year=1989|article=extreme point|encyclopedia=Dictionary of mathematics|series=Collins dictionary|publisher=[[HarperCollins]]|isbn=0-00-434347-6}}
* {{Grothendieck Topological Vector Spaces}} <!--{{sfn|Grothendieck|1973|p=}}-->
* {{Halmos A Hilbert Space Problem Book 1982}} <!--{{sfn|Halmos|1982|pp=}}-->
* {{Jarchow Locally Convex Spaces}} <!--{{sfn|Jarchow|1981|p=}}-->
* {{Köthe Topological Vector Spaces I}} <!--{{sfn|Köthe|1983|p=}}-->
* {{Köthe Topological Vector Spaces II}} <!--{{sfn|Köthe|1979|p=}}-->
* {{Narici Beckenstein Topological Vector Spaces|edition=2}} <!--{{sfn|Narici|Beckenstein|2011|p=}}-->
* {{Robertson Topological Vector Spaces}} <!--{{sfn|Robertson|Robertson|1980|p=}}-->
* {{Rudin Walter Functional Analysis|edition=2}} <!--{{sfn|Rudin|1991|p=}}-->
* {{Schaefer Wolff Topological Vector Spaces|edition=2}} <!--{{sfn|Schaefer|Wolff|1999|p=}}-->
* {{Schechter Handbook of Analysis and Its Foundations}} <!--{{sfn|Schechter|1996|p=}}-->
* {{Trèves François Topological vector spaces, distributions and kernels}} <!--{{sfn|Trèves|2006|p=}}-->
* {{Wilansky Modern Methods in Topological Vector Spaces|edition=1}} <!--{{sfn|Wilansky|2013|p=}}-->

{{Functional analysis}}
{{Topological vector spaces}}

[[Category:Convex geometry]]
[[Category:Convex hulls]]
[[Category:Functional analysis]]
[[Category:Mathematical analysis]]