polynomial time solvability

Consider the following optimization problem:

$Min \qquad C^TX$

S.t.: $\qquad AX=0;$

$x_ix_j=x_kx_t$$\quad$for some $i\neq j\neq k\neq t$

$X=(x_1,x_2,...x_n)$ and $\quad x_j\geq 0\;\; j=1,2,...,n$

Here $C=(c_1,c_2,...,c_n), c_i\geq 0$ and $A$ is the adjacency matrix.

-Is this problem convex? -Can it be solved in polynomial time?

Nonlinear equality constraints involving continuous variables are not convex.

Here is a counterexample for your problem:

Suppose without loss of generality $x_{1}x_{2} - x_{3}x_{4} = 0$ is your nonlinear equality constraint, and let $S = \{(x_1, x_2, x_3, x_4, \ldots, x_{n}): x_1 x_2 - x_3 x_4 = 0\}$ be its associated feasible set.

Then $(6, 1, 3, 2, 0, \ldots, 0) \in S$, and $(1, 6, 3, 2, 0, \ldots, 0) \in S$, but $((6, 1, 3, 2, 0, \ldots, 0) + (1, 6, 3, 2, 0, \ldots, 0)) / 2 = (7/2, 7/2, 3, 2, 0, \ldots, 0) \not\in S$, because $(7/2)^2 - 6 = 49/4 - 6 = 25/4 \neq 0$.

Generally speaking, nonconvex problems cannot be solved in polynomial time.

This problem is converted to LP. Therefore it can be solved in polynomial time.

• This is not correct; see @GeoffOxberry's answer. Jun 21 '13 at 14:30