1
$\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).

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?
$\endgroup$
2
$\begingroup$

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$

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – karmanaut Sep 17 '17 at 19:02
  • 1
    $\begingroup$ 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$. $\endgroup$ – Johan Löfberg Sep 17 '17 at 19:08
  • $\begingroup$ 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. $\endgroup$ – karmanaut Sep 17 '17 at 19:55
  • 1
    $\begingroup$ 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. $\endgroup$ – Johan Löfberg Sep 17 '17 at 20:38
  • 1
    $\begingroup$ 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 $\endgroup$ – Johan Löfberg Sep 17 '17 at 20:54

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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