Shapley–Folkman lemma

A theorem stating that, in a finite-dimensional space, any point in a sum of convex hulls can be represented using points from the original sets except for at most as many summands as the dimension.

Connect

Minkowski sum: The set of all sums formed by choosing one element from each of several sets. The lemma compares a Minkowski sum with the sum formed after convexifying each summand.
Nonconvex optimization: Optimization in which the objective or feasible region is not convex. The lemma can bound the gap between nonconvex and convexified formulations.
Lloyd Shapley: An American mathematician whose work shaped cooperative game theory and mathematical economics. His name is attached to the lemma through its connection with game-theoretic convexity.
Helly's theorem: A theorem stating that a finite family of convex sets in dimension d has nonempty intersection if every d+1 of them intersect. It is another dimension-controlled convexity theorem, but concerns intersections rather than sums.
Convex hull: The smallest convex set containing a given set. Convexifying the summands creates the larger sum that the lemma approximates.
Integer programming: Optimization over variables restricted to integer values, often with linear constraints. Convexification can relax discrete choices, while the lemma limits how many summands need remain nonconvex.
Jon Folkman: An American mathematician known for contributions to convexity, optimization, and mathematical economics. His independent work established the result that shares his name.
Radon's theorem: A theorem stating that any d+2 points in d-dimensional space can be partitioned into two groups with intersecting convex hulls. It yields convexity structure through point partitions, not approximation of sums.
Carathéodory's theorem: A theorem stating that points in a convex hull in dimension d need at most d+1 points in their convex representations. Its dimension-based sparsity principle is closely related to the lemma’s bound on exceptional summands.
Large deviations theory: The mathematical study of probabilities of rare events and their exponential rates. Shapley–Folkman-type bounds help justify convex approximations in aggregate models.