# Polynomial solvability [duplicate]

Consider the following optimization problem:

Min$_{x}$ $\qquad \sum_{(i,j,t,s)\in I_r}||x_ix_j-x_tx_s||^2$

S.t.: $\qquad x\in \mathcal{C} ;$

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

Here, $\mathcal{C}$ is a convex set and $I_r$ is a polynomial sized index set.

Can this problem be solved in polynomial time?

• "$I_r$ is a polynomial sized index set." Polynomial-sized in $n$? – Geoff Oxberry Feb 15 '13 at 17:42
• Yes, polynomial-sized in $n$. – Star Feb 15 '13 at 17:46
• This question is virtually the same as scicomp.stackexchange.com/q/5279/276. Please do not post multiple questions that are virtually identical; it is considered poor etiquette. – Geoff Oxberry Feb 15 '13 at 17:50

Without loss of generality, suppose that $I_r = \{(1, 2, 3, 4)\}$, and let $F(x_{1}, x_{2}, x_{3}, x_{4} = \|x_{1}x_{2} - x_{3}x_{4}\|^2$. Consider the points $(1, 3, 0, 0)$ and $(3, 1, 0, 0)$; their midpoint is $(2, 2, 0, 0)$. If $F$ were convex, then it would be true that
In general, nonconvex problems are $\mathcal{NP}$-hard.