Shapley–Folkman lemma

Remarks

First, $\operatorname{conv}(S_1 + \cdots + S_N) = \operatorname{conv}(S_1) + \cdots + \operatorname{conv}(S_N)$, so $x = \sum_i \sum_j \lambda_{ij} y_{ij}$ with $y_{ij} \in S_i$, $\lambda_{ij} \ge 0$ and $\sum_j \lambda_{ij} = 1$ for each $i$. Then the point $(x, 1, \dots, 1) \in \R^{d+N}$ is a nonnegative combination of the vectors $(y_{ij}, e_i)$, where $e_i$ is the $i$-th unit vector of $\R^N$. By the conic form of Carathéodory's theorem, at most $d + N$ of these vectors are needed. Each index $i$ needs at least one of them, so at most $d$ indices use two or more, and the other indices use a single point of $S_i$. Example: $d = 1$ and $S_i = \set{0, 1}$ for all $i$. The point $x = 2.5$ of $\operatorname{conv}(S_1 + S_2 + S_3) = [0, 3]$ is $1 + 1 + 0.5$, and only one summand is outside its $S_i$.

Going deeper

For a student

A quantitative consequence, the Shapley–Folkman theorem, bounds the distance between $\operatorname{conv}(S_1 + \cdots + S_N)$ and $S_1 + \cdots + S_N$ in terms of $d$ and the sizes of the $S_i$, independently of $N$. In mathematical economics this explains why equilibria nearly exist in large markets with nonconvex preferences. In optimization it bounds the duality gap of separable nonconvex problems with many terms.