Computational Science Stack Exchange is a question and answer site for scientists using computers to solve scientific problems. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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?

share|improve this question

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

This question was marked as an exact duplicate of an existing question.

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


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

share|improve this answer
Note the similarity to my answer to…. – Geoff Oxberry Feb 15 '13 at 17:48

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