Feasibility checking

Question

Consider the following optimization problem:

$Min\;\;\; CX$

$AX\geq b$

$x_ix_j= x_s x_t\;\;\; i\neq j \neq s\neq t$

$x_j\geq 0;$

Where $A$ is the adjacency matrix and $C$ is a constant vector.

How can one check the feasibility of this optimization problem in an efficient way?

Answer 1

You can't. Optimization and feasibility are equivalent problems, because optimization can be achieved by solving a sequence of feasibility problems.Consequently, both are in the same computational complexity class. In an answer to a similar question you posed I showed that your formulation is nonconvex. Determining feasibility such problems is generally an $\mathcal{NP}$-hard problem.

A deleted answer from that similar question noted that the zero vector is a feasible solution for your problem; if you impose the constraint that the objective must be less than or equal to $-\varepsilon$ for $\varepsilon > 0$, then the feasibility problem is nontrivial.