Preliminaries Shapley–Folkman lemma

1 preliminaries

1.1 real vector spaces
1.2 convex sets
1.3 convex hull
1.4 minkowski addition
1.5 convex hulls of minkowski sums

preliminaries

the shapley–folkman lemma depends upon following definitions , results convex geometry.

real vector spaces

a real vector space of two dimensions can given cartesian coordinate system in every point identified ordered pair of real numbers, called coordinates , conventionally denoted by x and y. 2 points in cartesian plane can added coordinate-wise

(x1, y1) + (x2, y2) = (x1+x2, y1+y2);

further, point can multiplied each real number λ coordinate-wise

λ (x, y) = (λx, λy).

more generally, real vector space of (finite) dimension d can viewed set of d-tuples of d real numbers { (v1, v2, . . . , vd) } on two operations defined: vector addition , multiplication real number. finite-dimensional vector spaces, operations of vector addition , real-number multiplication can each defined coordinate-wise, following example of cartesian plane.

convex sets

in real vector space, non-empty set q defined convex if, each pair of points, every point on line segment joins them subset of q. example, solid disk 



∙


{\displaystyle \bullet }

convex circle 



∘


{\displaystyle \circ }

not, because not contain line segment joining points 



⊘


{\displaystyle \oslash }

; non-convex set of 3 integers {0, 1, 2} contained in interval [0, 2], convex. example, solid cube convex; however, hollow or dented, example, crescent shape, non-convex. empty set convex, either definition or vacuously, depending on author.

more formally, set q convex if, points v0 and v1 in q , every real number λ in unit interval [0,1], point

(1 − λ) v0 + λv1

is member of q.

by mathematical induction, set q convex if , only if every convex combination of members of q belongs to q. definition, convex combination of indexed subset {v0, v1, . . . , vd} of vector space weighted average λ0v0 + λ1v1 + . . . + λdvd, indexed set of non-negative real numbers {λd} satisfying equation λ0 + λ1 + . . .  + λd = 1.

the definition of convex set implies intersection of 2 convex sets convex set. more generally, intersection of family of convex sets convex set. in particular, intersection of 2 disjoint sets empty set, convex.

convex hull

in convex hull of red set, each blue point convex combination of red points.

for every subset q of real vector space, convex hull conv(q) minimal convex set contains q. thus conv(q) intersection of convex sets cover q. convex hull of set can equivalently defined set of convex combinations of points in q. example, convex hull of set of integers {0,1} closed interval of real numbers [0,1], contains integer end-points. convex hull of unit circle closed unit disk, contains unit circle.

minkowski addition

minkowski addition of sets. sum of squares q1=[0,1] and q2=[1,2] square q1+q2=[1,3].

in real vector space, minkowski sum of 2 (non-empty) sets q1 and q2 defined set q1 + q2 formed addition of vectors element-wise summand sets

q1 + q2 = { q1 + q2 : q1 ∈ q1 , q2 ∈ q2 }.

for example

{0, 1} + {0, 1} = {0+0, 0+1, 1+0, 1+1} = {0, 1, 2}.

by principle of mathematical induction, minkowski sum of finite family of (non-empty) sets

{qn : qn ≠ Ø , 1 ≤ n ≤ n }

is set formed element-wise addition of vectors

∑ qn = {∑ qn : qn ∈ qn}.

convex hulls of minkowski sums

minkowski addition behaves respect convexification —the operation of taking convex hulls. specifically, subsets q1 and q2 of real vector space, convex hull of minkowski sum minkowski sum of convex hulls. is,

conv( q1 + q2 ) = conv( q1 ) + conv( q2 ).

this result holds more generally, consequence of principle of mathematical induction. each finite collection of sets,

conv(  ∑ qn  ) = ∑ conv( qn ).




^ arrow & hahn (1980, p. 375)
^ rockafellar (1997, p. 10)
^ arrow & hahn (1980, p. 376), rockafellar (1997, pp. 10–11), , green & heller (1981, p. 37)
^ arrow & hahn (1980, p. 385) , rockafellar (1997, pp. 11–12)
^ cite error: named reference carter94 invoked never defined (see page).
^ schneider (1993, p. xi) , rockafellar (1997, p. 16)
^ rockafellar (1997, p. 17) , starr (1997, p. 78)
^ schneider (1993, pp. 2–3)
^ arrow & hahn (1980, p. 387)