Return to Answer

If we restrict to probability measures (you said you were also interested in this case) then $n$ atoms definitely do not suffice. To see this, let the $f_i$ be bump functions of height $n+1$ with disjoint support. Then any measure composed of $n$ atoms which satisfies the constraints necessarily has an objective value of zero. However with $n+1$ atoms (one of mass $\frac{1}{n+1}$ for each $i$ at a point where each $f_i$ takes the value $n+1$) we can achieve a positive objective value.

To prove that $n+1$ atoms suffice in general, define the map $f:[0,1]\to\mathbb{R}^{n+1}$ whose components are the $f_i$. Define $\Delta$ to be the set of Borel probability measures on $[0,1]$. Extend $f$ to $\Delta$ by linearity, defining $f(\mu) = \int f d\mu$. Our goal is to optimize the first coordinate over the set of points in the image $f(\Delta)$, so we will compute this set.

In fact $f(\Delta) = conv(f([0,1]))$ where $conv$ denotes convex hull. The inclusion $\supseteq$ follows from linearity of integration. The reverse follows because $f([0,1])$ is compact, hence so is its convex hull. For any point $y$ not in $conv(f([0,1]))$ there is a linear inequality satisfied by all points of $f([0,1])$ but not by $y$. By linearity of integration such an inequality is satisfied on $f(\Delta)$, so $y\not\in f(\Delta)$.

By Caratheodory's Theorem any point in $conv(f([0,1]))$ can be written as a convex combination of at most $n+2$ elements of $f([0,1])$ (one more than the dimension $n+1$ of the ambient space). An extension due to Hanner and Radstrom shows that we can actually use $n+1$ elements because $f([0,1])$ is connected, $f$ being continuous.

Suppose the problem is feasible. Let $\mu$ be any optimal solution, which exists because the feasible set is weakly compact (or one can give a more elementary argument in $\mathbb{R}^{n+1}$). Then any $\nu$ satisfying $f(\mu) = f(\nu)$ is also optimal. The above argument shows that there exists such a $\nu$ supported on at most $n+1$ points.

If we restrict to probability measures (you said you were also interested in this case) then $n$ atoms definitely do not suffice. To see this, let the $f_i$ be bump functions of height $n+1$ with disjoint support. Then any measure composed of $n$ atoms which satisfies the constraints necessarily has an objective value of zero. However with $n+1$ atoms (one of mass $\frac{1}{n+1}$ for each $i$ at a point where each $f_i$ takes the value $n+1$) we can achieve a positive objective value.

To prove that $n+1$ atoms suffice in general, define the map $f:[0,1]\to\mathbb{R}^{n+1}$ whose components are the $f_i$. Define $\Delta$ to be the set of Borel probability measures on $[0,1]$. Extend $f$ to $\Delta$ by linearity, defining $f(\mu) = \int f d\mu$. Our goal is to optimize the first coordinate over the set of points in the image $f(\Delta)$, so we will compute this set.

In fact $f(\Delta) = conv(f([0,1]))$ where $conv$ denotes convex hull. The inclusion $\supseteq$ follows from linearity of integration. The reverse follows because $f([0,1])$ is compact, hence so is its convex hull. For any point $y$ not in $conv(f([0,1]))$ there is a linear inequality satisfied by all points of $f([0,1])$ but not by $y$. By linearity of integration such an inequality is satisfied on $f(\Delta)$, so $y\not\in f(\Delta)$.

By Caratheodory's Theorem any point in $conv(f([0,1]))$ can be written as a convex combination of at most $n+2$ elements of $f([0,1])$ (one more than the dimension $n+1$ of the ambient space). An extension due to Hanner and Radstrom shows that we can actually use $n+1$ elements because $f([0,1])$ is connected, $f$ being continuous.

Suppose the problem is feasible. Let $\mu$ be any optimal solution, which exists because the feasible set is weakly compact (or one can give a more elementary argument in $\mathbb{R}^{n+1}$). Then any $\nu$ satisfying $f(\mu) = f(\nu)$ is also optimal. The above argument shows that there exists such a $\nu$ supported on at most $n+1$ points.

Note that this argument would work equally well to find such a $\nu$ satisfying $n+1$ constraints rather than optimizing over those satisfying $n$ constraints. Also, the argument allows for constraints of a much more general form than just equations. I have a feeling that using the structure of the given problem in a slightly different way may allow one to avoid the Hanner and Radstrom result and give a bound of $n+1$ without using the fact that the space on which the $f_i$ were defined was connected (i.e. replacing $[0,1]$ with an arbitrary compact Hausdorff space), but I am not sure.

If we restrict to probability measures (you said you were also interested in this case) then $n$ atoms definitely does not suffice. To see this, let the $f_i$ be bump functions of height $n+1$ with disjoint support. Then any measure composed of $n$ atoms which satisfies the constraints necessarily has an objective value of zero. However with $n+1$ atoms (one of mass $\frac{1}{n+1}$ for each $i$ at a point where each $f_i$ takes the value $n+1$) we can achieve a positive objective value.

It is true that $n+1$ atoms suffice in general, though this relies on the fact that the domain of the functions is $[0,1]$ (in particular connected -- for other domains I believe the bound would actually be $n+2$). I will look up the reference later today and post it.

If we restrict to probability measures (you said you were also interested in this case) then $n$ atoms definitely do not suffice. To see this, let the $f_i$ be bump functions of height $n+1$ with disjoint support. Then any measure composed of $n$ atoms which satisfies the constraints necessarily has an objective value of zero. However with $n+1$ atoms (one of mass $\frac{1}{n+1}$ for each $i$ at a point where each $f_i$ takes the value $n+1$) we can achieve a positive objective value.

To prove that $n+1$ atoms suffice in general, define the map $f:[0,1]\to\mathbb{R}^{n+1}$ whose components are the $f_i$. Define $\Delta$ to be the set of Borel probability measures on $[0,1]$. Extend $f$ to $\Delta$ by linearity, defining $f(\mu) = \int f d\mu$. Our goal is to optimize the first coordinate over the set of points in the image $f(\Delta)$, so we will compute this set.

In fact $f(\Delta) = conv(f([0,1]))$ where $conv$ denotes convex hull. The inclusion $\supseteq$ follows from linearity of integration. The reverse follows because $f([0,1])$ is compact, hence so is its convex hull. For any point $y$ not in $conv(f([0,1]))$ there is a linear inequality satisfied by all points of $f([0,1])$ but not by $y$. By linearity of integration such an inequality is satisfied on $f(\Delta)$, so $y\not\in f(\Delta)$.

By Caratheodory's Theorem any point in $conv(f([0,1]))$ can be written as a convex combination of at most $n+2$ elements of $f([0,1])$ (one more than the dimension $n+1$ of the ambient space). An extension due to Hanner and Radstrom shows that we can actually use $n+1$ elements because $f([0,1])$ is connected, $f$ being continuous.

Suppose the problem is feasible. Let $\mu$ be any optimal solution, which exists because the feasible set is weakly compact (or one can give a more elementary argument in $\mathbb{R}^{n+1}$). Then any $\nu$ satisfying $f(\mu) = f(\nu)$ is also optimal. The above argument shows that there exists such a $\nu$ supported on at most $n+1$ points.

If we restrict to probability measures (you said you were also interested in this case) then $n$ atoms definitely does not suffice. To see this, let the $f_i$ be bump functions of height $n+1$ with disjoint support. Then any measure composed of $n$ atoms which satisfies the constraints necessarily has an objective value of zero. However with $n+1$ atoms (one of mass $\frac{1}{n+1}$ for each $i$ at a point where each $f_i$ takes the value $n+1$) we can achieve a positive objective value.

It is true that $n+1$ atoms suffice in general, though this relies on the fact that the domain of the functions is $[0,1]$ (in particular connected). I will look up the reference later today and post it.

If we restrict to probability measures (you said you were also interested in this case) then $n$ atoms definitely does not suffice. To see this, let the $f_i$ be bump functions of height $n+1$ with disjoint support. Then any measure composed of $n$ atoms which satisfies the constraints necessarily has an objective value of zero. However with $n+1$ atoms (one of mass $\frac{1}{n+1}$ for each $i$ at a point where each $f_i$ takes the value $n+1$) we can achieve a positive objective value.

It is true that $n+1$ atoms suffice in general, though this relies on the fact that the domain of the functions is $[0,1]$ (in particular connected -- for other domains I believe the bound would actually be $n+2$). I will look up the reference later today and post it.