Shapley–Folkman theorem and Starr's corollary Shapley–Folkman lemma

the circumradius (blue) , inner radius (green) of point set (dark red, convex hull shown lighter red dashed lines). inner radius smaller circumradius except subsets of single circle, equal.

shapley , folkman used lemma prove theorem, bounds distance between minkowski sum , convex hull, convexified sum:

the shapley–folkman theorem states squared euclidean distance point in convexified sum conv( ∑ qn ) original (unconvexified) sum ∑ qn bounded sum of squares of the d largest circumradii of sets qn (the radii of smallest spheres enclosing these sets). bound independent of number of summand-sets n (if n > d).

the shapley–folkman theorem states bound on distance between minkowski sum , convex hull; distance 0 if , if sum convex. bound on distance depends on dimension d , on shapes of summand-sets, not on number of summand-sets n, when n > d.

the circumradius exceeds (and cannot less than) inner radius:

the inner radius of set qn defined smallest number r such that, point q in convex hull of qn, there sphere of radius r contains subset of qn convex hull contains q.

starr used inner radius reduce upper bound stated in shapley–folkman theorem:

starr s corollary shapley–folkman theorem states squared euclidean distance point x in convexified sum conv( ∑ qn ) original (unconvexified) sum ∑ qn bounded sum of squares of the d largest inner-radii of sets qn.

starr s corollary states upper bound on euclidean distance between minkowski sum of n sets , convex hull of minkowski sum; distance between sum , convex hull measurement of non-convexity of set. simplicity, distance called non-convexity of set (with respect starr s measurement). thus, starr s bound on non-convexity of sum depends on the d largest inner radii of summand-sets; however, starr s bound not depend on number of summand-sets n, when n > d. example, distance between convex interval [0, 2] , non-convex set {0, 1, 2} equals one-half

1/2 = |1 − 1/2| = |0 − 1/2| = |2 − 3/2| = |1 − 3/2|.

thus, starr s bound on non-convexity of average

 ⁄n ∑ qn

decreases number of summands n increases. example, distance between averaged set

1/2 ( {0, 1} + {0, 1} ) = {0, 1/2, 1}

and convex hull [0, 1] only 1/4, half distance (1/2) between summand {0, 1} and [0, 1].

the shapes of subcollection of only d summand-sets determine bound on distance between average set , convex hull; thus, number of summands increases infinity, bound decreases 0 (for summand-sets of uniformly bounded size). in fact, starr s bound on non-convexity of average set decreases 0 number of summands n increases infinity (when inner radii of summands bounded same number).