|
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. |
|||
|
|
