Skip to main content
2 of 3
added 29 characters in body
Turbo
  • 13.9k
  • 1
  • 27
  • 76

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,y_1,\dots,y_n$$ 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?

Turbo
  • 13.9k
  • 1
  • 27
  • 76