# A simple infinite dimensional optimization problem

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]$$

-
I am familiar with such problems over the set of Borel probability measures, but not as much for all positive Borel measures. If you're interested in that problem too I can comment on it. In any case I am also interested in the general answer. –  Noah Stein May 24 '10 at 21:14
Yes, I would be interested to learn something about other optimization problems over probability measures. –  Guy Katriel May 24 '10 at 21:54
Some internet searching led me to this manuscript nicolapersico.com/files/linearprogram8.pdf which deals with the problem case $n=2$ (one constraint + the constraint of being a probability measure). However it is assumed there also that $f_0$ is increasing, and on the other a `generic' uniqueness theorem is proved. I don't understand exactly how this result is related to the approaches discussed by the responders below. –  Guy Katriel May 25 '10 at 4:38

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.

-
Thanks, that looks like a great source! One thing I don't see there is the statement that $n$ $delta$-functions are sufficient, where $n$ is the number of constraints. –  Guy Katriel May 24 '10 at 21:49
Thank you - that's exactly what I need. –  Guy Katriel May 24 '10 at 22:00
You're welcome. –  Andrey Rekalo May 24 '10 at 22:04
Note that that paper considers the slightly different case of finite positive Borel measures. I'm not sure if the case of arbitrary positive Borel measures would be different. –  Noah Stein May 24 '10 at 23:21
As Pietro noted, the condition that it be a probability measure is just one more linear constraint, which explains why in the above-quoted theorem it is $m+1$ points and not $m$. –  Guy Katriel May 25 '10 at 4:18

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.

-
Thank you for the nice argument. –  Guy Katriel May 25 '10 at 4:22
I wonder if there is any published source giving your argument. –  Guy Katriel May 25 '10 at 15:41
I always wonder what source to quote for this. I first saw it as Theorem $3.1.1$ in Volume $2$ of Karlin's <i>Mathematical methods and theory in games, programming, and economics</i> (I'm a game theorist). The weird thing about this reference though is that there's a book by Dover with the same title and author which says on the cover that it is two volumes bound as one. However, the "two volumes" are Volume 1 of the set mentioned above and some other book! So if you're looking in the library be sure to get volume 2 by itself. –  Noah Stein May 25 '10 at 16:42
I also cooked up a more topological proof as Theorem $2.1.21$ of my masters thesis which you can get from my webpage if you're interested. –  Noah Stein May 25 '10 at 16:44
Thank you very much! –  Guy Katriel May 25 '10 at 17:39

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).

-
The counterexample in Noah's answer shows that only $n$ Dirac measures may not be enough. –  Andrey Rekalo May 25 '10 at 2:16
uhm... does the counterxample assume that the support of $f_0$ is disjoint from the others? I explicitly excluded this case (the functional is unbounded) –  Pietro Majer May 25 '10 at 2:57
oh I see, it refers to probability measures (which not the original problem). –  Pietro Majer May 25 '10 at 3:15
note however that the constraint of being a probability measure corresponds to taking one more function $f_{n+1}=1$ (constant) :-) –  Pietro Majer May 25 '10 at 3:18
I guess to get the statement about extreme points you have to invoke the Caratheodory theorem, as in Noah's proof. –  Guy Katriel May 25 '10 at 4:30