# 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:

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

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$

• Thank you very much for the reply! I was not aware of bilinear programs! Seems like a quadratic function is also a bilinear function. Could you clarify how can I incorporate the interval halving in this program since the value y can take does not have an upper bound apriori. – karmanaut Sep 17 '17 at 19:02
• Bilinear is simply a special case of quadratic. To find an initial upper bound, simply solve a linear problem without the first constraint where you maximize $z$. If $xc_1 \leq c_2$, the solution to the original problem is $y=0$. If the problem is unbounded, then the problem is ill-posed as $y = 0_{+}$ is optimal. Otherwise, an initial upper bound can be computed from $(x c_1-c_2)/z$. – Johan Löfberg Sep 17 '17 at 19:08
• Before I accept your answer, I am still at loss on how do I actually incorporate the range of y in the program. Adding a constraint of $y \leq c_3$ does not make the program linear. Could you give a small example of the program which is LP when y is bounded? I looked for cutting plane method but could not convince myself how does it make the program linear. – karmanaut Sep 17 '17 at 19:55
• You perform a bisection so you solve LP with $y$ fixed to 50. If that leads to infeasibility, you know that 50 is a new lower bound instead of $0$. If it leads to feasibility, you know 50 is a new upper bound instead of 100. Rinse and repeat. – Johan Löfberg Sep 17 '17 at 20:38
• Yes, but $z$ is unbounded in the linear program where you skip the first constraint, which I proposed as the first way to get an initial bound. Better to solve a problem where you get a bounded $z$ by consttruction – Johan Löfberg Sep 17 '17 at 20:54