Fact-checked by Grok 2 weeks ago

Extreme point

In , an extreme point of a C in a is defined as a point x \in C that cannot be written as a x = \theta y + (1 - \theta) z for any \theta \in (0,1) and distinct points y, z \in C. This means extreme points lie on the "boundary" of the set in a strong sense, as they are not interior to any contained within C. Extreme points play a fundamental role in the structure of convex sets, particularly through the Krein–Milman theorem, which asserts that every nonempty compact convex subset of a locally convex topological vector space is the closure of the convex hull of its extreme points. This theorem, originally established by Mark Kreĭn and David Milman in 1940, highlights how extreme points "generate" the entire set via convex combinations, and it extends earlier ideas from Hermann Minkowski on finite-dimensional cases. In finite dimensions, such as \mathbb{R}^n, the set of extreme points E(C) may be finite (e.g., the vertices of a polytope like a simplex or hypercube) or infinite (e.g., the entire boundary sphere of a ball). Notably, E(C) is not always closed, as demonstrated by certain pathological sets in \mathbb{R}^3 where extreme points include a circle and isolated points but exclude limit points. The concept is pivotal in optimization, especially , where the defined by linear inequalities forms a , and the optimal value of a linear objective function over this region is attained at an extreme point (a ). By the Minkowski–Carathéodory theorem, any point in a compact of n can be expressed as a of at most n+1 extreme points, limiting the complexity of such representations. These properties underpin algorithms like the simplex method and broader applications in , , and .

Definition

Formal Definition

In the context of convex analysis, an extreme point of a convex set K in a real is a point p \in K that cannot be expressed as a nontrivial of two distinct points in K. Formally, whenever p = t x + (1 - t) y for some x, y \in K and t \in (0, 1), it must hold that x = y = p. The collection of all extreme points of K is commonly denoted by \ext(K) or \extreme(K). This definition applies to convex sets in topological vector spaces more generally, capturing the geometric intuition that extreme points are the "corners" of K, lying on the boundary and not in the relative interior of any line segment entirely contained within K. The concept originates from Hermann Minkowski's foundational work on bodies at the turn of the , which formalized the generalization of vertices from finite-dimensional polytopes to arbitrary sets in higher dimensions.

Characterizations

In convex analysis, a point p \in K, where K is a convex subset of an , is characterized algebraically as extreme if and only if, for any x, y \in K and scalars \alpha, \beta > 0 with \alpha + \beta = 1, the equation p = \alpha x + \beta y implies x = y = p. This condition ensures that p cannot be expressed as a nontrivial of distinct points in K. To derive this from the formal definition of an extreme point (a point not in the relative interior of any in K), suppose for contradiction that p = \alpha x + \beta y with \alpha, \beta > 0, \alpha + \beta = 1, and say x \neq p. Then p lies in the open segment joining x and y, both in K, contradicting extremality; the converse follows similarly by showing any such combination places p in the relative interior. These algebraic properties hold in any , independent of . Geometrically, p is extreme if, for every line \ell through p, the intersection K \cap \ell is a interval having p as an —such as the \{p\}, a half-line starting at p, or a closed with p as one —but never an interval with p in its relative interior. This captures the intuitive notion that extreme points are "corners" where the set does not extend symmetrically in both directions along any line. The equivalence to the algebraic follows by noting that a containing p in its relative interior would yield a nontrivial , while an interval with p as prevents this. In the setting of normed spaces, an analytic characterization states that p \in K is extreme if there exists no d \neq 0 such that both p + \epsilon d and p - \epsilon d lie in K for some \epsilon > 0. This condition verifies extremality by checking local along directions, aiding computational methods in finite dimensions where one can test small perturbations. The proof of relies on contradiction: if such a d exists, then p is the midpoint of the segment from p - \epsilon d to p + \epsilon d, both in K, implying a nontrivial ; conversely, any nontrivial combination induces such a direction. Like the others, this holds without invoking or of the .

Examples

Finite-Dimensional Cases

In finite-dimensional Euclidean spaces, extreme points of convex sets provide intuitive geometric illustrations of points that cannot be expressed as nontrivial convex combinations of other points in the set. Consider the simplest case in \mathbb{R}: the closed interval [a, b] with a < b. Its extreme points are precisely the endpoints a and b, as any interior point can be written as a convex combination of these endpoints, while the endpoints themselves cannot. In contrast, the open interval (a, b) contains no extreme points, since every point therein is an interior point of some line segment within the set. In \mathbb{R}^2, the unit disk \{ x : \|x\| \leq 1 \} exemplifies a convex set with infinitely many extreme points, which form the boundary circle \{ x : \|x\| = 1 \}. Each point on this circle cannot be expressed as a convex combination of distinct points inside or on the disk without being one of the endpoints of the segment, whereas any interior point is a strict convex combination of boundary points. For a convex polygon in \mathbb{R}^2, such as a triangle or square, the extreme points are exactly the vertices; points on the edges are convex combinations of adjacent vertices, and interior points are combinations of multiple vertices. This pattern extends to convex polytopes in \mathbb{R}^n, where extreme points are the vertices, and higher-dimensional faces (edges, facets) consist of convex combinations of those vertices. The standard n-simplex in \mathbb{R}^n, defined as \Delta^n = \{ x \in \mathbb{R}^{n+1}_{\geq 0} : \sum_{i=1}^{n+1} x_i = 1 \} (embedded in \mathbb{R}^n), has exactly n+1 extreme points, corresponding to the standard basis vectors e_1, \dots, e_{n+1}. Every other point in the simplex is a convex combination of these vertices, highlighting the minimal structure that generates the entire set. This finite number of extreme points underscores the compactness and boundedness of polytopal convex sets in finite dimensions. In the context of linear programming, the feasible region defined by linear inequalities forms a convex polyhedron in \mathbb{R}^n, and its extreme points correspond precisely to the basic feasible solutions—points where at least n constraints are active (tight) and the corresponding basis matrix is invertible. Optimal solutions to linear programs over such polyhedra occur at these extreme points, enabling algorithms like the simplex method to traverse vertices efficiently.

Infinite-Dimensional Cases

In infinite-dimensional Banach spaces, the set of extreme points of the closed unit ball often exhibits behaviors distinct from finite-dimensional cases, such as being infinite or uncountable, and may fail to be closed in the norm topology, complicating geometric analysis. These features arise due to the lack of compactness in the norm topology and the presence of non-strict convexity. In the sequence space \ell^1 of absolutely summable real sequences with the \ell^1-norm, the extreme points of the closed unit ball consist precisely of the signed standard basis vectors \pm e_n for n \in \mathbb{N}, where e_n has a 1 in the n-th position and 0s elsewhere. These points correspond to the "atoms" of the space, and there are countably infinitely many, contrasting with the finite number in finite-dimensional \ell^1_n spaces. In the dual space \ell^\infty of bounded real sequences with the sup-norm, the extreme points of the closed unit ball are the sequences x = (x_k)_{k=1}^\infty such that x_k = \pm 1 for every k. This set is uncountable (homeomorphic to the Cantor set) and forms a non-compact "boundary" in the norm topology, though the unit ball is compact in the weak* topology. Unlike finite-dimensional analogues, the convex hull of these extremes does not yield the entire ball in the norm closure, but does in the weak* closure by the Krein–Milman theorem. The set \mathcal{P}(K) of regular Borel probability measures on a compact Hausdorff space K, viewed as a convex subset of the dual of C(K) with the weak* topology, has extreme points consisting of the Dirac delta measures \delta_x for x \in K. In particular, when K itself is the closed unit ball of a finite-dimensional space (e.g., a polytope), the extremes of \mathcal{P}(K) align with Diracs at the vertices of K, extending the finite-dimensional polytope example to measures. However, for general compact K, the extremes are all Diracs, uncountably many if K is uncountable. In the space C[0,1] of continuous real functions on [0,1] with the supremum norm, the extreme points of the closed unit ball are solely the constant functions f \equiv 1 and f \equiv -1. No other functions achieve extremality, as any non-constant f with \|f\|_\infty = 1 can be expressed as a nontrivial convex combination of distinct functions in the ball (e.g., by perturbing where |f| < 1). This scarcity underscores non-strict convexity, where most boundary points (e.g., functions attaining \pm 1 at some points but not constantly) are not extreme, unlike the fuller boundary in strictly convex spaces.

Properties

Algebraic Properties

The set of extreme points of a convex set K, denoted \operatorname{ext}(K), is generally not convex. For instance, consider the unit square [0,1]^2; its extreme points are the four vertices (0,0), (1,0), (0,1), and (1,1), but the midpoint (0.5,0) of the edge between (0,0) and (1,0) lies in the convex hull of these vertices yet is not itself an extreme point, as it can be expressed as a nontrivial convex combination of points in K. Extreme points are preserved under affine bijections. Specifically, if f is an affine bijection from the ambient space to itself and p \in \operatorname{ext}(K), then f(p) \in \operatorname{ext}(f(K)), since any convex combination representation would contradict the extremality of p via the affine linearity of f. This property facilitates reductions in optimization problems by transforming sets while maintaining their extremal structure. For a compact convex set K in a locally convex topological vector space, the convex hull of \operatorname{ext}(K) is dense in K, though it may not equal K without taking the closure; the full set K is the closed convex hull of its extreme points, as established by the . Detailed proofs of this density and closure relation rely on the separation properties of the space but are deferred to the discussion of relevant theorems. An extreme point of K corresponds to a 0-dimensional face of K. More generally, the minimal faces of K are precisely the singletons consisting of extreme points, underscoring the algebraic role of extreme points as the "vertices" in the facial structure of convex sets.

Topological Properties

In compact convex sets within locally convex topological vector spaces, the set of extreme points, denoted \operatorname{ext}(K), is not necessarily closed in the relative topology. For instance, in finite-dimensional Euclidean spaces of dimension greater than 2, there exist compact convex sets where \operatorname{ext}(K) fails to be closed; a specific example involves the convex hull of a suitable sequence of points approaching a limit point that lies in the relative interior of a face rather than being extreme itself. In infinite-dimensional settings, such as certain Banach spaces, \operatorname{ext}(K) can exhibit even more complex topological behavior, including non-closedness, though in Hilbert spaces the closed unit ball provides a counterexample where \operatorname{ext}(K) coincides with the unit sphere, which is closed but whose exposed points (a dense subset) highlight subtleties in approximation properties. If nonempty, \operatorname{ext}(K) for a compact convex set K in a locally convex space inherits the Baire category property from the ambient space, meaning it is a Baire space in the subspace topology: the intersection of countably many dense open subsets is again dense. This ensures that \operatorname{ext}(K) cannot be written as a countable union of nowhere dense sets, providing robustness against certain pathological decompositions. In metrizable cases, \operatorname{ext}(K) is moreover a G_\delta set (countable intersection of open sets) in K, which aligns with its Baire structure and facilitates applications in descriptive set theory, such as homeomorphic embeddings of Polish spaces into such extreme point sets. In non-compact convex sets, such as open balls in normed spaces, \operatorname{ext}(K) is often empty, as every point lies in the relative interior of some line segment within K, precluding extremality. This emptiness persists even when the convex hull of a dense subset of K fills the space, illustrating how topological openness undermines the existence of boundary-like extremes despite the set's "fullness" in a density sense. For example, the open unit interval (0,1) has no extreme points, though its closure [0,1] does, with extremes at the endpoints. In metric spaces, extreme points of a convex set K admit a local characterization: a point x \in K is extreme if and only if for every \epsilon > 0, the intersection K \cap B(x, \epsilon) (where B(x, \epsilon) is the open \epsilon-ball centered at x) contains no nontrivial line segment having x in its relative interior. This metric condition operationalizes the global convex combination prohibition, allowing verification through small-scale geometric inspections without requiring compactness. Recent research since 2010 has extended such density considerations to weak topologies; for instance, in weak^*-closed convex sets of dual Banach spaces, exposed extreme points (those separated by continuous linear functionals) may be dense in \operatorname{ext}(K) under the weak^* topology, aiding representation theorems in non-normable settings.

Theorems

Krein–Milman Theorem

The asserts that if K is a nonempty compact subset of a Hausdorff locally topological vector space, then K equals the closure of the of its extreme points: K = \overline{\conv}(\ext(K)). This representation highlights the role of extreme points as the "vertices" generating the entire set under combinations and limits. The theorem was established by Mark Grégoire Krein and David Milman in their 1940 paper, where they extended earlier finite-dimensional insights to infinite-dimensional settings. It builds directly on Hermann Minkowski's 1911 result, which showed that in finite-dimensional spaces, every compact body is the of its extreme points without needing closure. The proof in the original work leverages separation properties and compactness in the , marking a foundational advance in . A standard proof begins by applying to the collection of closed faces of K, ordered by inclusion, to obtain a minimal nonempty closed face F. Any such minimal F must be a singleton and hence an extreme point, as otherwise it would contain a proper closed face by the Krein–Milman separation lemma or arguments. The set of all extreme points is nonempty due to , and ensures that the closed of \ext(K) coincides with K, often via showing that any point outside this hull can be separated by a continuous linear functional. Important corollaries include the existence of at least one extreme point in any nonempty compact , as an empty \ext(K) would imply K is empty. The theorem underpins Choquet theory, where every point in K admits a as the barycenter of a supported on \ext(K), known as Choquet's ; this strengthens the convex hull description to an form and applies to problems in and of linear functionals.

Results in Banach Spaces

In Banach spaces, the analysis of extreme points extends the classical Krein–Milman theorem to address challenges in infinite dimensions, particularly for non-compact sets, by incorporating geometric properties like the Radon-Nikodym property (RNP). A fundamental result, due to Joram Lindenstrauss, establishes that every nonempty closed bounded convex subset of a Banach space with the RNP contains at least one extreme point. This guarantees the existence of extreme points even without compactness, contrasting with the general locally convex case where such sets may lack them. Complementing this, Robert R. Phelps proved the full characterization: a Banach space has the RNP if and only if every closed bounded convex subset is the closed convex hull of its extreme points. These theorems link extremal structure to dentability—a property where sets can be "dented" by hyperplanes of arbitrary small width—and provide tools for integral representations in non-reflexive settings. Gerald A. advanced this framework with a non-compact analogue of Choquet's , applicable to separable closed bounded subsets of Banach spaces with the RNP. In dual Banach spaces, showed that every point admits an representation with respect to a supported on the extreme points, where the representing measures can be chosen via weak*-slices of the set. This result ties the closed of extreme points to dentability conditions: if a set is dentable, its slices contain extreme points densely, enabling such representations. 's implies stronger decomposition properties and has implications for measurability in Banach spaces, resolving questions about barycentric mappings in infinite dimensions. Extreme points of the unit ball also characterize key geometric features, such as strict convexity. A is strictly convex if and only if every point on the unit sphere is an extreme point of the closed unit ball. Equivalently, the unit ball contains no line segments on its . For instance, in the space \ell^1, the extreme points of the unit ball are precisely the vectors with a single coordinate of 1 and the rest zero, forming a set that does not cover the entire sphere, reflecting the lack of strict convexity. In contrast, Hilbert spaces are , so their unit spheres consist entirely of extreme points, with no extreme points in the open unit ball—a property holding trivially in any normed space, as interior points are convex combinations of nearby points. This characterization extends Mazur's lemma, which concerns weak closures of convex hulls, by highlighting how extremal points on the boundary detect uniformity in the . In operator algebras, extreme points of the unit ball in the play a crucial role in . For a unital , the extreme points of the state space (the set of positive linear functionals of norm 1) correspond exactly to the pure states. By the Gelfand-Naimark-Segal construction, these pure states induce irreducible representations of the algebra on Hilbert spaces, classifying the irreducible unitary representations via the extremal structure. This application underscores the utility of extreme points in decomposing states and understanding spectral properties beyond finite-dimensional geometry.

Related Concepts

k-Extreme Points

In , k-extreme points provide a generalization of extreme points to account for local dimensionality in . A point p \in K in a convex set K is k-extreme if it lies in the relative interior of some k-dimensional face of K, meaning the minimal face containing p has dimension k; equivalently, there do not exist k+1 linearly independent directions d_1, \dots, d_{k+1} such that p \pm d_i \in K for each i = 1, \dots, k+1. This formulation extends the standard case, where 0-extreme points are the usual extreme points corresponding to 0-dimensional faces (vertices). In finite-dimensional polytopes, k-extreme points consist of all points in the relative interiors of the k-faces. These points capture the "local extremality" within their supporting k-dimensional structure but may not be globally extreme. For instance, in a 3-dimensional , the 1-extreme points include midpoints of the , which are extreme relative to the 1-dimensional edge faces containing them but lie in combinations of global extreme points (vertices). The collection of k-extreme points is intimately connected to the facial decomposition of the . Specifically, in polytopes, the convex hulls of lower-dimensional extreme points within each k-face fill the k-faces, and thus the k-extreme points, together with lower-order ones, generate the k-skeleton—the union of all k-dimensional faces—via affine spans and combinations. In infinite-dimensional settings, such as Banach spaces of measurable operators, k-extreme points extend this framework to characterize the orbital structure and boundary behavior of sets, relating to higher-order singularities where the set exhibits flatness or facial exposure in finite codimensions up to k. This connection aids in understanding non-strictly bodies and their decomposability properties.

Exposed Extreme Points

An exposed extreme point of a K in a is a point p \in K such that there exists a continuous linear functional f with f(p) = \sup_{x \in K} f(x) and p is the unique point in K achieving this supremum. This definition implies that the defined by f(x) = f(p) intersects K precisely at the \{p\}. Exposed extreme points form a of all extreme points, as the uniqueness condition ensures extremality: if p = \lambda x + (1-\lambda) y for x, y \in K and $0 < \lambda < 1, then applying f yields a unless x = y = p. In finite-dimensional spaces, not every extreme point need be exposed; for instance, the of a in \mathbb{R}^3 contains extreme points on the relative interiors of the top and bottom circular boundaries that lie in exposed faces (the disks) but are not themselves exposed. However, for polytopes in finite dimensions, every extreme point is exposed, as all faces are exposed faces. In general, for a closed , the exposed extreme points are dense in the set of extreme points by Straszewicz's theorem. In infinite-dimensional spaces, the inclusion can be strict, with examples in certain Banach spaces where some extreme points lack unique supporting functionals. This notion is equivalent to p being the sole intersection point of K with a at p, distinguishing it from broader extreme points that may share supporting hyperplanes with positive-dimensional faces. In optimization, exposed extreme points facilitate algorithms like the method for linear programs over polytopes, where vertices—being exposed—can be enumerated or pivoted to via basis exchanges to reach optima. In duality theory, the presence of exposed points aids in verifying conditions, as unique maximizers of functionals correspond to exposed points, ensuring no under constraint qualifications.