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]
Definition
Throughout, we assume that X is a real or complex vector space.
Definition:[2] For any p, x, y ∈ X, say that p lies between x and y if x ≠ y and there exists a 0 < t < 1 such that p = tx + (1 - t)y.
Definition:[2] If K is a subset of X and p ∈ K, then p is called an extreme point 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).
Characterizations
Definition:[2] The midpoint of two elements x and y in a vector space is the vector 1/2(x + y).
Definition:[2] 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. We call x and y the endpoints of these interval. An interval is said to be non-degenerate or proper if its endpoints are distinct. The midpoint of an interval is the midpoint of its endpoints.
Note that [x, y] is equal to the convex hull of {x, y} so if K is convex and x, y ∈ K, then [x, y] ⊆ K.
Definition:[2] If K is a nonempty subset of X and F is a nonempty subset of K, then F is called a face 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 are equivalent:
p is an extreme point of K;
K ∖ { p } is convex;
p is not the midpoint of a non-degenerate line segment contained in K;
for any x, y ∈ K, if p ∈ [x, y] then x = y = p;
if x ∈ X is such that both p + x and p - x belong to K, then x = 0;
{ 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]
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(C).[2] This is also true for injective affine maps.
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.
The extreme points of the closed unit disk in ℝ2 is the unit circle.
Any open interval in ℝ has no extreme points while any non-degenerate closed interval not equal to ℝ does have extreme points (i.e. the closed interval's endpoint(s)).
More generally, any open subset of finite-dimensional Euclidean space ℝn has no extreme points.
Properties
The extreme points of a compact convex 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 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).[3]
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.[4]
Edgar's theorem implies Lindenstrauss's theorem.
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'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
Choquet theory
References
Saltzman, Matthew. "What is the difference between corner points and extreme points in linear programming problems?".
Narici & Beckenstein 2011, pp. 275-339.
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.
Bibliography
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.
Rudin, Walter (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.
Narici, Lawrence; Beckenstein, Edward (2011). Topological Vector Spaces. Pure and applied mathematics (Second ed.). Boca Raton, FL: CRC Press. ISBN 978-1584888666. OCLC 144216834.
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.
Trèves, François (2006) [1967]. Topological Vector Spaces, Distributions and Kernels. Mineola, N.Y.: Dover Publications. ISBN 978-0-486-45352-1. OCLC 853623322.
Functional analysis (topics – glossary)
Spaces
Hilbert space Banach space Fréchet space topological vector space
Theorems
Hahn–Banach theorem closed graph theorem uniform boundedness principle Kakutani fixed-point theorem Krein–Milman theorem min-max theorem Gelfand–Naimark theorem Banach–Alaoglu theorem
Operators
bounded operator compact operator adjoint operator unitary operator Hilbert–Schmidt operator trace class unbounded operator
Algebras
Banach algebra C*-algebra spectrum of a C*-algebra operator algebra group algebra of a locally compact group von Neumann algebra
Open problems
invariant subspace problem Mahler's conjecture
Applications
Besov space Hardy space spectral theory of ordinary differential equations heat kernel index theorem calculus of variation functional calculus integral operator Jones polynomial topological quantum field theory noncommutative geometry Riemann hypothesis
Advanced topics
locally convex space approximation property balanced set Schwartz space weak topology barrelled space Banach–Mazur distance Tomita–Takesaki theory
vte
Topological vector spaces (TVSs)
Basic concepts
Banach space Continuous linear operator Functionals Hilbert space Linear operators Locally convex space Homomorphism Topological vector space Vector space
Main results
Closed graph theorem F. Riesz's theorem Hahn–Banach (hyperplane separation Vector-valued Hahn–Banach) Open mapping (Banach–Schauder) (Bounded inverse) Uniform boundedness (Banach–Steinhaus)
Maps
Almost open Bilinear (form operator) and Sesquilinear forms Closed Compact operator Continuous and Discontinuous Linear maps Densely defined Homomorphism Functionals Norm Operator Seminorm Sublinear Transpose
Types of sets
Absolutely convex/disk Absorbing/Radial Affine Balanced/Circled Banach disks Bounding points Bounded Complemented subspace Convex Convex cone (subset) Linear cone (subset) Extreme point Pre-compact/Totally bounded Radial Radially convex/Star-shaped Symmetric
Set operations
Affine hull (Relative) Algebraic interior (core) Convex hull Linear span Minkowski addition Polar (Quasi) Relative interior
Types of TVSs
Asplund B-complete/Ptak Banach (Countably) Barrelled (Ultra-) Bornological Brauner Complete (DF)-space Distinguished F-space Fréchet (tame Fréchet) Grothendieck Hilbert Infrabarreled Interpolation space LB-space LF-space Locally convex space Mackey (Pseudo)Metrizable Montel Quasibarrelled Quasi-complete Quasinormed (Polynomially Semi-) Reflexive Riesz Schwartz Semi-complete Smith Stereotype (B Strictly Uniformly convex (Quasi-) Ultrabarrelled Uniformly smooth Webbed With the approximation property
Undergraduate Texts in Mathematics
Graduate Studies in Mathematics
Hellenica World - Scientific Library
Retrieved from "http://en.wikipedia.org/"
All text is available under the terms of the GNU Free Documentation License
