# Polynomial solvability [duplicate]

This question is an exact duplicate of:

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?

-

## marked as duplicate by Geoff Oxberry♦Feb 15 '13 at 17:52

"$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

In general, no.

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

\begin{align} F(2, 2, 0, 0) \leq \frac{1}{2}F(1, 3, 0, 0) + \frac{1}{2}F(1, 3, 0, 0). \end{align}

However,

\begin{align} 16 \not\leq \frac{1}{2} \cdot 9 + \frac{1}{2} \cdot 9. \end{align}

In general, nonconvex problems are $\mathcal{NP}$-hard.

-
Note the similarity to my answer to scicomp.stackexchange.com/questions/5279/…. –  Geoff Oxberry Feb 15 '13 at 17:48