# Prove that this is the solution to the given minimization problem

I have the minimization problem

minimize $\displaystyle f_0 = \sum_{i=1}^{N} \mu_i \left( \left( 2^\frac{R_i}{\mu_i} - 1 \right) \right)$

with constraint

$\displaystyle\sum_{i=1}^{N} \mu_i = 1$

and believe that the solution is

$\displaystyle \mu_i = \frac{R_i}{\sum_{j=1}^{N} R_j}$.

The first derivative is $\displaystyle f_0^\prime = \sum_{i=1}^{N} \left( 2^\frac{{R}_i}{\mu_i} - \frac{{R}_i}{\mu_i} \rm{log}(2)2^\frac{R_i}{\mu_i} - 1 \right)$

$N$ and $R_i$ are given. I can show that for $i=2$, $f_0^\prime = 0$, by inserting $\mu_2 = 1 - \mu_1$ in $f_0$, taking the derivative and then inserting the solution.

But how can I show it for any $i$?

I couldn't just insert the solution into the first derivative, so I tried to argue that if it works for $i=2$ it would also work for higher $i$. Or that the problem can always be solved for $i=2$ and then subdivided further. But I am not sure.

Any hints are appreciated.

-
Which quantities are given parameter-values, which ones are variables? Why the $L$, the index ${}_0$, and what is $\overline{R_i}\$? – Christian Blatter Jul 2 '11 at 15:23
thx, I removed the unneeded indices. Calling the cost function $f_0$ is a convention. – Hauke Jul 2 '11 at 16:08

The usual Lagrange multiplier method works (if you are not familiar with the method, let me recommand reading the WP page before continuing, in particular you must realize that the quantity you denote by $f'_0$ simply does not enter the picture).
For every given $i$, the partial derivatives with respect to $\mu_i$ of the function $f_0$ to be minimized and of the constraint are $$2^{R_i/\mu_i}-1-(R_i/\mu_i)\log(2)2^{R_i/\mu_i}\quad\text{and}\quad 1\quad\text{respectively}.$$ Hence the former must not depend on $i$, that is, for a given $C$, $$2^{R_i/\mu_i}(1-\log(2)R_i/\mu_i)=C.$$ The function $x\mapsto 2^{x}(1-\log(2)x)$ is monotone on $x\ge0$ hence $R_i/\mu_i$ must not depend on $i$, that is, one must have $\mu_i=cR_i$ for a given $c$. Since $\sum\mu_i=1$, $1/c$ is the sum of $R_i$ over $i$ and you are done: the optimal vector $(\mu_i)$ is given by $$\mu_i=\frac{R_i}{R_1+\cdots+R_N}.$$
The function $x\mapsto 2^x$ is convex. Therefore by Jensen's inequality for arbitrary $\mu_i\geq0$ with $\sum_{i=1}^N \mu_i=1$ and arbitrary $x_i\in{\mathbb R}$ one has $$\sum_{i=1}^N \mu_i\ 2^{x_i}\geq 2^\sigma\ ,$$ where $\sigma:=\sum_{i=1}^N\mu_i x_i$ is the weighted arithmetic mean of the $x_i$. Now put $x_i:={R_i \over \mu_i}$ and obtain $$\sum_{i=1}^N \mu_i\ 2^{R_i / \mu_i}\geq 2^{\sum_i R_i}\ .$$ This can be interpreted as follows: Your function $f_0$ of the $\mu_i$ assumes its minimum $2^{\sum_i R_i}-1$ when all $x_i$ are equal to their common arithmetic mean $\sigma$, which in turn means that the $\mu_i$ have to be proportional to the $R_i$.