3
$\begingroup$

Consider an optimization problem as follows: $$ \min\mathbb E_w[f_0(w)] \mathrm{\,\,\,\,\,\ s.t.\,\,\,\,} E_w[f_i(w)]\leq 0 ,\,\,\, i=1,\dots, k $$ where the maximum is taken over $\mathscr M$, the space of probability measureson $(X,\mathscr B)$. Indeed the problem can be written as : $$ \min_{\mu\in\mathscr M} \int_Xf_0\mathrm{d}\mu \mathrm{\,\,\,\,\,\ s.t.\,\,\,\,} \int_Xf_i\mathrm d\mu\leq 0 ,\,\,\, i=1,\dots, k. (\star) $$ This problem occurs particularly in information theory where the goal is to maximize certain entropy function or mutual information subject to some assumptions on the random variable variance.


Ex.1. Differential entropy of a continuous random variable $Y$ with the variance bounded by $\sigma^2$ is $\frac 12\log(2\pi e \sigma^2)$ and it is obtained by choosing $Y$ as Gaussian. This can be proved using positivity of KL-divergence $D(f||g)$ and choosing $g$ Gaussian distribution.


Similar statements can be found in different entropy maximization problems with similar proof techniques. However, the previous example is rather an exception and the problem can easily get more complicated, for instance when the difference of two mutual information should be maximized.

Apart from information theoretic context, the problem $(\star)$ is independently interesting.


Here is the question: Has there been any work on solving $(*)$ in a systematic way, something like classical optimization theory? Are there any special cases of the problem, like those mentioned above, for which the problem can be solved?


Remark 1 I can spot a similarity with Kantorovich's formulation of optimal transportation problem.


Update 1 From the comments below, a solution can be found when $f_i$'s are not changing with the choice of $\mu$. An answer can be found here: semi-infinite linear programming. In this case, the objective function and constraints are linear functional of $\mu$ and therefore one can apply similar methods from linear programming with proper considerations. The solution to this problem is a finite measure with $k+1$ points.

$\endgroup$
  • 2
    $\begingroup$ For starters, if $X$ is Polish and the functions $f_i$ are continuous, then existence of a minimizer should follow from the fact that $\mathscr{M}$ is weakly compact. $\endgroup$ – Nate Eldredge Oct 15 '15 at 21:39
  • 1
    $\begingroup$ Isn't this just a semi-infinite linear program? You have a finite constraint space $\mathbb{R}^k$, which means you should be able to formulate a dual program with $k$ variables. See mathoverflow.net/questions/210376/… $\endgroup$ – Tom Solberg Oct 15 '15 at 22:42
  • $\begingroup$ @TomSolberg, Thanks a lot; Interestingly I knew but forgot about Miacheal's work on a very related problem to OP. So thanks! However, my question is a little bit more general; here $f_0$ can depend on the measure, hence perturbing the linear programming analogy; For instance take $f_0=\log\frac{\textrm d\mu}{\textrm dm}$ where $m$ is Lebesgue measure. $\endgroup$ – Arash Oct 16 '15 at 11:24
  • $\begingroup$ @TomSolberg, The answer is insightful but how far we can push the LP analogy; can we use convex optimization analogy? I am not sure because, as stated in the OP, for some cases, the solution is a continuous measure and therefore no hope for a discrete measure to be the solution. $\endgroup$ – Arash Oct 16 '15 at 11:30
  • $\begingroup$ @Arash Differential entropy problem is a terrible example because it is not a problem about a functional of this type: it involves a non-linear expression in the density of the probability measure. $\endgroup$ – fedja Oct 18 '15 at 0:38

Your Answer

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

Browse other questions tagged or ask your own question.