Real vector spaces

A real vector space of two dimensions can be given a Cartesian coordinate system in which every point is identified by an ordered pair of real numbers, called "coordinates", which are conventionally denoted by x and y. Two points in the Cartesian plane can be added coordinate-wise

(x₁, y₁) + (x₂, y₂) = (x₁+x₂, y₁+y₂);

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

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

More generally, any real vector space of (finite) dimension  ${\displaystyle D}$ can be viewed as the set of all ${\displaystyle D}$-tuples of  ${\displaystyle D}$ real numbers { (v₁, v₂, . . . , v_D) } on which two operations are defined: vector addition and multiplication by a real number. For finite-dimensional vector spaces, the operations of vector addition and real-number multiplication can each be defined coordinate-wise, following the example of the Cartesian plane.^[8]

Convex sets

In a real vector space, a non-empty set Q is defined to be convex if, for each pair of its points, every point on the line segment that joins them is still in Q. For example, a solid disk ${\displaystyle \bullet }$ is convex but a circle ${\displaystyle \circ }$ is not, because it does not contain a line segment joining its points ${\displaystyle \oslash }$; the non-convex set of three integers {0, 1, 2} is contained in the interval [0, 2], which is convex. For example, a solid cube is convex; however, anything that is hollow or dented, for example, a crescent shape, is non-convex. The empty set is convex, either by definition^[9] or vacuously, depending on the author.

More formally, a set Q is convex if, for all points v₀ and v₁ in Q and for every real number λ in the unit interval [0,1], the point

(1 − λ) v₀ + λv₁

is a member of Q.

By mathematical induction, a set Q is convex if and only if every convex combination of members of Q also belongs to Q. By definition, a convex combination of an indexed subset {v₀, v₁, . . . , v_D} of a vector space is any weighted average λ₀v₀ + λ₁v₁ + . . . + λ_Dv_D, for some indexed set of non-negative real numbers {λ_d} satisfying the equation λ₀ + λ₁ + . . .  + λ_D = 1.^[10]

The definition of a convex set implies that the intersection of two convex sets is a convex set. More generally, the intersection of a family of convex sets is a convex set. In particular, the intersection of two disjoint sets is the empty set, which is convex.^[9]

Convex hull

For every subset Q of a real vector space, its convex hull Conv(Q) is the minimal convex set that contains Q. Thus Conv(Q) is the intersection of all the convex sets that cover Q. The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in Q.^[11] For example, the convex hull of the set of integers {0,1} is the closed interval of real numbers [0,1], which contains the integer end-points.^[7] The convex hull of the unit circle is the closed unit disk, which contains the unit circle.

Minkowski addition

In any vector space (or algebraic structure with addition), ${\displaystyle X}$, the Minkowski sum of two non-empty sets ${\displaystyle A,B\subseteq X}$ is defined to be the element-wise operation ${\displaystyle A+B:=\{x+y\mid x\in A,~y\in B\}.}$ (See also.^[12]) For example

${\displaystyle \{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}}$

This operation is clearly commutative and associative on the collection of non-empty sets. All such operations extend in a well-defined manner to recursive forms ${\displaystyle \sum _{n=1}^{N}Q_{n}=Q_{1}+Q_{2}+\ldots +Q_{N}.}$ By the principle of induction it is easy to see that^[13]

${\displaystyle \sum _{n=1}^{N}Q_{n}=\{\sum _{n=1}^{N}q_{n}\mid q_{n}\in Q_{n},~1\leq n\leq N\}.}$

Convex hulls of Minkowski sums

Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets ${\displaystyle A,B\subseteq X}$ of a real vector space, ${\displaystyle X}$, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls. That is,

${\displaystyle \mathrm {Conv} (A+B)=\mathrm {Conv} (A)+\mathrm {Conv} (B).}$

And by induction it follows that

${\displaystyle \mathrm {Conv} (\sum _{n=1}^{N}Q_{n})=\sum _{n=1}^{N}\mathrm {Conv} (Q_{n})}$

for any ${\displaystyle N\in \mathbb {N} }$ and non-empty subsets ${\displaystyle Q_{n}\subseteq X}$, ${\displaystyle 1\leq n\leq N}$.^[14][15]

Notation

${\displaystyle D,N\in \{1,2,3,...\}}$ are positive integers.

${\displaystyle D}$ is the dimension of the ambient space ${\displaystyle \mathbb {R} ^{D}}$.

${\displaystyle Q_{1},...,Q_{N}}$ are nonempty, bounded subsets of ${\displaystyle \mathbb {R} ^{D}}$. They are also called "summands". ${\displaystyle N}$ is the number of summands.

${\displaystyle Q=\sum _{n=1}^{N}Q_{n}}$ is the Minkowski sum of the summands.

${\displaystyle x}$ is an arbitrary vector in ${\displaystyle \mathrm {Conv} (Q)}$.

Shapley–Folkman lemma

Since ${\displaystyle \mathrm {Conv} (Q)=\sum _{n=1}^{N}\mathrm {Conv} (Q_{n})}$, for any ${\displaystyle x\in \mathrm {Conv} (Q)}$, there exist elements ${\displaystyle q_{n}\in \mathrm {Conv} (Q_{n})}$ such that ${\displaystyle \sum _{n=1}^{N}q_{n}=x}$. The Shapley–Folkman lemma refines this statement.

For example, every point in ${\displaystyle [0,2]=[0,1]+[0,1]=\mathrm {Conv} (\{0,1\})+\mathrm {Conv} (\{0,1\})}$ is the sum of an element in ${\displaystyle \{0,1\}}$ and an element in ${\displaystyle [0,1]}$.^[7]

Shuffling indices if necessary, this means that every point in ${\displaystyle \mathrm {Conv} (Q)}$ can be decomposed as

${\displaystyle x=\sum _{n=1}^{D}q_{n}+\sum _{n=D+1}^{N}q_{n}}$

where ${\displaystyle q_{n}\in \mathrm {Conv} (Q_{n})}$ for ${\displaystyle 1\leq n\leq D}$ and ${\displaystyle q_{n}\in Q_{n}}$ for ${\displaystyle D+1\leq n\leq N}$. Note that the reindexing depends on the point ${\displaystyle x}$.^[16]

The lemma may be stated succinctly as

${\displaystyle \mathrm {Conv} \left(\sum _{n=1}^{N}Q_{n}\right)\subseteq \bigcup _{I\subseteq \{1,2,\ldots N\}:~|I|=D}\left(\sum _{n\in I}\mathrm {Conv} (Q_{n})+\sum _{n\notin I}Q_{n}\right).}$

Shapley–Folkman theorem

Shapley and Folkman used their lemma to prove the following theorem, which quantifies the difference between ${\displaystyle Q}$ and ${\displaystyle \mathrm {Conv} (Q)}$ using squared Euclidean distance.

For any nonempty subset ${\displaystyle S\subseteq \mathbb {R} ^{D}}$ and any point ${\displaystyle x\in \mathbb {R} ^{D},}$ define their squared Euclidean distance to be the infimum

$${\displaystyle d^{2}(x,S)=\inf _{y\in S}\|x-y\|^{2}.}$$

And more generally, for any two nonempty subsets ${\displaystyle S,S'\subseteq \mathbb {R} ^{D},}$ define

$${\displaystyle d^{2}(S,S')=\inf _{x\in S,y\in S'}\|x-y\|^{2}.}$$

Note that ${\displaystyle d^{2}(x,S)=(\inf _{y\in S}\|x-y\|)^{2},}$ so we can simply write ${\displaystyle d^{2}(x,S)=d(x,S)^{2},}$ where ${\displaystyle d(x,S)=\inf _{y\in S}\|x-y\|.}$ Similarly, ${\displaystyle d^{2}(S,S')=d(S,S')^{2}.}$

For example, ${\displaystyle d^{2}([0,2],\{0,1,2\})=1/4=d([0,2],\{0,1,2\})^{2}.}$

The squared Euclidean distance is a measure of how "close" two sets are. In particular, if two sets are compact, then their squared Euclidean distance is zero if and only if they are equal. Thus, we may quantify how close to convexity ${\displaystyle Q}$ is by upper-bounding ${\displaystyle d^{2}(\mathrm {Conv} (Q),Q).}$

For any bounded subset ${\displaystyle S\subset \mathbb {R} ^{D},}$ define its circumradius ${\displaystyle rad(S)}$ to be the infimum of the radius of all balls containing it (as shown in the diagram). More formally,

$${\displaystyle rad(S)\equiv \inf _{x\in R^{N}}\sup _{y\in S}\|x-y\|}$$

Now we can state

where we use the notation ${\displaystyle \sum _{\max D}}$ to mean "the sum of the ${\displaystyle D}$ largest terms".

Note that this upper bound depends on the dimension of ambient space and the shapes of the summands, but not on the number of summands.

Shapley–Folkman–Starr theorem

Define the inner radius ${\displaystyle r(S)}$ of a bounded subset ${\displaystyle S\subset \mathbb {R} ^{D}}$ to be the infimum of ${\displaystyle r}$ such that, for any ${\displaystyle x\in \mathrm {Conv} (S)}$, there exists a ball ${\displaystyle B}$ of radius ${\displaystyle r}$ such that ${\displaystyle x\in \mathrm {Conv} (S\cap B)}$.^[20]

For example, let ${\displaystyle B'\subset B\subset \mathbb {R} ^{D}}$ be two nested balls, then the circumradius of ${\displaystyle B\setminus B'}$ is the radius of ${\displaystyle B}$, but its inner radius is the radius of ${\displaystyle B'}$.

Since ${\displaystyle r(S)\leq rad(S)}$ for any bounded subset ${\displaystyle S\subset \mathbb {R} ^{D}}$, the following theorem is a refinement:

In particular, if we have an infinite sequence ${\displaystyle (Q_{n})_{n=1,2,...}}$ of nonempty, bounded subsets of ${\displaystyle \mathbb {R} ^{D}}$, and if there exists some ${\displaystyle r_{0}\geq 0}$ such that the inner radius of each ${\displaystyle Q_{n}}$ is upper-bounded by ${\displaystyle r_{0}}$, then

$${\displaystyle d^{2}\left(\mathrm {Conv} \left({\frac {1}{N}}\sum _{n=1}^{N}Q_{n}\right),{\frac {1}{N}}\sum _{n=1}^{N}Q_{n}\right)\leq {\frac {Dr_{0}^{2}}{N}}.}$$

This can be interpreted as stating that, as long as we have an upper bound on the inner radii, performing "Minkowski-averaging" would get us closer and closer to a convex set.

Other proofs of the results

There have been many proofs of these results, from the original,^[20] to the later Arrow and Hahn,^[22] Cassels,^[23] Schneider,^[24] etc. An abstract and elegant proof by Ekeland^[25] has been extended by Artstein.^[26] Different proofs have also appeared in unpublished papers.^[2][27] An elementary proof of the Shapley–Folkman lemma can be found in the book by Bertsekas,^[28] together with applications in estimating the duality gap in separable optimization problems and zero-sum games.

Usual proofs of these results are nonconstructive: they establish only the existence of the representation, but do not provide an algorithm for computing the representation. In 1981, Starr published an iterative algorithm for a less sharp version of the Shapley–Folkman–Starr theorem.^[29]

A proof of the results

The following proof of Shapley–Folkman lemma is from.^[30] The proof idea is to lift the representation of ${\displaystyle x}$ from ${\displaystyle \mathbb {R} ^{D}}$to ${\displaystyle \mathbb {R} ^{D+N}}$, use Carathéodory's theorem for conic hulls, then drop back to ${\displaystyle \mathbb {R} ^{D}}$.

Proof of Shapley–Folkman lemma

Since ${\displaystyle x\in \sum _{n=1}^{N}\mathrm {Conv} (Q_{n})}$, there exists a minimal set of indices ${\displaystyle I\subset 1:N}$, such that ${\displaystyle x\in \sum _{n\in I}\mathrm {Conv} (Q_{n})}$, but ${\displaystyle x\not \in \sum _{n\in J}\mathrm {Conv} (Q_{n})}$ for any proper subset ${\displaystyle J\subsetneq I}$.

Since we can always drop to such a set ${\displaystyle I}$, we WLOG assume that ${\displaystyle 1:N}$ is itself a minimal set of indices, that is, ${\displaystyle x}$ cannot be represented as ${\displaystyle \sum _{n\in I}q_{n}}$ where ${\displaystyle I}$ is a proper subset of ${\displaystyle 1:N}$.

For each ${\displaystyle n}$, represent ${\displaystyle q_{n}\in \mathrm {Conv} (Q_{n})}$ as ${\displaystyle q_{n}=\sum _{k=1}^{K}w_{n,k}q_{n,k}}$, where ${\displaystyle K}$ is a large finite number, ${\displaystyle w_{n,k}\geq 0}$, and ${\displaystyle \sum _{k}w_{n,k}=1}$.

Now "lift" the representation ${\displaystyle x=\sum _{n}\sum _{k}w_{n,k}q_{n,k}}$ from ${\displaystyle \mathbb {R} ^{D}}$ to ${\displaystyle \mathbb {R} ^{D+N}}$. Define

$${\displaystyle {\bar {x}}=(x,1,...,1);\quad {\bar {q}}_{n,k}=(q_{n,k},e_{n})}$$

where ${\displaystyle e_{n}}$ is the vector in ${\displaystyle \mathbb {R} ^{N}}$ that has 1 at coordinate ${\displaystyle n}$, and 0 at all other coordinates.

With this, we have a lifted representation

$${\displaystyle {\bar {x}}=\sum _{n}\sum _{k}w_{n,k}{\bar {q}}_{n,k}.}$$

That is, ${\displaystyle {\bar {x}}}$ is in the conic hull of ${\displaystyle \{{\bar {q}}_{n,k}\}_{n\in 1:N,k\in 1:K}}$.

By Carathéodory's theorem for conic hulls, we have an alternative representation

$${\displaystyle {\bar {x}}=\sum _{n}\sum _{k}w'_{n,k}{\bar {q}}_{n,k}}$$

such that ${\displaystyle w'_{n,k}\geq 0}$, and at most ${\displaystyle N+D}$ of them are nonzero. Since we defined

$${\displaystyle {\bar {x}}=(x,1,...,1);\quad {\bar {q}}_{n,k}=(q_{n,k},e_{n})}$$

this alternative representation is also a representation for ${\displaystyle x}$.

Since we assumed that ${\displaystyle x}$ cannot be represented as ${\displaystyle \sum _{n\in I}q_{n}}$ where ${\displaystyle I}$ is a proper subset of ${\displaystyle 1:N}$, we find that for every ${\displaystyle n\in 1:N}$, at least one of ${\displaystyle w'_{n,k}}$ is nonzero.

Since at most ${\displaystyle N+D}$ of ${\displaystyle w_{n,k}'}$ are nonzero, we find that for at most ${\displaystyle D}$ of ${\displaystyle n\in 1:N}$, at least two of ${\displaystyle w_{n,k}'}$ are nonzero.

Thus we obtain a representation

$${\displaystyle {\bar {x}}=\sum _{n}\left(\sum _{k}w'_{n,k}{\bar {q}}_{n,k}\right)}$$

where for at most ${\displaystyle D}$ of ${\displaystyle n}$, the term ${\displaystyle \sum _{k}w'_{n,k}{\bar {q}}_{n,k}}$ is not in ${\displaystyle Q_{n}}$.

The following "probabilistic" proof of Shapley–Folkman–Starr theorem is from.^[23]

We can interpret ${\displaystyle \mathrm {Conv} (S)}$ in probabilistic terms: ${\displaystyle \forall x\in \mathrm {Conv} (S)}$, since ${\displaystyle x=\sum w_{n}q_{n}}$ for some ${\displaystyle q_{n}\in S}$, we can define a random vector ${\displaystyle X}$, finitely supported in ${\displaystyle S}$, such that ${\displaystyle Pr(X=q_{n})=w_{n}}$, and ${\displaystyle x=\mathbb {E} [X]}$.

Then, it is natural to consider the "variance" of a set ${\displaystyle S}$ as

$${\displaystyle Var(S):=\sup _{x\in \mathrm {Conv} (S)}\inf _{\mathbb {E} [X]=x,X{\text{ is finitely supported in }}S}Var[X]}$$

With that, ${\displaystyle d(S,\mathrm {Conv} (S))^{2}\leq Var(S)\leq r(S)\leq rad(S)}$.

Proof of Shapley–Folkman–Starr theorem

It suffices to show ${\displaystyle Var\left(Q\right)\leq \sum _{\max D}Var(Q_{n})}$.

${\displaystyle \forall x\in \mathrm {Conv} (Q)}$, by Shapley–Folkman lemma, there exists a representation ${\displaystyle x=\sum _{n\in I}x_{n}+\sum _{n\in J}q_{n}}$, such that ${\displaystyle I,J}$ partitions ${\displaystyle \{1,2,...,N\},|I|\leq D,x_{n}\in \mathrm {Conv} (Q_{n}),q_{n}\in Q_{n}}$.

Now, for each ${\displaystyle n\in I}$, construct random vectors ${\displaystyle X_{n}}$ such that ${\displaystyle X_{n}}$ is finitely supported on ${\displaystyle Q_{n}}$, with ${\displaystyle \mathbb {E} [X_{n}]=x_{n}}$ and ${\displaystyle Var[X_{n}]<Var[Q_{n}]+\epsilon }$, where ${\displaystyle \epsilon >0}$ is an arbitrary small number.

Let all such ${\displaystyle X_{n}}$ be independent. Then let ${\displaystyle X=\sum _{n\in I}X_{n}+\sum _{n\in J}q_{n}}$. Since each ${\displaystyle q_{n}}$ is a deterministic vector, we have

$${\displaystyle Var[X]=Var\left[\sum _{n\in I}X_{n}\right]=\sum _{n\in I}Var\left[X_{n}\right]\leq \sum _{n\in I}\left(Var(Q_{n})+\epsilon \right)\leq \sum _{\max D}Var(Q_{n})+D\epsilon .}$$

Since this is true for arbitrary ${\displaystyle \epsilon >0}$, we have ${\displaystyle Var[X]\leq \sum _{\max D}Var(Q_{n})}$, and we are done.

Economics

In economics, a consumer's preferences are defined over all "baskets" of goods. Each basket is represented as a non-negative vector, whose coordinates represent the quantities of the goods. On this set of baskets, an indifference curve is defined for each consumer; a consumer's indifference curve contains all the baskets of commodities that the consumer regards as equivalent: That is, for every pair of baskets on the same indifference curve, the consumer does not prefer one basket over another. Through each basket of commodities passes one indifference curve. A consumer's preference set (relative to an indifference curve) is the union of the indifference curve and all the commodity baskets that the consumer prefers over the indifference curve. A consumer's preferences are convex if all such preference sets are convex.^[32]

An optimal basket of goods occurs where the budget-line supports a consumer's preference set, as shown in the diagram. This means that an optimal basket is on the highest possible indifference curve given the budget-line, which is defined in terms of a price vector and the consumer's income (endowment vector). Thus, the set of optimal baskets is a function of the prices, and this function is called the consumer's demand. If the preference set is convex, then at every price the consumer's demand is a convex set, for example, a unique optimal basket or a line-segment of baskets.^[33]

Mathematical optimization

The Shapley–Folkman lemma has been used to explain why large minimization problems with non-convexities can be nearly solved (with iterative methods whose convergence proofs are stated for only convex problems). The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.^[61]

Probability and measure theory

Convex sets are often studied with probability theory. Each point in the convex hull of a (non-empty) subset Q of a finite-dimensional space is the expected value of a simple random vector that takes its values in Q, as a consequence of Carathéodory's lemma. Thus, for a non-empty set Q, the collection of the expected values of the simple, Q-valued random vectors equals Q's convex hull; this equality implies that the Shapley–Folkman–Starr results are useful in probability theory.^[67] In the other direction, probability theory provides tools to examine convex sets generally and the Shapley–Folkman–Starr results specifically.^[68] The Shapley–Folkman–Starr results have been widely used in the probabilistic theory of random sets,^[69] for example, to prove a law of large numbers,^[6][70] a central limit theorem,^[70][71] and a large-deviations principle.^[72] These proofs of probabilistic limit theorems used the Shapley–Folkman–Starr results to avoid the assumption that all the random sets be convex.

A probability measure is a finite measure, and the Shapley–Folkman lemma has applications in non-probabilistic measure theory, such as the theories of volume and of vector measures. The Shapley–Folkman lemma enables a refinement of the Brunn–Minkowski inequality, which bounds the volume of sums in terms of the volumes of their summand-sets.^[73] The volume of a set is defined in terms of the Lebesgue measure, which is defined on subsets of Euclidean space. In advanced measure-theory, the Shapley–Folkman lemma has been used to prove Lyapunov's theorem, which states that the range of a vector measure is convex.^[74] Here, the traditional term "range" (alternatively, "image") is the set of values produced by the function. A vector measure is a vector-valued generalization of a measure; for example, if p₁ and p₂ are probability measures defined on the same measurable space, then the product function p₁ p₂ is a vector measure, where p₁ p₂ is defined for every event ω by

(p₁ p₂)(ω)=(p₁(ω), p₂(ω)).

Lyapunov's theorem has been used in economics,^[45][75] in ("bang-bang") control theory, and in statistical theory.^[76] Lyapunov's theorem has been called a continuous counterpart of the Shapley–Folkman lemma,^[3] which has itself been called a discrete analogue of Lyapunov's theorem.^[77]