郭沅鑫Kevin

2022/12/24阅读：16主题：默认主题

# 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.,

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.

作者介绍