3
$\begingroup$

Let $f(x) \in C[-1,2]$. Consider an optimization problem $ J[\mu] = \int\limits_{-1}^{2}f(x) \, \mu(dx) \to \max\limits_{\mu - \text{Borel probability measure}} $ with restriction $ \int\limits_{-1}^{2}x \, \mu(dx) = 0. $ Is it true that solution of this problem (maximal value of $J$) will not change if we replace $f$ by its concave envelope? If the answer is positive, what about optimal measure? Will it change, if it exists?

1 Answers 1

2

I assume that by the concave envelope of $f$ you mean $ g(x) = \sup_{a \le x, b \ge x} \frac{(b-x)f(a) + (x-a)f(b)}{b-a} $ It is true that the maximum of $J_g$ is the same as that of $J_f$, and any $\mu$ that maximizes $J_f[\mu]$ also maximizes $J_g[\mu]$. However, there may be $\mu$ that maximize $J_g[\mu]$, but not $J_f[\mu]$.

It is clear that $g(x) \ge f(x)$ for all $x$, hence $J_g[\mu] \ge J_f[\mu]$. To prove equality of the maxima it would then suffice to show that for every measure $\nu$ there is a measure $\mu$ such that $J_f[\mu] = J_g[\nu]$. In fact we can show that for every $\mu$ there is a $\nu$ such that $J_g[\mu] = J_g[\nu]$ and $\mu(f \ne g) = 0$.

First, observe that $f$ and $g$ are continuous, so the set of points where they differ is a union of pairwise disjoint open intervals ($f$ and $g$ necessarily agree on the endpoints of their domain) and $g$ is linear on the closure of each of these intervals. Now let $(a, b)$ be one of these intervals. If we define $\mu$ so that \begin{eqnarray} \mu((a, b)) &=& 0 \\ \mu(\{a\}) &=& \frac{1}{b-a} \int_a^b (b-x) \nu(dx) \\ \mu(\{b\}) &=& \frac{1}{b-a} \int_a^b (x-a) \nu(dx) \\ \mu|_{[a,b]^c} &=& \mu|_{[a,b]^c} \end{eqnarray} it is easy to verify that $\int_a^b \mu(dx) = \int_a^b \nu(dx)$ and $\int_a^b x \mu(dx) = \int_a^b x \nu(dx)$. It follows, since $g$ is linear on $[a,b]$, that $\int_a^b g(x) \mu(dx) = \int_a^b g(x) \nu(dx)$.

Performing this construction on all the intervals produces a measure $\mu$ that satisfies the constraints and for which $J_f(\mu) = J_g(\mu) = J_g(\nu)$. This shows that the maximum of $J_f$ can not be less than that of $J_g$. It also implies that a maximizer of $J_f$ is also a maximizer of $J_g$.

For a simple example showing that a maximizer of $J_g$ does not necessarily maximize $J_f$, take $f(x) = x^2$. The unique maximizer for $J_f$ is then a discrete measure with $\mu(-1) = \frac23, \mu(2) = \frac13$. On the other hand, $g$ is linear, so any probability measure with zero mean will maximize $J_g$.

(For what it's worth, I suspect that the maximum of $J_g$ is always equal to $g(0)$, which by the construction above would imply that $J_f$ is always maximized by a measure consisting of one or two point masses.)