# Linear program with one quadratic condition convex in domain of interest polynomial time solvable?

$c\leq xy$ is not a convex condition.

However we know $c\leq xy$ is convex in domain $x,y>0$ in $\mathbb R^2$ for any fixed $c\in\mathbb R$.

Is $c\leq x_1y_1+\dots+x_ny_n$ with $0\leq x_1,\dots,x_n\leq 1$and $0\leq y_1,\dots,y_n\leq n-1$ a convex condition in $\mathbb R^{2n}$ for any fixed $c\in\mathbb R$?

Essentialy I have one constraint of form $$c\leq x_1y_1+\dots+x_ny_n$$ $$0\leq x_1,\dots,x_n\leq1$$ $$0\leq y_1,\dots,y_n\leq n-1$$ and remaining constraints of form $$AX\leq b$$ where $A\in\mathbb R^{m\times 2n}$, $X=\begin{bmatrix}x_1,\dots,x_n,y_1,\dots,y_n\end{bmatrix}'$ and $b\in\mathbb R^m$ where $m=n^\alpha$ at some fixed $\alpha>0$.

Is this quadratic program with single quadratic constraint and polynomially many linear constraints solvable in polynomial time with some known algorithm?

Even for $n=2$ the constraint is not convex. Note that at $(x_1,x_2,y_1,y_2) = (0,1,0,1)$ and $(x_1,x_2,y_1,y_2) = (1,0,1,0)$ we have $x_1 y_1 + x_2 y_2 =1$, but at their midpoint $(1/2,1/2,1/2,1/2)$ we have only $x_1 y_1 + x_2 y_2 = 1/2$.
• thank you. this was a silly problem then. Would you know if $x_1y_1+\dots+x_ny_n\leq c$ with $0\leq x_1,\dots,x_n\leq 1$and $0\leq y_1,\dots,y_n\leq 2^n-1$ is not convex as well? We know $xy\leq c$ is convex if $0\leq x\leq 1$ holds. – Brout May 2 '18 at 2:01