Take the 2-minute tour ×
Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. It's 100% free, no registration required.

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?

share|improve this question
add comment

2 Answers 2

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.

share|improve this answer
add comment

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

share|improve this answer
    
This is not correct; see @GeoffOxberry's answer. –  Christian Clason Jun 21 '13 at 14:30
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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