Statements Shapley–Folkman lemma

1 statements

1.1 lemma of shapley , folkman

1.1.1 dimension of real vector space


1.2 shapley–folkman theorem , starr s corollary
1.3 proofs , computations

statements

minkowski addition , convex hulls. sixteen dark-red points (on right) form minkowski sum of 4 non-convex sets (on left), each of consists of pair of red points. convex hulls (shaded pink) contain plus-signs (+): right plus-sign sum of left plus-signs.

the preceding identity conv( ∑ qn ) = ∑ conv( qn ) implies if point x lies in convex hull of minkowski sum of n sets

x ∈ conv( ∑ qn )

then x lies in sum of convex hulls of summand-sets

x ∈ ∑ conv( qn ).

by definition of minkowski addition, last expression means x = ∑ qn selection of points qn in convex hulls of summand-sets, is, each qn ∈ conv(qn). in representation, selection of summand-points qn depends on chosen sum-point x.

lemma of shapley , folkman

a winner of 2012 nobel award in economics, lloyd shapley proved shapley–folkman lemma jon folkman.

for representation of point x, shapley–folkman lemma states if dimension d less number of summands

d < n

then convexification needed only d summand-sets, choice depends on x: point has representation

x
=

∑

1
≤

d

≤

d





q

d



+

∑

d
+
1
≤

n

≤

n





q

n





{\displaystyle x=\sum _{1\leq {d}\leq {d}}{q_{d}}+\sum _{d+1\leq {n}\leq {n}}{q_{n}}}

where qd belongs convex hull of qd for d (or fewer) summand-sets and qn belongs to qn remaining sets. that is,

x
∈


∑

1
≤

d

≤

d




conv
⁡

(

q

d


)


+

∑

d
+
1
≤

n

≤

n





q

n






{\displaystyle x\in {\sum _{1\leq {d}\leq {d}}{\operatorname {conv} {(q_{d})}}+\sum _{d+1\leq {n}\leq {n}}{q_{n}}}}

for re-indexing of summand sets; re-indexing depends on particular point x being represented.

the shapley–folkman lemma implies, example, every point in [0, 2] sum of integer from {0, 1} , real number from [0, 1].

dimension of real vector space

conversely, shapley–folkman lemma characterizes dimension of finite-dimensional, real vector spaces. is, if vector space obeys shapley–folkman lemma natural number d, , no number less than d, dimension exactly d; shapley–folkman lemma holds finite-dimensional vector spaces.

shapley–folkman theorem , starr s corollary

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]. 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).

proofs , computations

the original proof of shapley–folkman lemma established existence of representation, did not provide algorithm computing representation: similar proofs have been given arrow , hahn, cassels, , schneider, among others. abstract , elegant proof ekeland has been extended artstein. different proofs have appeared in unpublished papers, also. in 1981, starr published iterative method computing representation of given sum-point; however, computational proof provides weaker bound original result. elementary proof of shapley–folkman lemma in finite-dimensional space can found in book bertsekas

together applications in estimating duality gap in separable optimization problems , zero-sum games.