Extreme point

From Wikipedia, the free encyclopedia
Jump to navigation Jump to search
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 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[edit]

Throughout, it is assumed that S is a real or complex vector space.

For any x, x1, x2S, say that x lies between[2] x1 and x2 if x1x2 and there exists a 0 < t < 1 such that x = tx1 + (1 − t)x2.

If K is a subset of S and xK, then x 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 x1, x2K and 0 < t < 1 such that x1x2 and x = tx1 + (1 − t) x2. The set of all extreme points of K is denoted by extreme(K).

Characterizations[edit]

The midpoint[2] of two elements x and y in a vector space is the vector 1/2(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 xy.[2] The points x and y are called 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, yK, 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 pF 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 pK. Then the following 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, yK, if p ∈ [x, y] then x = p or y = p;
  5. if xX is such that both p + x and px belong to K, then x = 0;
  6. { p } is a face of K.

Examples[edit]

  • 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 : XY sends the extreme points of a convex set CX 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[edit]

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[edit]

Krein–Milman theorem[edit]

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[edit]

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[edit]

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[edit]

Citations[edit]

  1. ^ Saltzman, Matthew. "What is the difference between corner points and extreme points in linear programming problems?".
  2. ^ a b c d e f g h i j Narici & Beckenstein 2011, pp. 275-339.
  3. ^ 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.
  4. ^ Edgar GA. A noncompact Choquet theorem. Proceedings of the American Mathematical Society. 1975;49(2):354-8.

Bibliography[edit]