MathOverflow is a question and answer site for professional mathematicians. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top


This is the full version of a question I asked earlier. I am trying to understand whether finding a solution to the following bilinear system is computationally hard or easy:

$\lambda_i^T u_{ij} = 0$ for all $i,j$

$\sum_{i=1}^n u_{ij} = u_j$ for all $j$

$\sum_{j=1}^m (e p_j^T - e^T p_j I)u_{ij} \geq 0$ for all $i$

$\lambda_i \geq 0$ for all $i$

$e^T \lambda_i = 1$ for all $i$

The variables are $\lambda_i$ and $u_{ij}$, the constants are $p_j$ and $u_j$, and $e$ is the vector of all ones. If the dimension of the $\lambda_i,u_{ij}$ is $k$, then the numbers of variables $m,n$ are related by $m=(n-1)^k$.

Is solving this underdetermined bilinear system NP-hard or can one find a solution? Bilinear systems are NP-hard in general, but all proofs I have seen involve manipulating the matrix $A$ in $x^TAy$. I don't understand how extra linear constraints affect the complexity of the bilinear equations.

Thank you in advance!

share|cite|improve this question
Not sure what you mean about "extra linear constraints". You mean the inequality constraints? Also, just a comment: a system being NP-hard does not preclude one from finding a solution. Those statements are not mutually exclusive. A worst-case complexity bound is just that: a bound. The simplex method is NP-hard, but its average performance is extremely good. – Gilead Dec 24 '11 at 16:28
It looks like this could be reformulated into a (mixed) linear complementarity problem (if $u_{ij}$ can be made to be non-negative). There may exist complexity proofs in the LCP literature. – Gilead Dec 24 '11 at 16:33
Thanks Gilead. Unfortunately I can't just assume that $u_{ij} \geq 0$. There is a way to reformulate this problem so that $u_{ij} \geq 0$, but then the bilinear constraints would become $u_{ij}^T \lambda_i = \alpha_{ij}$ for some $\alpha_{ij} \geq 0$, and this would no longer be a complementarity problem. I'm not sure if that formulation would be easier. Alos, I understand NPC != unsolvable, but I am trying to understand the complexity of the problem these equations encode. So I am looking either for a polytime algorithm or an NPC proof. – Woland Dec 27 '11 at 5:30
Oh, and by extra linear constraints I mean additional constraints of the form $c_i(x) \geq 0$, $d_i(y) \geq 0$, $e_i(x) = 0$, $f_i(y) = 0$, where $c,d,e,f$ are linear. These are in addition to the bilinear constraints $y^T x = 0$. – Woland Dec 27 '11 at 5:34

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.