# Feasibility checking

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?

• I should also note that due to the similarity of this question to scicomp.stackexchange.com/q/5258/276, this question nearly duplicates that one because it involves similar reasoning, and because feasibility problems are so closely related to optimization problems. – Geoff Oxberry Feb 14 '13 at 11:49

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.
• Any idea about the $\mathcal{NP}$-hardness? – Star Feb 15 '13 at 13:23
• I'm not sure what you're getting at here. Nonconvex optimization problems are $\mathcal{NP}$-hard problems; you can't address this obstacle unless you decide to adopt a convex formulation, or prove that $\mathcal{P} = \mathcal{NP}$ and go from there. Since the $\mathcal{P} = \mathcal{NP}$ problem has been open for at least four decades and resisted any attempts at solution, changing your formulation is the only practical option I can see with the information you've supplied. – Geoff Oxberry Feb 17 '13 at 5:37