# 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) which is perhaps evidence of hardness

Listing specific questions below:

1. Can this problem be transformed into a linear program by taking logarithms?
2. Is there any literature reference or reduction showing that linear programs with non-convex quadratic constraints is an NP-Hard problem?

Edit : Cross posted question at math.stackexchange

Based on posts from or-exchange and some internet reading, the following algorithm works. We adapt the cutting plane method to binary search for variable $y$. For my problem, the upper and lower bounds for all variables are known (but if these are not known, one can find a bound on $y$ by solving the LP by removing the first constraint). Let $l \leq y \leq u$.
Fix $y = (l+u)/2$. This converts the program to a linear program. If the resulting constraints are feasible, update $u(l) = (l+u)/2$. Keep performing the binary search until we reach the optimal solution with an additive $\epsilon_0$. The running time of the algorithm is $O(PTIME)\log\frac{u-l}{\epsilon_0}$.
• As I said in the answer on math.stackechange, you can solve it analytically (empirically you will see that every second $x_i$ will be zero and all other elements equal to the same value, call it $\mu$, hence $z$ will be equal to $\mu$ at optimality, plug into first constraint and minimize left-hand side analytically). All you have to do is to prove that this solution actually is the optimal choice – Johan Löfberg Sep 18 '17 at 16:39
• but unfortunately, you will see that the problem does not have any minimizer, as the optimal cost tends to $c_1\lfloor n/2 \rfloor$ for $\mu \rightarrow \infty$ – Johan Löfberg Sep 18 '17 at 16:55