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

  • 1
    $\begingroup$ 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. $\endgroup$ – Noah Stein May 24 '10 at 21:14
  • $\begingroup$ Yes, I would be interested to learn something about other optimization problems over probability measures. $\endgroup$ – Guy Katriel May 24 '10 at 21:54
  • $\begingroup$ 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. $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Guy Katriel May 24 '10 at 21:49
  • $\begingroup$ 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. $\endgroup$ – Noah Stein May 24 '10 at 23:21
  • $\begingroup$ 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$. $\endgroup$ – Guy Katriel May 25 '10 at 4:18
  • $\begingroup$ oops - thinking about it again, it seems to me that the statement in the theorem quoted above is not quite sufficient for proving the result I stated. Suppose that maximum in my problem is attained at some measure $\mu$, and you want to prove that this $\mu$ can be replaced by another measure supported on finitely many points. This new measure would have to satisfy $n+1$ conditions - the constraints + having the same value on $f_0$. But according to the above theorem this would require a combination of $n+1$ $\delta$-functions, not $n$, so there is a gap here. Or am I missing something? $\endgroup$ – Guy Katriel May 25 '10 at 7:26
  • $\begingroup$ Well, actually $n+2$ $\delta$-functions are required for an arbitrary measurable space $X$ according to the theorem in my answer. A refined argument as in Noah's answer shows that when $X=[0,1]$ $n+1$ $\delta$-functions are enough. $\endgroup$ – Andrey Rekalo May 25 '10 at 12:34

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.

| cite | improve this answer | |
  • $\begingroup$ I wonder if there is any published source giving your argument. $\endgroup$ – Guy Katriel May 25 '10 at 15:41
  • 1
    $\begingroup$ 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. $\endgroup$ – Noah Stein May 25 '10 at 16:42
  • $\begingroup$ 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. $\endgroup$ – Noah Stein May 25 '10 at 16:44

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

| cite | improve this answer | |
  • $\begingroup$ The counterexample in Noah's answer shows that only $n$ Dirac measures may not be enough. $\endgroup$ – Andrey Rekalo May 25 '10 at 2:16
  • $\begingroup$ 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) $\endgroup$ – Pietro Majer May 25 '10 at 2:57
  • $\begingroup$ oh I see, it refers to probability measures (which not the original problem). $\endgroup$ – Pietro Majer May 25 '10 at 3:15
  • $\begingroup$ note however that the constraint of being a probability measure corresponds to taking one more function $f_{n+1}=1$ (constant) :-) $\endgroup$ – Pietro Majer May 25 '10 at 3:18
  • $\begingroup$ I guess to get the statement about extreme points you have to invoke the Caratheodory theorem, as in Noah's proof. $\endgroup$ – Guy Katriel May 25 '10 at 4:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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