¿Programa lineal con una condición cuadrática convexa en el dominio de interés resoluble en tiempo polinómico?

Question

$c\leq xy$ no es una condición convexa.

Sin embargo, sabemos que $c\leq xy$ es convexo en el dominio $x,y>0$ en $\mathbb R^2$ para cualquier $c\in\mathbb R$ .

Es $c\leq x_1y_1+\dots+x_ny_n$ con $0\leq x_1,\dots,x_n\leq 1$ y $0\leq y_1,\dots,y_n\leq n-1$ una condición convexa en $\mathbb R^{2n}$ para cualquier $c\in\mathbb R$ ?

Esencialmente tengo una restricción de la forma $$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$$ y las restantes restricciones de la forma $$AX\leq b$$ donde $A\in\mathbb R^{m\times 2n}$ , $X=\begin{bmatrix}x_1,\dots,x_n,y_1,\dots,y_n\end{bmatrix}'$ y $b\in\mathbb R^m$ donde $m=n^\alpha$ en algún punto fijo $\alpha>0$ .

¿Es este programa cuadrático con una única restricción cuadrática y un número polinomial de restricciones lineales resoluble en tiempo polinomial con algún algoritmo conocido?

Answer 1

Incluso para $n=2$ la restricción no es convexa. Obsérvese que en $(x_1,x_2,y_1,y_2) = (0,1,0,1)$ y $(x_1,x_2,y_1,y_2) = (1,0,1,0)$ tenemos $x_1 y_1 + x_2 y_2 =1$ , pero en su punto medio $(1/2,1/2,1/2,1/2)$ sólo tenemos $x_1 y_1 + x_2 y_2 = 1/2$ .