0
$\begingroup$

As part of our project, we are required to determine the total number of distinct solutions to the following equations.

There are $n$ variables of one type, say $\{p_i\}_{i=1}^n$, $m$ variables of other type, say $\{q_j\}_{j=1}^m$. Cost between units $p_i$ and $q_j$ is given by $w_{ij}$. Each $p_i, q_j \in (0,1)$.

Problem is, given a set of $\{w_{ij}\}$, how many distinct solutions $\{\mathbb{p},\mathbb{q}\}$ can satisfy the following equations simultaneously $$\log \frac{p_i}{1-p_i} = \sum_j w_{ij}q_j - \left(p_i - \frac{1}{2}\right)\sum_jw_{ij}^2\left(q_j - q_j^2\right) \text{, for $1 \le i \le n$}$$ $$\log \frac{q_j}{1-q_j} = \sum_i w_{ij}p_i - \left(q_j - \frac{1}{2}\right)\sum_iw_{ij}^2\left(p_i - p_i^2\right) \text{, for $1 \le j \le m$}$$

ATTEMPT I

I tried to fix the $\{q_j\}_{j=1}^m$ and $\{w_{ij}\}$ so that the 1st equation took the form of $$\log \frac{p_i}{1-p_i} = -a_ip_i + b_i$$ The important thing to note here is that $a_i > 0$ irrespective of the values of $\{q_j\}$ and $\{w_{ij}\}$. Now if we plot the graph of $y = \log \frac{x}{1-x}$, then we can see that a line with negative slope $y = -a_ix + b_i$ shall cut this graph exactly once. Thus given vector q, the vector p gets uniquely determined and vice-versa.

Unfortunately I could not get a closed-form analytical solution for the above so didn't know how to proceed firther.

ATTEMPT 2

In the first equation I tried to treat a single unit $q_j$ as the variable resulting in a quadratic equation. I could get to the point that despite being quadratic, if we restrict $|w_{ij}| < 2$ (not a bad assumption) then there is at most one solution to this quadratic equation.

However, again I am stuck about how to proceed further.

ATTEMPT 3

This is a bold (and desperate) attempt of actually fixing the p and q vectors and instead treating $\{w_{ij}\}$ as the variables. Then the problem reduces to the following.

What is the maximum number of distinct pairs of vectors {p,q} possible such that the $\{w_{ij}\}$ satisfy each set of equations. If the quadratic term was not there then this would be actually a system of linear equations and assuming linear independence we could have got a bound on this number using rank techniques.

Can we extend this approach to quadratic case?

Any help, pointers shall be much appreciated. An approximation or bound shall also be sufficient.

Thanks

$\endgroup$
  • $\begingroup$ Have you tried to get smth useful from symmetry w.r.t. to p and q? Like introducing symmetric variables, adding equations etc $\endgroup$ – VorKir Feb 4 '17 at 20:57
  • $\begingroup$ @VorKir I am not able to see how I can use the symmetry. $\endgroup$ – user104452 Feb 5 '17 at 13:18

Your Answer

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

Browse other questions tagged or ask your own question.