Solving linear program with 1 quadratic constraint complexity Consider the following linear program,
$$\min y \\
xc_1 \leq c_2 + yz,\\
x = x_1 + \dots + x_n,\\
z \leq x_1 + x_2, \\
z \leq x_2 + x_3, \\
\vdots\\
z \leq x_{n-1} + x_n, \\
x,x_1, \dots, x_n,y,z \geq 0
$$ 
where $c_1, c_2$ are constants. This is an example of quadratically constrained linear program where I have 1 quadratic constraint. I wish to find out if this problem is NP-Hard or not. The quadratic constraint can be expressed in the form $\vec{y}M\vec{y}^T$ where $M$ for my problem is not positive semidefinite (and thus, non-convex).
Listing the questions:


*

*Can this problem be transformed into a linear program by taking logs?

*Is there any literature reference or reduction showing that linear programs with non-convex quadratic constraints is an NP-Hard problem? 

 A: Consider the following linear program - and then you write down a bilinear program.
Good news though is that you easily can solve this by bisection in $y$, meaning that 
complexity is complexity of solving a linear program, times a constant which is logarithmic in the desired precision (as you half the interval for every linear program you solve)
EDIT: Good or bad news is that the problem can be solved analytically, the optimal value approaches $0$ but that is done by letting half of the $x_i$ tend to infinity. Let $x_i$ be $\mu$ for even $i$ and $0$ for odd $i$. The constraints involving $z$ then all simplify to $z\leq \mu$. The constraints will be active at optimality (otherwise $z$ can be made larger and thus $y$ smaller), hence $z = \mu$. The first constraint simplifies to $(c_1\mu \lfloor n/2 \rfloor -c_2)/\mu\leq y$, or equivalently we are minimizing $c_1 \lfloor n/2 \rfloor -c_2/\mu$. We have $\mu \geq 0$ and for the problem to make sense $c_2\leq 0$ (otherwise the problem is trivial as one could take the zero solution.) 
Hence, the infimum is  $c_1 \lfloor n/2 \rfloor$ which is approached when $\mu \rightarrow 0$
