Polynomial solvability [duplicate]

Question

This question is an exact duplicate of:

• Convexity of a function [migrated] 1 answer

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?

Answer 1

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.