1
$\begingroup$

Hello,

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!

Improve this question
$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – Gilead
    Commented Dec 24, 2011 at 16:28
  • $\begingroup$ 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. $\endgroup$
    – Gilead
    Commented Dec 24, 2011 at 16:33
  • $\begingroup$ 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. $\endgroup$
    – Woland
    Commented Dec 27, 2011 at 5:30
  • $\begingroup$ 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$. $\endgroup$
    – Woland
    Commented Dec 27, 2011 at 5:34

0

Reset to default

You must log in to answer this question.