Solving linear program with 1 quadratic constraint complexity

 0 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 17 Sep '17, 12:02 karmanaut 11●2 accept rate: 0% Paul Rubin ♦♦ 14.6k●4●12 1 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. (20 Sep '17, 05:27) Erling_MOSEK
Be the first one to answer this question!
 toggle preview community wiki

By Email:

Markdown Basics

• *italic* or _italic_
• **bold** or __bold__
• image?![alt text](/path/img.jpg "Title")
• numbered list: 1. Foo 2. Bar
• to add a line break simply add two spaces to where you would like the new line to be.
• basic HTML tags are also supported

Tags: