# Finding maximum of sum of square roots

Let $$0 \leq x_1, \dots, x_n \leq 1$$ and $$\sum_{i=1}^n x_i = 1$$, i.e. $$x_i$$ form a probability distribution. Let $$m_1, \dots, m_n \geq 1$$ be fixed numbers. I'm looking for $$x_i$$ that maximize the following:

\begin{align} \sum_i \frac{\sqrt{x_i}}{\sqrt{m_i}} \end{align}

I was able to show that for case of $$n = 2$$ (where we only have a single variable) the maximum is at $$x_1 = \frac{m_2}{m_1+m_2}$$ and $$x_1 = 1-x_2$$. Let $$M = \sum_i m_i$$. From this, I think $$x_i$$ that maximize the above might be

$$x_i \propto {M - m_i}?$$

• Your guess isn't true in general, because then $\sum x_i$ would equal $n-1$, which is only equal to $1$ if $n = 2$. May 19 at 0:21
• @VarunVejalla Right! I fixed my question to reflect that.
– KRL
May 19 at 0:26
• I would have said your $n=2$ example suggests $x_1 m_1 = x_2m_2$ leading to the guess $x_i \propto \frac1{m_i}$ May 19 at 0:38

$$L(x, \lambda) = \sum_i \frac{\sqrt{x_i}}{\sqrt{m_i}} - \lambda\left(\sum_i x_i - 1\right)$$
Then taking the derivatives with respect to the $$x_i$$, you'd need $$\frac{1}{2\sqrt{x_i}\sqrt{m_i}}-\lambda=0$$ for all $$i$$. This can be solved for $$x_i$$ as $$x_i=\frac{1}{4\lambda^2 m_i}$$ and since $$\sum_i x_i$$ must equal $$1$$, you have that $$\sum_i \frac{1}{4\lambda^2 m_i} = 1 \to \lambda = \frac{1}{2}\sqrt{\sum_i \frac{1}{m_i} }$$
So $$x_i = \frac{1}{m_i\sum_{i}\frac{1}{m_i} }$$ which yields a maximum of $$\sqrt{\sum_i \frac{1}{m_i}}$$
Apply the Cauchy-Schwarz inequality $$\left(\sum \frac{\sqrt{x_i}}{\sqrt{m_i}}\right)^2 \le \sum \frac{1}{m_i} \cdot \sum x_i$$ with equality only when $$x_i$$ and $$\frac{1}{m_i}$$ are proportional.