Minimizing $(q_1, q_2, \dots, q_K) \mapsto \left(\sum_{i=1}^K\frac{p_i^2\sigma_i^2}{q_i}\right)\left( \sum_{i=1}^Kq_i\tau_i\right)$ with a constraint

Question

$$ \begin{array}{ll} \underset {q_1, q_2, \dots, q_K} {\text{minimize}} & \displaystyle \left( \sum\limits_{i=1}^K \frac{p_i^2\sigma_i^2}{q_i} \right) \left( \sum\limits_{i=1}^K q_i\tau_i\right) \\ \text{subject to} & \displaystyle \sum\limits_{i=1}^K q_i = 1 \end{array} $$

It turns out that, the optimal $q_i$ is

$$ q_i^* = \dfrac{\frac{p_i\sigma_i}{\sqrt{\tau_i}}}{\sum\limits_{\ell = 1}^K \dfrac{p_{\ell}\sigma_{\ell}}{\sqrt{\tau_{\ell}}}}.$$

The first method that comes to mind is by using Lagrangian method. I have $$ \mathcal{L}(q,\lambda) = \left(\sum_{i=1}^K\frac{p_i^2\sigma_i^2}{q_i}\right)\left( \sum_{i=1}^Kq_i\tau_i\right) + \lambda\left(\sum_{i=1}^Kq_i - 1 \right). $$ Then, $$ \frac{\partial \mathcal{L}}{\partial q_j} = \left(-\frac{p_i^2\sigma_i^2}{q_i^2} \right)\left( \sum_{i=1}^Kq_i\tau_i\right) + \tau_j\left(\sum_{i=1}^K\frac{p_i^2\sigma_i^2}{q_i}\right) + \lambda. $$ So, $\frac{\partial \mathcal{L}}{\partial q_j} = 0$ implies $$ q_j = \frac{p_j\sigma_j\sqrt{\sum_{\ell = 1}^Kq_{\ell}\tau_{\ell}}}{\sqrt{\tau_j\sum_{\ell = 1}^K\frac{p_{\ell}^2q_{\ell}^2}{q_{\ell}} + \lambda}}. $$ Usually, to find $\lambda$ I would just solve $$ \sum_{j=1}^K \frac{p_j\sigma_j\sqrt{\sum_{\ell = 1}^Kq_{\ell}\tau_{\ell}}}{\sqrt{\tau_j\sum_{\ell = 1}^K\frac{p_{\ell}^2q_{\ell}^2}{q_{\ell}} + \lambda}} = 1 $$ for $\lambda$. But the equation looks very difficult to solve. Is there a trick that I can use to solve this?

---

Motivation

This question comes from a theoretic study of Monte Carlo simulation for reducing variance. One technique to reduce variance is called stratified sampling. The idea is to create partition of the population you want to sample from. But, how do we choose the allocation? This optimization problem is to find the optimal allocation.

Answer 1

Applying the Cauchy–Schwarz inequality:

$$\left( \sum_{i=1}^K\frac{p_i^2\sigma_i^2}{q_i} \right) \left( \sum\limits_{i=1}^K q_i\tau_i\right) \ge \left(\sum_{i=1}^K \frac{p_i\sigma_i}{\sqrt{q_i}}\cdot \sqrt{q_i\tau_i}\right)^2 =\left(\sum_{i=1}^K p_i\sigma_i \sqrt{\tau_i}\right)^2$$

The equality occurs if and only if

$$ \frac{p_1\sigma_1}{\sqrt{q_1}}\cdot \frac{1}{\sqrt{q_1\tau_1}} =\dots=\frac{p_K\sigma_K}{\sqrt{q_K}}\cdot \frac{1}{\sqrt{q_K\tau_K}} $$ $$\iff \frac{q_1}{p_1\sigma_1\cdot\frac{1}{\sqrt{\tau_1}}}=\dots=\frac{q_K}{p_K\sigma_K\cdot\frac{1}{\sqrt{\tau_K}}} \tag{1} $$

With the condition $\sum_{i=1}^K q_i = 1$, from $(1)$, we can deduce that the equality occurs if and only if $$ (1) \iff \frac{q_1}{p_1\sigma_1\cdot\frac{1}{\sqrt{\tau_1}}}=\dots=\frac{q_K}{p_K\sigma_K\cdot\frac{1}{\sqrt{\tau_K}}} = \frac{\sum_{l=1}^K q_l}{\sum_{l=1}^K p_l\sigma_l\cdot\frac{1}{\sqrt{\tau_l}}} = \frac{1}{\sum_{l=1}^Kp_l\sigma_l\cdot\frac{1}{\sqrt{\tau_l}}}$$ $$\iff \frac{q_i}{p_i\sigma_i\cdot\frac{1}{\sqrt{\tau_i}}}= \frac{1}{\sum_{l=1}^Kp_l\sigma_l\cdot\frac{1}{\sqrt{\tau_l}}}\hspace{1cm} \forall i=1,\dots,K$$

or

$$q_i =\frac{p_i\sigma_i\cdot\frac{1}{\sqrt{\tau_i}}}{\sum_{l=1}^Kp_l\sigma_l\cdot\frac{1}{\sqrt{\tau_l}}} \hspace{1cm} \forall i=1,\dots,K$$