Consider a system of constraints over non-negative variables $x_{1},...,x_{n}$ of the following form:
$$\sum_{i=1}^n x_{i}=1$$ For every $i\in[n]$, $$L_{i} \le x_{i} \le U_{i}$$ For every $(i,j)\in[n]\times[n]$, $$L_{ij} \le x_{i} \cdot x_{j} \le U_{ij}$$
where $\{L_{i}\}_{i=1}^n$, $\{U_{i}\}_{i=1}^n$, $\{L_{ij}\}_{(i,j)\in[n] \times [n]}$, $\{U_{ij}\}_{(i,j)\in[n] \times [n]}$ are parameters in the range $[0,1]$.
I'm trying to find an algorithm that, given the set of parameters, decides whether or not the feasible region defined by the above system of constraints is empty. The algorithm doesn't actually need to find a feasible solution if one exists, only to determine its existence. While this program seems rather simple, I think it is not convex, so I guess Ellipsoid magic is not going to work.
Is there an algorithm, even super-polynomial, to decide whether the program is feasible?