Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
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
add comment

3 Answers

up vote 5 down vote accepted

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.

share|improve this answer
    
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
show 2 more comments

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.

share|improve this answer
    
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
1  
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
add comment

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

share|improve this answer
    
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
show 3 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.