A simple infinite dimensional optimization problem

Question

I'd be grateful for a reference for the following result, which I believe to be true, and should be well-known.

Let the continuous functions $f_0,f_1,\cdots,f_n: [0,1]\rightarrow [0,\infty)$ be given and consider the problem of maximizing the integral $$\int_0^1 f_0(x)d\mu(x)$$ over all positive Borel measures $\mu$ on [0,1], which satisfy the constraints $$\int_0^1 f_k(x)d\mu(x)=1,\;\;1\leq k\leq n.$$

Then, if a solution exists, the maximum is attained by a linear combination of (at most) $n$ shifted $\delta$-functions: $$\mu=\sum_{j=1}^n \alpha_j\delta(x-x_j),\;\;\;x_j\in [0,1]$$

Answer 1

This is a particular case of the Generalized Moment Problem.

The result you are looking for can be found in the first chapter of Moments, Positive Polynomials and Their Applications by Jean-Bernard Lasserre (Theorem 1.3). The proof follows from a general result from measure theory.

Theorem. Let $f_1, \dots , f_m : X\to\mathbb R$ be Borel measurable on a measurable space $X$ and let $\mu$ be a probability measure on $X$ such that $f_i$ is integrable with respect to $\mu$ for each $i = 1, \dots, m$. Then there exists a probability measure $\nu$ with finite support on $X$, such that: $$\int_X f_id\mu=\int_Xf_i d\nu,\quad i = 1,\dots,m.$$ Moreover, the support of $\nu$ may consist of at most $m+1$ points.

Answer 2

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.

Answer 3

Let $E= C([0,1])$ and $E^* $ it's dual, the relative Borel measures on [0,1], and $E_+^* $ it's positive cone (the positive measures). The constraint is the w* closed convex subset C of $E^* $ obtained as intersection of $E^*_+ $ with the w* closed affine subspace of E

{ $m\in E^*: \langle m,f_k \rangle=1\; \forall k=1\dots n $ },$ \qquad $

It's not completely clear to me under what conditions on the $f_1,\dots ,f_n$ the convex C is not empty (e.g if $f_3=f_1+f_2$ the constraint is empty). I will assume therefore that (1) C is not empty.

Clearly, a necessary condition for the existence of the minimizer is also

$\mathrm{supp}(f_0) \subset \mathrm{supp}(f_1)\cup\dots \cup \mathrm{supp}(f_n).\qquad(2)$

Otherwise the functional to maximize is unbounded from above on the constraint C since e.g. C contains a whole half-line $t \delta_x +\mu$, with $t\geq0, $ $\ \mu\in C $, $f_0(x)>0$ and

$ x\notin \mathrm{supp}(f_1)\cup\dots \cup \mathrm{supp}(f_n). $

Assuming both necessity condition (1) and (2) (say wlog $f_0>0$ everywhere) C is non-empty, bounded, in fact w* compact by the Banach -Alaoglu theorem, and the functional to be maximized $m\mapsto \langle m,f_0 \rangle$ is linear and w* continuous (indeed it's the evaluation at $f_0$). So by compactness it attains a maximum. Moreover, any maximum point $\mu$ is attained at an extremal point of C.

The only non standard part is to recognize that in fact all extremal points of C are positive linear combinations of at most n measures $\delta_x.$ Indeed, if $\mu$ is an extremal point of C then for any $k=1,\dots ,n$ the restirction of $\mu$ to

$\mathrm{supp}(f_k) \setminus \bigcup_{j\neq k} \mathrm{supp}(f_j)$

is either zero or atomic, which implies $\mathrm{card}( \mathrm{supp}(\mu))\le n. $

Rmk: as a consequence the set C is not empty if and only if it containe a positive linear combination of n deltas. The case of probability measures, that apparently was not required by the initial question, is covered adding as n+1 th function the constant 1 (this authomatically satisfies (2)). So incidentally this is the proof of the above quoted theorem (with continuous $f_k$; the case of Borel measurable shouldn't be different).