Extreme point

Last updated
A convex set in light blue, and its extreme points in red. Extreme points.svg
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]

Contents

Definition

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

For any x, x1, x2S, say that xlies 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

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

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

Citations

    1. Saltzman, Matthew. "What is the difference between corner points and extreme points in linear programming problems?".
    2. 1 2 3 4 5 6 7 8 9 10 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

    Related Research Articles

    Compact space Topological notions of all points being "close"

    In mathematics, more specifically in general topology, compactness is a property that generalizes the notion of a subset of Euclidean space being closed and bounded. Examples include a closed interval, a rectangle, or a finite set of points. This notion is defined for more general topological spaces than Euclidean space in various ways.

    Convex set In geometry, set that intersects every line into a single line segment

    In geometry, a subset of a Euclidean space, or more generally an affine space over the reals, is convex if, given any two points, it contains the whole line segment that joins them. Equivalently, a convex set or a convex region is a subset that intersects every line into a single line segment . For example, a solid cube is a convex set, but anything that is hollow or has an indent, for example, a crescent shape, is not convex.

    The Hahn–Banach theorem is a central tool in functional analysis. It allows the extension of bounded linear functionals defined on a subspace of some vector space to the whole space, and it also shows that there are "enough" continuous linear functionals defined on every normed vector space to make the study of the dual space "interesting". Another version of the Hahn–Banach theorem is known as the Hahn–Banach separation theorem or the hyperplane separation theorem, and has numerous uses in convex geometry.

    In mathematics, a topological vector space is one of the basic structures investigated in functional analysis. A topological vector space is a vector space which is also a topological space, this implies that vector space operations be continuous functions. More specifically, its topological space has a uniform topological structure, allowing a notion of uniform convergence.

    In mathematics, a topological space is said to be a Baire space, if for any given countable collection of closed sets with empty interior in , their union also has empty interior in . Equivalently, a locally convex space which is not meagre in itself is called a Baire space. According to Baire category theorem, compact Hausdorff spaces and complete metric spaces are examples of a Baire space. Bourbaki coined the term "Baire space".

    In functional analysis and related areas of mathematics, Fréchet spaces, named after Maurice Fréchet, are special topological vector spaces. They are generalizations of Banach spaces. All Banach and Hilbert spaces are Fréchet spaces. Spaces of infinitely differentiable functions are typical examples of Fréchet spaces, many of which are typically not Banach spaces.

    In mathematical analysis, a family of functions is equicontinuous if all the functions are continuous and they have equal variation over a given neighbourhood, in a precise sense described herein. In particular, the concept applies to countable families, and thus sequences of functions.

    Closed graph theorem

    In mathematics, the closed graph theorem is a basic result which characterizes continuous functions in terms of their graphs. In particular, they give conditions when functions with closed graphs are necessarily continuous. In mathematics, there are several results known as the "closed graph theorem".

    In functional analysis and related areas of mathematics, locally convex topological vector spaces (LCTVS) or locally convex spaces are examples of topological vector spaces (TVS) that generalize normed spaces. They can be defined as topological vector spaces whose topology is generated by translations of balanced, absorbent, convex sets. Alternatively they can be defined as a vector space with a family of seminorms, and a topology can be defined in terms of that family. Although in general such spaces are not necessarily normable, the existence of a convex local base for the zero vector is strong enough for the Hahn–Banach theorem to hold, yielding a sufficiently rich theory of continuous linear functionals.

    In functional analysis and related areas of mathematics an absorbing set in a vector space is a set S which can be "inflated" or "scaled up" to eventually always include any given point of the vector space. Alternative terms are radial or absorbent set.

    In functional analysis and related areas of mathematics, a barrelled space is a topological vector space (TVS) for which every barrelled set in the space is a neighbourhood for the zero vector. A barrelled set or a barrel in a topological vector space is a set that is convex, balanced, absorbing, and closed. Barrelled spaces are studied because a form of the Banach–Steinhaus theorem still holds for them.

    In linear algebra and related areas of mathematics a balanced set, circled set or disk in a vector space is a set such that for all scalars satisfying

    In functional analysis and related areas of mathematics, a Montel space, named after Paul Montel, is any topological vector space (TVS) in which an analog of Montel's theorem holds. Specifically, a Montel space is a barrelled topological vector space in which every closed and bounded subset is compact.

    In mathematical analysis, the Kakutani fixed-point theorem is a fixed-point theorem for set-valued functions. It provides sufficient conditions for a set-valued function defined on a convex, compact subset of a Euclidean space to have a fixed point, i.e. a point which is mapped to a set containing it. The Kakutani fixed point theorem is a generalization of Brouwer fixed point theorem. The Brouwer fixed point theorem is a fundamental result in topology which proves the existence of fixed points for continuous functions defined on compact, convex subsets of Euclidean spaces. Kakutani's theorem extends this to set-valued functions.

    In mathematics, a nuclear space is a topological vector space that can be viewed as a generalization of finite dimensional Euclidean spaces that is different from Hilbert spaces. Nuclear spaces have many of the desirable properties of finite-dimensional vector spaces. The topology on them can be defined by a family of seminorms whose unit balls decrease rapidly in size. Vector spaces whose elements are "smooth" in some sense tend to be nuclear spaces; a typical example of a nuclear space is the set of smooth functions on a compact manifold.

    Krein–Milman theorem On when a space equals the closed convex hull of its extreme points

    In the mathematical theory of functional analysis, the Krein–Milman theorem is a proposition about compact convex sets in locally convex topological vector spaces (TVSs).

    Convex cone subset of a vector space closed under positive linear combinations

    In linear algebra, a convex cone is a subset of a vector space over an ordered field that is closed under linear combinations with positive coefficients.

    In mathematics, particularly in functional analysis, a webbed space is a topological vector space designed with the goal of allowing the results of the open mapping theorem and the closed graph theorem to hold for a wider class of linear maps whose codomains are webbed spaces. A space is called webbed if there exists a collection of sets, called a web that satisfies certain properties. Webs were first investigated by de Wilde.

    F. Riesz's theorem is an important theorem in functional analysis that states that a Hausdorff topological vector space (TVS) is finite-dimensional if and only if it is locally compact. The theorem and its consequences are used ubiquitously in functional analysis, often used without being explicitly mentioned.

    In mathematics, particularly in functional analysis and topology, the closed graph theorem is a fundamental result stating that a linear operator with a closed graph will, under certain conditions, be continuous. The original result has been generalized many times so there are now many theorems referred to as "closed graph theorems."