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$}$$


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.


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.


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.


  • $\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.