Carathéodory's theorem

Let's talk about convex geometry. To start off we quickly recall what vector spaces are: they are sets equipped with vector addition and scalar multiplication such that certain axioms hold. A vector subspace is a subset of a vector space such that it is closed under vector addition and scalar multiplication. In this sense, we can draw the analogy between convex sets and vector subspaces - convex sets are subsets of vector subspaces such that they are closed under convex combinations, i.e., a set is convex if .

Convex sets are desirable, but they are not everywhere - often times we wish to 'transform' a non-convex set into a convex set. A natural idea is to figure out what is the smallest convex set that contains . We call this set the convex hull of , usually denoted as .

Now does convex hull remind you of something similar in linear algebra? If we want to find out the smallest vector subspace containing a set , we simply take the linear span of , which is defined by all linear combinations of the points in . It would not be a surprise that convex hulls can be characterized in an completely analogous way: the convex hull of is the set of all convex combinations of the points in , i.e.,

From here on we also use convex hull to denote the set of all convex combinations of a set, as we have shown they are in fact equivalent.

One of the best thing about a vector subspace is that we can find a basis of it, such that every point in the vector subspace can be represented as a unique linear combination of the basis vectors. More specifically, if we have any set , then we can find points in , such that and is a linearly independent set. The value is called the dimension of the vector subspace .

The result above actually exhibits one of the advantage of vector subspaces: we can characterize the smallest vector subspace containing using not more than points. Can we transfer this result, in a certain sense, to convex geometry? Well, no and yes. No because in general we cannot characterize a convex set using finitely many points: just note that is an unbounded convex set, but any finite set is bounded hence its convex hull is also bounded (Exercise: prove it!).

Still there is a 'yes' aspect to it - and this is the main theme of this article, the Carathéodory theorem for convex sets. The statement of the theorem is given as follows:

Theorem 1 (Carathéodory). Given a point , we can find a subset such that and .

Before seeing the proof of the theorem, we discuss how it is different from the somewhat similar result in linear algebra. Given a basis of a vector subspace, any point can be represented as a unique linear combination of the basis vectors. In other words, the choice of the basis comes before the specification of a particular point. However in Carathéodory's theorem, we first fix a point in the convex hull, then find a 'basis' accordingly; for different points, the 'basis', i.e., is chosen differently in general.

Proof. The proof relies on a 'descent' type of argument, which shows that if we can write as a convex combination of more than points, then it is always possible to reduce at least one of the points. By repeating this argument, we can decrease the number of points in the convex combination until it is not more than .

Suppose where for all and . If then we are done. Otherwise, by a dimensionality argument, we know that is a linearly dependent set, hence we can find some coefficients that are not all nonzero such that . By letting , we rewrite the previous formula as and we also know that . Since not all 's are zero, we conclude that there must be a . In particular, we define , and then for all , we have that , and . Furthermore, . Now we consider the combination:

By previous argument, it is clearly a convex combination, and effectively it is a convex combination of not more than points: note that thus is not involved! Therefore, we have reduced the number of points in the convex combination by at least one. Repeating this argument, we can eventually get to the statement of Caratheodory's theorem.

In general, the quantity cannot be improved - we can always consider a -simplex in , which is the convex hull of its affinity independent vertices, and any point in the interior of the simplex cannot be written as the convex combination of less than vertices. However, when , i.e., the boundary of the convex hull of , we can improve to . (Exercise: Why? Hint: Supporting hyperplane theorem!)

Carathéodory's theorem tells us that characterizing a point in a convex set needs more effort as the dimension increases. However, in the next article we will show a truly impressive theorem which uses probabilistic method to prove that we only need points to approximately characterize a point in a convex set of any dimension such that the error norm is bounded by times the diameter of the convex set.