1
$\begingroup$

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?

|cite|improve this question
$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Geoff Oxberry Feb 14 '13 at 11:49
4
$\begingroup$

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.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ Any idea about the $\mathcal{NP}$-hardness? $\endgroup$ – Star Feb 15 '13 at 13:23
  • $\begingroup$ 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. $\endgroup$ – Geoff Oxberry Feb 17 '13 at 5:37
  • $\begingroup$ It's certainly not true that all nonconvex optimization problems are NP-hard. You'd have to do some work to show that this particular problem is NP-Hard. $\endgroup$ – Brian Borchers Jan 28 '14 at 16:53
  • $\begingroup$ You're right. It's not true that all nonconvex optimization problems are NP-hard. Having worked in a lab that specialized in solving nonconvex optimization problems, most nonconvex problems are treated that way in practice until proven otherwise. I don't know of many practitioners who would go through and check every single formulation they came across for NP-hardness. More common seems to be checking problem classes (QP with one negative eigenvalue, for instance). $\endgroup$ – Geoff Oxberry Jan 28 '14 at 18:27

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.