2
$\begingroup$

$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?

$\endgroup$
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – Brout May 2 '18 at 2:01
  • $\begingroup$ Same counterexample. $\endgroup$ – Robert Israel May 2 '18 at 16:31
  • $\begingroup$ Actually I found that one out already. $\endgroup$ – Brout May 2 '18 at 16:32

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

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