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} u_{ij} = u_j$ for all $j$

$\sum_j (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.

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!