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?

asked 17 Sep '17, 12:02

karmanaut's gravatar image

accept rate: 0%

edited 17 Sep '17, 15:30

Paul%20Rubin's gravatar image

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.

(20 Sep '17, 05:27) Erling_MOSEK
Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here



Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text]( "Title")
  • 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



Asked: 17 Sep '17, 12:02

Seen: 445 times

Last updated: 20 Sep '17, 05:27

OR-Exchange! Your site for questions, answers, and announcements about operations research.