2
$\begingroup$

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

Improve this question
$\endgroup$
1

1 Answer 1

Reset to default
1
$\begingroup$

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}$.

While this algorithm can find the optimal solution within a small additive constant, I am still not sure about the hardness of the problem for solving exactly. Any comments regarding complexity are welcome!

Improve this answer
$\endgroup$
2
  • 1
    $\begingroup$ 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 $\endgroup$
    – Johan Löfberg
    Commented Sep 18, 2017 at 16:39
  • $\begingroup$ 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$ $\endgroup$
    – Johan Löfberg
    Commented Sep 18, 2017 at 16:55

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.