Convex Sets and the Convex Hull

Introduction

A subset of a real vector space is convex when it contains the segment joining any two of its points, and the convex hull of a set is the smallest convex set containing it. Convexity is a structure of the affine geometry of a vector space, and it needs no distance: it is visible in the linear operations alone. The results of this article use a topology only where compactness is required, so the space is a real vector space, and, when a closure or a limit occurs, a locally convex space in the sense of Locally Convex Spaces.

The finite-dimensional calculus of convex sets — Carathéodory's bound, the relative interior, the nearest-point map, the support and separation theorems, polyhedra and the Minkowski–Weyl theorem — is developed in Convex Analysis, in the Foundations of Analysis category of this Part. That article is the owner of those results and they are cited here, not restated. What this article adds is the part of the theory that is not finite-dimensional: the convex hull read as a closure operator, the faces of a convex set, and the extreme points, whose theory culminates in the Krein–Milman theorem — a compact convex set is the closed convex hull of its extreme points — together with the converse of Milman. These are the objects on which the later articles of this category build: the extremal rays of a cone, the integral representation of Choquet, and the operators that a convex set carries.

The topology used is the one of Topological Modules and Vector Spaces and Locally Convex Spaces, the duality and the separation theorem are Duality Theory, and the order-theoretic vocabulary of a closure operator is Order Theory and Lattices. The article names the derivative and the measure, which are the instruments of this Part, only where a result of Convex Analysis uses them.

Convex Sets in a Vector Space

Definition and Elementary Properties

Let $E$ be a real vector space.

Definition. A subset $C\subseteq E$ is convex when

$$ (1-t)\,x + t\,y \in C \qquad \text{for all } x,y\in C \text{ and } t\in[0,1]. $$

A convex combination of a finite family $x_1,\dots,x_k$ is a sum $\sum_i t_i x_i$ with $t_i\geq0$ and $\sum_i t_i = 1$; a conical combination drops the condition on the sum, and an affine combination asks only that $\sum_i t_i = 1$. Convexity is exactly closure under convex combinations, proved by induction on the number of terms.

Proposition (elementary stability). The intersection of any family of convex sets is convex; the sum $C_1 + C_2$ and the image $T(C)$ under a linear map are convex; the product of convex sets is convex; and if $C$ is convex, $x\in C$ and $\lambda>0$ then $\lambda(C-x)$ is convex and contains the origin.

Proof. The intersection statement is immediate from the definition; a convex combination of points of $C_1+C_2$ splits according to the coefficient and reassembles; $T$ commutes with convex combinations; and the last statement is the invariance of convexity under an affine map.

The cone generated by a set $A$ is the set of conical combinations of points of $A$, and it is convex and closed under nonnegative scaling. The affine hull $\operatorname{aff}(A)$ is the set of affine combinations, the smallest affine subspace containing $A$; the convex hull is the next definition.

The Convex Hull

Definition. The convex hull of $A\subseteq E$ is

$$ \operatorname{conv}(A) = \Bigl\{\sum_{i=1}^{k} t_i a_i : k\geq1,\ a_i\in A,\ t_i\geq0,\ \sum_{i=1}^{k} t_i = 1\Bigr\}, $$

the set of all convex combinations of finite families of points of $A$.

Proposition (the hull is a convex set, and it is the least one). $\operatorname{conv}(A)$ is convex, contains $A$, and is contained in every convex set that contains $A$.

Proof. A convex combination of two convex combinations, with coefficient $t\in[0,1]$, is again a convex combination of points of $A$ after discarding the terms whose coefficient is zero, so the hull is convex; it contains $A$ through the one-term combinations; and any convex set containing $A$ contains every convex combination of its points, by induction on the number of terms, so it contains the hull.

Proposition (the operators). The maps $A\mapsto \operatorname{conv}(A)$, $A\mapsto \operatorname{aff}(A)$ and $A\mapsto \operatorname{cone}(A)$ are monotone and increasing. The convex hull is idempotent, $\operatorname{conv}(\operatorname{conv}(A)) = \operatorname{conv}(A)$, so it is a closure operator on the lattice of subsets of $E$ in the sense of Order Theory and Lattices; its fixed points are exactly the convex sets, and $\operatorname{conv}$ is the least closed set containing $A$.

Proof. Monotonicity and $A\subseteq\operatorname{conv}(A)$ are read off the definition; idempotence holds because a convex combination of convex combinations expands into a convex combination, using that a positive combination of nonnegative coefficients normalises; and a closure operator is characterised by these three properties, its fixed points being the sets equal to their hulls.

The closed convex hull $\overline{\operatorname{conv}}(A)$ is the closure of $\operatorname{conv}(A)$; in a topological vector space it is the least closed convex set containing $A$, and it is again a closure operator. The two operators differ as soon as the space is infinite-dimensional and not locally compact: the closed convex hull of a compact set need not be compact, and the closed convex hull of a convex set need not be closed.

Extreme Points and Faces

Definition. Let $C\subseteq E$ be convex. A point $x\in C$ is extreme when it is not the midpoint of two distinct points of $C$: if $x = \tfrac12(y+z)$ with $y,z\in C$, then $y = z = x$. The set of extreme points is written $\operatorname{ext}(C)$.

A subset $F\subseteq C$ is a face of $C$ when it is convex and satisfies the stronger condition: if $x = (1-t)y + tz \in F$ with $y,z\in C$ and $0 < t < 1$, then $y,z\in F$. A face is proper when $F\neq C$, and exposed when there is a continuous linear functional $f$ with $F = \{x\in C : f(x) = \sup_C f\}$.

Proposition. Every face of a convex set is convex; an intersection of faces is a face; the extreme points are exactly the singleton faces; and a face of a face is a face of the original set.

Proof. Convexity is part of the definition of a face, and the intersection of convex sets is convex; the face condition passes to the intersection. The second assertion is the unwinding of the definitions: a point is extreme exactly when the singleton consisting of it satisfies the face condition. For the third, the face condition for $F$ applied to a point of a face of $F$ is the face condition for the larger set, because the segments with endpoints in $C$ that meet $F$ at an interior point have their endpoints in $F$.

Proposition (a compact convex set has an extreme point). Let $K$ be a nonempty compact convex subset of a locally convex space. Then $\operatorname{ext}(K)\neq\emptyset$.

Proof. The family of nonempty compact subsets of $K$ that are faces of $K$ is nonempty (it contains $K$) and is ordered by inclusion; a chain has nonempty intersection by the finite intersection property of a compact set, and the intersection is a compact face, so the family has a maximal element $F$ by Zorn's lemma. A maximal compact face has no proper face other than the empty set. If $F$ contained two distinct points $x, y$, the separation theorem of Duality Theory would give a continuous functional $f$ not constant on $F$, and the set of points of $F$ where $f$ attains its maximum would be a nonempty proper face of $F$, a contradiction. Hence $F$ is a singleton, and its point is extreme in $K$.

The proof is the standard one; it uses the axiom of choice through Zorn's lemma and the separation theorem for a locally convex space. The finite-dimensional case is Convex Analysis.

The Krein–Milman Theorem

Theorem (Krein–Milman). Let $K$ be a compact convex subset of a locally convex space. Then

$$ K = \overline{\operatorname{conv}}\bigl(\operatorname{ext}(K)\bigr). $$

In particular a nonempty compact convex set has extreme points, and two compact convex sets with the same extreme points coincide.

Proof. The inclusion $\supseteq$ holds because $K$ is convex and closed and the extreme points lie in $K$. For the converse, suppose some point $a\in K$ were outside the closed convex subset $L = \overline{\operatorname{conv}}(\operatorname{ext} K)$. The separation theorem of Duality Theory would give a continuous linear functional $f$ with $f(a) > \sup_L f$; the set $F = \{x\in K : f(x) = \sup_K f\}$ is a nonempty compact face of $K$ and misses $L$, so it contains no extreme point of $K$. But by the previous proposition applied to $F$, which is compact convex, $F$ has an extreme point $x$; and $x$, being extreme in $F$, is extreme in $K$, a contradiction.

Theorem (Milman's converse). Let $K$ be a compact convex set and let $T\subseteq K$ satisfy $K = \overline{\operatorname{conv}}(T)$. Then every extreme point of $K$ lies in $\overline{T}$.

Proof sketch. Let $x\in\operatorname{ext}(K)$ and suppose $x\notin\overline{T}$. Separating $x$ from the closed convex set $\overline{\operatorname{conv}}(T) = K$ gives a continuous functional $f$ and a number $\alpha$ with $f(x) > \alpha > \sup_T f$. The set $F = \{y\in K : f(y) \geq \alpha\}$ is a nonempty compact face of $K$ disjoint from $T$, and $x\notin F$; the extreme points of $F$ are extreme in $K$ and are not in $\overline{T}$. Repeating the argument with $F$ in place of $K$, and iterating, produces a decreasing sequence of compact faces with extreme points progressively further from $\overline{T}$; the intersection of a maximal chain of such faces is a face whose extreme points are extreme in $K$ and lie in $\overline{T}$, contradicting the choice of $x$ above $\alpha$. The finite iteration carried out on the faces alone yields the claim.

The Finite-Dimensional Case

In $\mathbb{R}^n$ the separation theorem above is the supporting-hyperplane theorem, and compactness is local: a closed and bounded convex set is compact, its extreme points are the vertices it has, and the Krein–Milman theorem reduces to Minkowski's theorem, that a compact convex set is the convex hull of its extreme points. The bound on the number of points needed is Carathéodory's, $n+1$; both are Convex Analysis, together with the polyhedral case, in which the extreme points and the extreme rays are finite in number. In infinite dimension Carathéodory's bound fails, and the closure in the Krein–Milman statement cannot be removed in general.

Worked Cases

The Unit Ball of a Normed Space

Let $E$ be a normed space and let $B = \{x : \lVert x\rVert\leq1\}$ be its closed unit ball, convex by the triangle inequality. A point $x$ is extreme in $B$ exactly when $\lVert x\rVert = 1$ and $x$ is not the midpoint of two distinct unit vectors; the set of extreme points is the unit sphere only in the finite-dimensional strictly convex case. For $E = \ell^1$, whose unit ball is the closed convex hull of the vectors $\pm e_n$, the extreme points are exactly the $\pm e_n$, and the Krein–Milman theorem reads $B = \overline{\operatorname{conv}}\{\pm e_n\}$: every summable family with $\lVert x\rVert_1\leq1$ is the closed convex hull of the basis vectors, and the closure is not removable, since a point such as $x = (\tfrac12,\tfrac12,0,\dots)$ is not a finite or countable convex combination with sum one of the $\pm e_n$.

A Simplex

Let $K$ be a compact convex set whose extreme points are a finite set $\{v_1,\dots,v_n\}$. Then every point of $K$ is a convex combination of the $v_i$, the representation is unique, and $K$ is a simplex; the functional $x\mapsto (t_1,\dots,t_n)$ is the affine isomorphism onto the standard simplex. The compact convex sets in the plane are the only case in which the extreme-point set separates the simplexes from the polygons, and they are the elementary instance of the Choquet theory of a later article in this category.

Summary

A subset of a real vector space is convex when it contains the segments between its points, and the convex hull $\operatorname{conv}(A)$ is the set of finite convex combinations of points of $A$, the least convex set containing $A$. The hull is a closure operator on the lattice of subsets — monotone, increasing and idempotent — whose fixed points are the convex sets, and the closed convex hull is the corresponding operator for closed convex sets. The faces of a convex set are its convex subsets with the midpoint property, the extreme points are the singleton faces, an intersection of faces is a face, and a compact convex set has an extreme point, by Zorn's lemma and the separation theorem. The Krein–Milman theorem states that a compact convex subset of a locally convex space is the closed convex hull of its extreme points, so two such sets with the same extreme points coincide; Milman's converse states that if $K = \overline{\operatorname{conv}}(T)$ then every extreme point of $K$ lies in the closure of $T$. In finite dimension the theorem is Minkowski's, the extreme points are finite in the polyhedral case, and Carathéodory's bound $n+1$ on the number of points in a convex combination is available; in infinite dimension the bound fails and the closure in the theorem cannot be removed. The finite-dimensional calculus of convex sets — relative interiors, projections, separation, polyhedra — is Convex Analysis; the separation theorem invoked here is Duality Theory; and the closure-operator language is Order Theory and Lattices.

Summary of Notation

Symbol	Meaning
$E$	Real vector space, locally convex when a topology is used
$C$, $K$, $A$	A convex set; a compact convex set; an arbitrary set
$\operatorname{conv}(A)$	Convex hull, the set of finite convex combinations
$\operatorname{aff}(A)$, $\operatorname{cone}(A)$	Affine hull, conical hull
$\overline{\operatorname{conv}}(A)$	Closed convex hull
$\operatorname{ext}(C)$	Set of extreme points
Face, proper face	A convex subset with the midpoint property; one that is not all of $C$
Exposed face	A face cut out by a continuous functional attaining its maximum
$f$	Continuous linear functional used to expose a face or separate a point