How to solve simple bilinear equations under extra linear constraints

2011-12-24T07:25:28Z

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!

How to solve simple bilinear equations under extra linear constraints - MathOverflow

How to solve simple bilinear equations under extra linear constraints