Shapley–Folkman lemma

The Shapley–Folkman lemma is illustrated by the Minkowski addition of four sets. The point (+) in the convex hull of the Minkowski sum of the four non-convex sets (right) is the sum of four points (+) from the (left-hand) sets—two points in two non-convex sets plus two points in the convex hulls of two sets. The convex hulls are shaded pink. The original sets each have exactly two points (shown as red dots).

The Shapley–Folkman lemma is a result in convex geometry that describes the Minkowski addition of sets in a vector space. It is named after mathematicians Lloyd Shapley and Jon Folkman, but was first published by the economist Ross M. Starr.

The lemma may be intuitively understood as saying that, if the number of summed sets exceeds the dimension of the vector space, then their Minkowski sum is approximately convex.

Related results provide more refined statements about how close the approximation is. For example, the Shapley–Folkman theorem provides an upper bound on the distance between any point in the Minkowski sum and its convex hull. This upper bound is sharpened by the Shapley–Folkman–Starr theorem (alternatively, Starr's corollary).

The Shapley–Folkman lemma has applications in economics, optimization and probability theory. In economics, it can be used to extend results proved for convex preferences to non-convex preferences. In optimization theory, it can be used to explain the successful solution of minimization problems that are sums of many functions. In probability, it can be used to prove a law of large numbers for random sets. Template:TOC limit

Introductory example

A set is convex if every line segment joining two of its points is a subset in the set: For example, the solid disk $\bullet$ is a convex set but the circle $\circ$ is not, because the line segment joining two distinct points $\oslash$ is not a subset of the circle.

The convex hull of a set Template:Mvar is the smallest convex set that contains Template:Mvar. This distance is zero if and only if the sum is convex.

Minkowski addition is the addition of the set members. For example, adding the set consisting of the integers zero and one to itself yields the set consisting of zero, one, and two:$$\{0,1\}+\{0,1\}=\{0+0,0+1,1+0,1+1\}=\{0,1,2\}.$$The subset of the integers Template:Math is contained in the interval of real numbers Template:Math, which is convex. The Shapley–Folkman lemma implies that every point in Template:Math is the sum of an integer from Template:Math and a real number from Template:Math.

The distance between the convex interval Template:Math and the non-convex set Template:Math equals one-half:

$\frac{1}{2}=|1-\frac{1}{2}|=|0-\frac{1}{2}|=|2-\frac{3}{2}|=|1-\frac{3}{2}|.$

However, the distance between the average Minkowski sum

$\frac{1}{2}(\{0,1\}+\{0,1\})=\{0,\frac{1}{2},1\}$

and its convex hull Template:Math is only Template:Math, which is half the distance (Template:Math) between its summand Template:Math and Template:Math. As more sets are added together, the average of their sum "fills out" its convex hull: The maximum distance between the average and its convex hull approaches zero as the average includes more summands.

Preliminaries

The Shapley–Folkman lemma depends upon the following definitions and results from convex geometry.

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 Template:Mvar and Template:Mvar. Two points in the Cartesian plane can be added coordinate-wise:

$(x_1,y_1)+(x_2,y_2)=(x_1+x_2,y_1+y_2);$

further, a point can be multiplied by each real number Template:Mvar coordinate-wise:

$\lambda (x,y)=(\lambda x,\lambda y).$

More generally, any real vector space of (finite) dimension Template:Mvar can be viewed as the set of all [[tuple|Template:Mvar-tuple]]s of Template:Mvar real numbers Template:Math 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.

Convex sets

In a real vector space, a non-empty set Template:Mvar is defined to be convex if, for each pair of its points, every point on the line segment that joins them is still in Template:Mvar. For example, a solid disk $\bullet$ is convex but a circle $\circ$ is not, because it does not contain a line segment joining its points $\oslash$; the non-convex set of three integers Template:Math is contained in the interval Template:Math, 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 or vacuously, depending on the author.

More formally, a set Template:Mvar is convex if, for all points Template:Mathand Template:Math in Template:Mvar and for every real number Template:Mvar in the unit interval Template:Math, the point

$(1-\lambda )v_1+\lambda v_2$

is a member of Template:Mvar.

By mathematical induction, a set Template:Mvar is convex if and only if every convex combination of members of Template:Mvar also belongs to Template:Mvar. By definition, a convex combination of an indexed subset Template:Math of a vector space is any weighted average Template:Math for some indexed set of non-negative real numbers Template:Math satisfying the equation Template:Math.

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.

Convex hull

In the convex hull of the red set, each blue point is a convex combination of some red points.

For every subset Template:Mvar of a real vector space, its Template:Nowrap is the minimal convex set that contains Template:Mvar. Thus Template:Math is the intersection of all the convex sets that cover Template:Mvar. The convex hull of a set can be equivalently defined to be the set of all convex combinations of points in Template:Mvar. For example, the convex hull of the set of integers Template:Math is the closed interval of real numbers Template:Math, which contains the integer end-points. The convex hull of the unit circle is the closed unit disk, which contains the unit circle.

Minkowski addition

Minkowski addition of sets. The sum of the squares $Q_1=[0,1{]}^2$ and $Q_2=[1,2{]}^2$ is the square $Q_1+Q_2=[1,3{]}^2$.

In any vector space (or algebraic structure with addition), Template:Mvar, the Minkowski sum of two non-empty sets Template:Math is defined to be the element-wise operation Template:Math (See also .) For example,

$\{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 $\sum _{n=1}^N{Q}_n=Q_1+Q_2+\dots +Q_N.$ By the principle of induction it is easy to see that

$\sum _{n=1}^N{Q}_n=\{\sum _{n=1}^N{q}_n\mid q_n\in Q_n,1\le n\le N\}.$

Convex hulls of Minkowski sums

Minkowski addition behaves well with respect to taking convex hulls. Specifically, for all subsets Template:Math of a real vector space, Template:Mvar, the convex hull of their Minkowski sum is the Minkowski sum of their convex hulls. That is,

$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(A+B)=\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(A)+\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(B).$

And by induction it follows that

$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(\sum _{n=1}^N{Q}_n)=\sum _{n=1}^N\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(Q_n)$

for any Template:Math and non-empty subsets Template:Math.

Statements of the three main results

Notation

Template:Mvar and Template:Mvar represent positive integers. Template:Mvar is the dimension of the ambient space Template:Math.

Template:Math are nonempty, bounded subsets of Template:Math. They are also called "summands". Template:Mvar is the number of summands.

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

Template:Mvar represents an arbitrary vector in Template:Math.

Shapley–Folkman lemma

Since $\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(Q)=\sum _{n=1}^N\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(Q_n)$, for any Template:Math, there exist elements Template:Math such that $\sum _{n=1}^N{q}_n=x$. The Shapley–Folkman lemma refines this statement.

For example, every point in Template:Math is the sum of an element in Template:Math and an element in Template:Math.

Shuffling indices if necessary, this means that every point in Template:Math can be decomposed as

$x=\sum _{n=1}^D{q}_n+\sum _{n=D+1}^N{q}_n$

where Template:Math for Template:Math and Template:Math for Template:Math. Note that the reindexing depends on the point Template:Mvar.

The lemma may be stated succinctly as

$\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\left(\sum _{n=1}^N{Q}_n\right)\subseteq \bigcup _{I\subseteq \{1,2,\dots N\}:|I|=D}(\sum _{n\in I}\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(Q_n)+\sum _{n\notin I}{Q}_n).$

The converse of Shapley–Folkman lemma

In particular, the Shapley–Folkman lemma requires the vector space to be finite-dimensional.

Shapley–Folkman theorem

Shapley and Folkman used their lemma to prove the following theorem, which quantifies the difference between Template:Mvar and Template:Math using squared Euclidean distance.

For any nonempty subset $S\subseteq {ℝ}^D$ and any point $x\in {ℝ}^D,$ define their squared Euclidean distance to be the infimum$$d^2(x,S)=\underset{y\in S}{\inf }\Vert x-y{\Vert }^2.$$More generally, for any two nonempty subsets $S,S^{\prime }\subseteq {ℝ}^D,$ define$$d^2(S,S^{\prime })=\underset{x\in S,y\in S^{\prime }}{\inf }\Vert x-y{\Vert }^2.$$Note that $d^2(x,S)=(\underset{y\in S}{\inf }\Vert x-y\Vert {)}^2,$ so we can simply write $d^2(x,S)=d(x,S{)}^2,$ where $d(x,S)=\underset{y\in S}{\inf }\Vert x-y\Vert .$ Similarly, $d^2(S,S^{\prime })=d(S,S^{\prime }{)}^2.$

For example, $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 Template:Mvar is by upper-bounding $d^2(\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(Q),Q).$

For any bounded subset $S\subset {ℝ}^D,$ define its circumradius $rad(S)$ to be the infimum of the radius of all balls containing it (as shown in the diagram). More formally, $$rad(S)\equiv \underset{x\in R^N}{\inf }\underset{y\in S}{\sup }\Vert x-y\Vert$$Now we can state

where we use the notation $\sum _{\max D}$ to mean "the sum of the Template:Mvar 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

$r(S)$

of a bounded subset

$S\subset {ℝ}^D$

to be the infimum of

$r$

such that, for any

$x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S)$

, there exists a ball

$B$

of radius

$r$

such that

$x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S\cap B)$

.

The circumradius (blue) and inner radius (green) of a point set (dark red, with its convex hull shown as the lighter red dashed lines). The inner radius is smaller than the circumradius except for subsets of a single circle, for which they are equal.

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

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

In particular, if we have an infinite sequence $(Q_n{)}_{n=1,2,...}$ of nonempty, bounded subsets of ${ℝ}^D$, and if there exists some $r_0\ge 0$ such that the inner radius of each $Q_n$ is upper-bounded by $r_0$, then $$d^2(\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}\left(\frac{1}{N}\sum _{n=1}^N{Q}_n\right),\frac{1}{N}\sum _{n=1}^N{Q}_n)\le \frac{D{r}_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, to the later Arrow and Hahn, Cassels, Schneider, etc. An abstract and elegant proof by Ekeland has been extended by Artstein. Different proofs have also appeared in unpublished papers. An elementary proof of the Shapley–Folkman lemma can be found in the book by Bertsekas, 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.

A proof of the results

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

The following "probabilistic" proof of Shapley–Folkman–Starr theorem is from.

We can interpret $\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S)$ in probabilistic terms: $\mathrm{\forall }x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S)$, since $x=\sum w_n{q}_n$ for some $q_n\in S$, we can define a random vector $X$, finitely supported in $S$, such that $Pr(X=q_n)=w_n$, and $x=𝔼[X]$.

Then, it is natural to consider the "variance" of a set $S$ as$$Var(S):=\underset{x\in \mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S)}{\sup }\underset{𝔼[X]=x,X\text{ is finitely supported in }S}{\inf }Var[X]$$With that, $d(S,\mathrm{C}\mathrm{o}\mathrm{n}\mathrm{v}(S){)}^2\le Var(S)\le r(S)\le rad(S)$.Template:Math proofTemplate:Math proof

History

A Winner of the 2012 Nobel Award in Economics, Lloyd Shapley proved the Shapley–Folkman lemma with Jon Folkman.

The lemma of Lloyd Shapley and Jon Folkman was first published by the economist Ross M. Starr, who was investigating the existence of economic equilibria while studying with Kenneth Arrow. In his paper, Starr studied a convexified economy, in which non-convex sets were replaced by their convex hulls; Starr proved that the convexified economy has equilibria that are closely approximated by "quasi-equilibria" of the original economy; moreover, he proved that every quasi-equilibrium has many of the optimal properties of true equilibria, which are proved to exist for convex economies.

Following Starr's 1969 paper, the Shapley–Folkman–Starr results have been widely used to show that central results of (convex) economic theory are good approximations to large economies with non-convexities; for example, quasi-equilibria closely approximate equilibria of a convexified economy. "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Roger Guesnerie.

The topic of non-convex sets in economics has been studied by many Nobel laureates: Shapley himself (2012), Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008), and Paul Samuelson (1970); the complementary topic of convex sets in economics has been emphasized by these laureates, along with Leonid Hurwicz, Leonid Kantorovich (1975), and Robert Solow (1987).

Applications

The Shapley–Folkman lemma enables researchers to extend results for Minkowski sums of convex sets to sums of general sets, which need not be convex. Such sums of sets arise in economics, in mathematical optimization, and in probability theory; in each of these three mathematical sciences, non-convexity is an important feature of applications.

Economics

The consumer prefers every basket of goods on the indifference curve I₃ over each basket on  I₂. The basket (Q_x, Q_y), where the budget line (shown in blue) supports I₂, is optimal and also feasible, unlike any basket lying on  I₃ which is preferred but unfeasible.

Template:See also 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.

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.

Non-convex preferences

When the consumer's preferences have concavities, the consumer may jump between two separate optimal baskets.

Template:See also However, if a preference set is non-convex, then some prices determine a budget-line that supports two separate optimal-baskets. For example, we can imagine that, for zoos, a lion costs as much as an eagle, and further that a zoo's budget suffices for one eagle or one lion. We can suppose also that a zoo-keeper views either animal as equally valuable. In this case, the zoo would purchase either one lion or one eagle. Of course, a contemporary zoo-keeper does not want to purchase half of an eagle and half of a lion (or a griffin)! Thus, the zoo-keeper's preferences are non-convex: The zoo-keeper prefers having either animal to having any strictly convex combination of both.

When the consumer's preference set is non-convex, then (for some prices) the consumer's demand is not connected; a disconnected demand implies some discontinuous behavior by the consumer, as discussed by Harold Hotelling:

If indifference curves for purchases be thought of as possessing a wavy character, convex to the origin in some regions and concave in others, we are forced to the conclusion that it is only the portions convex to the origin that can be regarded as possessing any importance, since the others are essentially unobservable. They can be detected only by the discontinuities that may occur in demand with variation in price-ratios, leading to an abrupt jumping of a point of tangency across a chasm when the straight line is rotated. But, while such discontinuities may reveal the existence of chasms, they can never measure their depth. The concave portions of the indifference curves and their many-dimensional generalizations, if they exist, must forever remain in unmeasurable obscurity.

The difficulties of studying non-convex preferences were emphasized by Herman Wold and again by Paul Samuelson, who wrote that non-convexities are "shrouded in eternal darkness ...",Template:Efn according to Diewert.

Nonetheless, non-convex preferences were illuminated from 1959 to 1961 by a sequence of papers in The Journal of Political Economy (JPE). The main contributors were Farrell, Bator, Koopmans, and Rothenberg. In particular, Rothenberg's paper discussed the approximate convexity of sums of non-convex sets. These JPE-papers stimulated a paper by Lloyd Shapley and Martin Shubik, which considered convexified consumer-preferences and introduced the concept of an "approximate equilibrium". The JPE-papers and the Shapley–Shubik paper influenced another notion of "quasi-equilibria", due to Robert Aumann.

Starr's 1969 paper and contemporary economics

Kenneth Arrow (1972 Nobel laureate) helped Ross M. Starr to study non-convex economies.

Previous publications on non-convexity and economics were collected in an annotated bibliography by Kenneth Arrow. He gave the bibliography to Starr, who was then an undergraduate enrolled in Arrow's (graduate) advanced mathematical-economics course. In his term-paper, Starr studied the general equilibria of an artificial economy in which non-convex preferences were replaced by their convex hulls. In the convexified economy, at each price, the aggregate demand was the sum of convex hulls of the consumers' demands. Starr's ideas interested the mathematicians Lloyd Shapley and Jon Folkman, who proved their eponymous lemma and theorem in "private correspondence", which was reported by Starr's published paper of 1969.

In his 1969 publication, Starr applied the Shapley–Folkman–Starr theorem. Starr proved that the "convexified" economy has general equilibria that can be closely approximated by "quasi-equilibria" of the original economy, when the number of agents exceeds the dimension of the goods: Concretely, Starr proved that there exists at least one quasi-equilibrium of prices p_opt with the following properties:

• For each quasi-equilibrium's prices p_opt, all consumers can choose optimal baskets (maximally preferred and meeting their budget constraints).
• At quasi-equilibrium prices p_opt in the convexified economy, every good's market is in equilibrium: Its supply equals its demand.
• For each quasi-equilibrium, the prices "nearly clear" the markets for the original economy: an upper bound on the distance between the set of equilibria of the "convexified" economy and the set of quasi-equilibria of the original economy followed from Starr's corollary to the Shapley–Folkman theorem.

Starr established that

"in the aggregate, the discrepancy between an allocation in the fictitious economy generated by [taking the convex hulls of all of the consumption and production sets] and some allocation in the real economy is bounded in a way that is independent of the number of economic agents. Therefore, the average agent experiences a deviation from intended actions that vanishes in significance as the number of agents goes to infinity".

Following Starr's 1969 paper, the Shapley–Folkman–Starr results have been widely used in economic theory. Roger Guesnerie summarized their economic implications: "Some key results obtained under the convexity assumption remain (approximately) relevant in circumstances where convexity fails. For example, in economies with a large consumption side, preference nonconvexities do not destroy the standard results". "The derivation of these results in general form has been one of the major achievements of postwar economic theory", wrote Guesnerie. The topic of non-convex sets in economics has been studied by many Nobel laureates: Arrow (1972), Robert Aumann (2005), Gérard Debreu (1983), Tjalling Koopmans (1975), Paul Krugman (2008), and Paul Samuelson (1970); the complementary topic of convex sets in economics has been emphasized by these laureates, along with Leonid Hurwicz, Leonid Kantorovich (1975), and Robert Solow (1987). The Shapley–Folkman–Starr results have been featured in the economics literature: in microeconomics, in general-equilibrium theory, in public economics (including market failures), as well as in game theory, in mathematical economics, and in applied mathematics (for economists). The Shapley–Folkman–Starr results have also influenced economics research using measure and integration theory.

Mathematical optimization

A function is convex if the region above its graph is a convex set.

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.

Preliminaries of optimization theory

Nonlinear optimization relies on the following definitions for functions:

• The graph of a function f is the set of the pairs of arguments x and function evaluations f(x)

Graph(f) = { (x, f(x) ) }

• The epigraph of a real-valued function f is the set of points above the graph

The sine function is non-convex.

Epi(f) = { (x, u) : f(x) ≤ u }.

• A real-valued function is defined to be a convex function if its epigraph is a convex set.

For example, the quadratic function f(x) = x² is convex, as is the absolute value function g(x) = |x|. However, the sine function (pictured) is non-convex on the interval (0, π).

Additive optimization problems

In many optimization problems, the objective function f is separable: that is, f is the sum of many summand-functions, each of which has its own argument:

f(x) = f( (x₁, ..., x _$N$) ) = Σ f_n(x_n).

For example, problems of linear optimization are separable. Given a separable problem with an optimal solution, we fix an optimal solution

x_min = (x₁, ..., x _$N$)_min

with the minimum value Template:Nowrap For this separable problem, we also consider an optimal solution (x_min, f(x_min) ) to the "convexified problem", where convex hulls are taken of the graphs of the summand functions. Such an optimal solution is the limit of a sequence of points in the convexified problem

(x_j, f(x_j) ) ∈  Σ Conv (Graph( f_n ) ).Template:Efn

Of course, the given optimal-point is a sum of points in the graphs of the original summands and of a small number of convexified summands, by the Shapley–Folkman lemma.

This analysis was published by Ivar Ekeland in 1974 to explain the apparent convexity of separable problems with many summands, despite the non-convexity of the summand problems. In 1973, the young mathematician Claude Lemaréchal was surprised by his success with convex minimization methods on problems that were known to be non-convex; for minimizing nonlinear problems, a solution of the dual problem need not provide useful information for solving the primal problem, unless the primal problem be convex and satisfy a constraint qualification. Lemaréchal's problem was additively separable, and each summand function was non-convex; nonetheless, a solution to the dual problem provided a close approximation to the primal problem's optimal value. Ekeland's analysis explained the success of methods of convex minimization on large and separable problems, despite the non-convexities of the summand functions. Ekeland and later authors argued that additive separability produced an approximately convex aggregate problem, even though the summand functions were non-convex. The crucial step in these publications is the use of the Shapley–Folkman lemma. Template:Efn The Shapley–Folkman lemma has encouraged the use of methods of convex minimization on other applications with sums of many functions.

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 QTemplate:'s convex hull; this equality implies that the Shapley–Folkman–Starr results are useful in probability theory. In the other direction, probability theory provides tools to examine convex sets generally and the Shapley–Folkman–Starr results specifically. The Shapley–Folkman–Starr results have been widely used in the probabilistic theory of random sets, for example, to prove a law of large numbers, a central limit theorem, and a large-deviations principle. 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. 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. 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 Template:Nowrap is a vector measure, where Template:Nowrap is defined for every event ω by

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

Lyapunov's theorem has been used in economics, in ("bang-bang") control theory, and in statistical theory. Lyapunov's theorem has been called a continuous counterpart of the Shapley–Folkman lemma, which has itself been called a discrete analogue of Lyapunov's theorem. Template:Clear

References

• Template:Cite journal
• Template:Cite book
• Template:Cite journal Republished in a festschrift for Robert J. Aumann, winner of the 2008 Nobel Prize in Economics:
  • Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book Reprint of (1982) Academic Press.
• Template:Cite journal Proceedings of 1981 IEEE Conference on Decision and Control, San Diego, CA, December 1981, pp. 432–443.
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite report
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite report
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite book. Reprint of the 1970 (Template:MR) Princeton Mathematical Series 28
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book English translation of the (1998) French Microéconomie: Les défaillances du marché (Economica, Paris)
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite book
• Template:Cite book
• Template:Cite journal
• Template:Cite journal
• Template:Cite journal
• Template:Cite book

External links

• Template:Cite book
• Template:Cite book
• Template:Cite web