3
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
-4
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This is not correct; see @GeoffOxberry's answer. $\endgroup$ – Christian Clason Jun 21 '13 at 14:30

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.