Lagrange multiplier and minimum variance

Question

Looking into a control variate technique of Monte Carlo simulation I have run into a cost-optimization problem that I'm not quite sure I understand. It seems it has to do with Lagrangian multipliers, but I am not positive about this so if someone can give a hint about the following problem I'll be very glad to hear his/her take on this.

Let's say we want to estimate $\mathbb E[f_1]$, defined as $$ \mathbb E[f_1] = \mathbb E[f_0] + \mathbb E[f_1 - f_0] $$ for which we can use the classical Monte Carlo estimator (I'm not writing it down since it is not crucial to the problem at hand).

If we define $C_0$ and $C_1$ to be the cost of $f_0$ and $(f_1-f_0)$ respectively, and $V_0$ and $V_1$ to be the variance of $f_0$ and $(f_1-f_0)$ respectively, then we can express the cost function as $$ N_0C_0 + N_1C_1 $$ and the variance as $$ N_0^{-1}V_0 + N_1^{-1}V_1 $$

Now the question is, how can we conclude from these two equations that for a fixed cost the variance is minimized by the expression below? $$ \frac{N_1}{N_0} = \frac{\sqrt{\frac{V_1}{C_1}}}{\sqrt{\frac{V_0}{C_0}}} $$

From some sources it seems like I need to use the Lagrangian multiplier and that this is just a simple cost minimization problem, but I'm not sure how to get to this result.

Answer 1

My understanding of the question is that you want to minimize $\frac{V_0}{N_0} + \frac{V_1}{N_1}$ given that $V_0,V_1,C_0V_0+C_1V_1$ are all held fixed. In this situation we can treat $V_0,V_1$ as parameters and solve the constrained minimization problem with the objective function $f(N_0,N_1)=\frac{V_0}{N_0}+\frac{V_1}{N_1}$ and the constraint $g(N_0,N_1)=C_0N_0+C_1N_1=C$ for some fixed $C$. To do this we introduce an additional variable $\lambda$, the Lagrange multiplier, and we solve the system of three equations:

$$\nabla f(N_0,N_1)=\lambda \nabla g(N_0,N_1) \\ g(N_0,N_1)=C.$$

The first two equations read:

$$-\frac{V_0}{N_0^2}=\lambda C_0 \\ -\frac{V_1}{N_1^2}=\lambda C_1.$$

Dividing these equations by each other we get

$$\frac{V_0 N_1^2}{V_1 N_0^2}=\frac{C_0}{C_1}.$$

Solving for $\frac{N_1}{N_0}$:

$$\frac{N_1}{N_0}=\sqrt{\frac{C_0 V_1}{C_1 V_0}}.$$

Note that this ratio can be found without knowing $C$. To actually find $N_0,N_1$ themselves, you need a specific value of $C$.

Answer 2

The Lagrangian is

$\mathcal L=\frac{V_0}{N_0}+\frac{V_1}{N_1}+\lambda (C-N_0\cdot C_0-N_1\cdot C_1)$

C is the cost budget or something similar. Taking the derivatives:

$\frac{\partial \mathcal L}{\partial N_0 }=-\frac{V_0}{N_0 ^2}-C_0\cdot \lambda=0$

$\Rightarrow -\frac{V_0}{N_0 ^2}=C_0\cdot \lambda \quad (1)$

$\frac{\partial \mathcal L}{\partial N_1 }=-\frac{V_1}{N_1 ^2}-C_1\cdot \lambda=0$

$\Rightarrow -\frac{V_1}{N_1 ^2}=C_1\cdot \lambda \quad (2)$

Dividing (1) by (2):

$\frac{V_0}{V_1}\cdot \frac{N_1^2}{N_0^2}=\frac{C_0}{C_1}$

$ \frac{N_1^2}{N_0^2}=\frac{C_0}{C_1}\cdot \frac{V_1}{V_0} \quad | \sqrt{\ \ } $

$ \frac{N_1}{N_0}=\sqrt{\frac{C_0}{C_1}\cdot \frac{V_1}{V_0} }$

This is equal to your solution.