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?
asked
karmanaut Paul Rubin ♦♦ |

If you had (c_1*x-c_2)^2 <= yz then it would be a conic quadratic optimization problem (aka. SOCP) and it would be polynomial solvable.