Convex hulls and Carathéodory’s theorem

Work in Euclidean space $\mathbb R^d$. The convex hull of a nonempty set S consists of its finite convex combinations: coefficients are nonnegative and sum to one. Its affine hull permits negative coefficients but retains the sum condition. The closed convex hull also includes limits of convex combinations. These distinctions matter even in one dimension. For S=(0,1), its convex hull remains (0,1), while its closed convex hull contains both endpoints. No finite average of strictly positive numbers can equal zero.

The convex hull is the smallest convex set containing S. To verify this, combine two finite mixtures into one longer list to show convexity. Conversely, any convex set containing S contains every finite mixture by repeatedly applying the two-point definition. This argument does not require compactness or a finite set of generators. In finite dimensions, however, dimension imposes a powerful bound on the number of nonzero weights. A generator set lying in an affine plane uses that plane’s dimension, even if the surrounding ambient space is much larger.

Suppose a representation uses more than d+1 points with strictly positive weights. The augmented vectors $(s_i,1)$ are linearly dependent in $\mathbb R^{d+1}$. Consequently there is a nonzero coefficient list a with both weighted location sum zero and coefficient sum zero. The list a has a positive entry and a negative entry; otherwise its zero sum would force every entry to vanish. Subtract a small multiple of this dependence from the original weights. Both the represented point and the total weight remain unchanged.

Increase that multiple until the first positive weight reaches zero. More precisely, choose the minimum of $\lambda_i/a_i$ over positive a entries. Every new weight stays nonnegative, and at least one disappears. Repeating the procedure leaves at most d+1 points. Replacing d with the affine dimension gives the sharper bound. This is a complete existence proof and also an elimination algorithm when a dependence can be computed. It guarantees neither uniqueness of the final support nor a preference for particular generators.

If S is compact and nonempty in finite dimensions, its convex hull is compact. Carathéodory reduces every point to d+1 generators, allowing repeated generators and zero weights. The hull is therefore the continuous image of the compact product of d+1 copies of S and the compact weight simplex. This compactness argument would fail without control over the number of generators. It gives existence results for maximizing a continuous objective over such a hull, but a nonlinear objective need not achieve its optimum at a generator.

The finite-dimensional hypothesis is substantive. In an infinite-dimensional Hilbert space, an infinite weighted limit can require arbitrarily large finite supports for accurate approximation, and need not belong to the finite convex hull at all. Even in finite dimensions the theorem preserves only the coordinates used to define the point. If a mixture must also preserve cost, variance, or another moment, include those quantities as extra coordinates before applying the bound. Adding constraints after compressing the original coordinates can destroy the feature one intended to preserve.