3
$\begingroup$

I am having the following function of 2 variables which I would like to minimize.

$$ f(x,y)={\left(n_{1}\right)\left(1- x\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}}\right)^{T}} + {\left(n_{2}\right)\left(1- y\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}}\right)^{T}}$$

Note that $x \in [0,1]$ and $y \in [0,1]$. In fact, $x$ and $y$ are probability values.

T is a positive integer. (T actually denotes number of tests in my actual problem.) $n_1$ and $n_2$ are also positive integers but much larger than T. ( $n_1$ and $n_2$ represents number of members in 2 classes in my actual problem setup).

$k_1$ and $k_2$ represents number of defective members in the two classes containing $n_1$ and $n_2$ members each. Thus, $T$ can be viewed as the number of tests made to identify the defective members.

The only way I can think of is take the partial derivatives w.r.t $x$ and $y$ and equate them to zero and solve simultaneously.

I tried this, but I don't see any ways of solving the resulting 2 equations as they are not analytically simple atleast for me.

I also notice that, there is some sort of symmetry in $f(x,y)$ with respect to $x$ and $y$. My hunch is that this could be made use of to find a minimum.

Can someone suggest a possible way of solving it?

One more question:

Is there any computer software package or online tools that I can use to minimize this function while keeping the generic letter constants as such?

$\endgroup$
6
  • 1
    $\begingroup$ Do not dream too much. This is a real monster. Cheers :-) $\endgroup$ Dec 13, 2019 at 8:54
  • $\begingroup$ Jyotish, Let $g(x,y)=1-x(1-x)^{k_1}(1-y)^{k_2}$ and $h(x,y)=1-y(1-x)^{k_1}(1-y)^{k_2}$. If g(x, y) and h(x, y) are minimum then f(x, y) is minimum. I took derivative and equate it to zero. I found that the minimum of g(x,y) and h(x, y) is zero. So minimum of f(x, y) is $n_1+n_2$. $\endgroup$
    – sirous
    Dec 13, 2019 at 14:11
  • $\begingroup$ @sirous , so did you minimize g(x,y) and h(x,y) separately? I think the 2 functions are not minimized for the same (x,y) values. Thus, the sum is not minimized at this point. do you agree? $\endgroup$
    – wanderer
    Dec 13, 2019 at 15:03
  • $\begingroup$ @ClaudeLeibovici , I tried to empirically find the point of minimum. I found that the solution is very close to $x =y= \frac{1}{k1+k2+1}$. Note that n1, n2, k1, k2 and T are positive integers and n1>> k1 and n2>>k2. Do you think atleast it is possible to prove this claim? $\endgroup$
    – wanderer
    Dec 13, 2019 at 16:00
  • 2
    $\begingroup$ Do you have any constraints on the parameters? The behaviour of $f$ depends very strongly on the signs of the parameters. Are $x$, $y$, and the parameters integers? rational? real? complex? Your proposal of taking derivatives suggests $x$ and $y$ are real or complex, but doesn't provide insight into the domain of the parameters. $\endgroup$ Jan 1, 2020 at 22:22

1 Answer 1

3
+50
$\begingroup$

$f(x,y)=\left(n_{1}\right)\left(1-x\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}}\right)^{T}+\left(n_{2}\right)\left(1-y\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}}\right)^{T}$

define $\alpha=\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}}$

$f(x,y)=\left(n_{1}\right)\left(1-x\alpha(x,y)\right)^{T}+\left(n_{2}\right)\left(1-y\alpha(x,y)\right)^{T}$

minimize with a Lagrange multiplier:

$\left(n_{1}\right)\left(1-x\alpha\right)^{T}+\left(n_{2}\right)\left(1-y\alpha\right)^{T}+\lambda(\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}}-\alpha)$

$\partial_{x}:-\left(T\alpha n_{1}\right)\left(1-x\alpha\right)^{T-1}-\lambda k_{1}(\left(1-x\right)^{k_{1}-1}\left(1-y\right)^{k_{2}})=0$

$\partial_{y}:-\left(T\alpha n_{2}\right)\left(1-y\alpha\right)^{T-1}-\lambda k_{2}(\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}-1})=0$

$\partial_{\alpha}:-\left(xTn_{1}\right)\left(1-x\alpha\right)^{T-1}-\left(yTn_{2}\right)\left(1-y\alpha\right)^{T-1}-\lambda=0$

multiplying the first two equations by $\frac{x}{\alpha};\frac{y}{\alpha}$ respectively:

$-\left(Txn_{1}\right)\left(1-x\alpha\right)^{T-1}-\lambda xk_{1}(\left(1-x\right)^{k_{1}-1}\left(1-y\right)^{k_{2}})/\alpha=0$

$-\left(Tyn_{2}\right)\left(1-y\alpha\right)^{T-1}-\lambda yk_{2}(\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}-1})/\alpha=0$

subtracting from the $\partial_{\alpha}$ term:

$-xk_{1}(\left(1-x\right)^{k_{1}-1}\left(1-y\right)^{k_{2}})/\alpha-yk_{2}(\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}-1})/\alpha+1=0$

using the constraint $\alpha=\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}}$ ( we are allowed to use it now that we have finished differentiating):

$-xk_{1}(\frac{\alpha}{1-x})/\alpha-yk_{2}(\frac{\alpha}{1-y})/\alpha+1=0$

yielding:

$k_{1}(\frac{x}{1-x})+k_{2}(\frac{y}{1-y})=1$

We can now eliminate $y$ and solve for a one dimensional minimum.

$\endgroup$
2
  • $\begingroup$ Thanks for the answer. I am going through it. I am aware of lagrange multipliers when there are equality constraints. Here you are defining $\alpha$ to explicitly bring in an equality constraint and then using Lagrange multipliers with that constraint. Is this a well-known trick? $\endgroup$
    – wanderer
    Jan 2, 2020 at 15:46
  • $\begingroup$ It just seemed to me a clean way to identify the common $\left(1-x\right)^{k_{1}}\left(1-y\right)^{k_{2}}$ term. I was surprised myself when I saw that I could eliminate one term regardless of the value of the multiplier. Maybe there is a direct way to do this, but I haven't looked. $\endgroup$
    – user619894
    Jan 5, 2020 at 5:41

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.