6
$\begingroup$

I would like to show that Quadratic Programming is NP-hard.

I am currently reading a couple of papers which state that QP is NP-Hard and prove it by transforming SAT to QP, however I am finding the diction quite tough since I am just a beginner in the field. Would anyone happen to know the answer to this question who can maybe explain it to me in simpler terms?

$\endgroup$
4
  • 1
    $\begingroup$ Where should we start? Do you know anything about NP-completeness? Have you seen any examples of NP-completeness proof? $\endgroup$ Nov 12, 2013 at 9:22
  • $\begingroup$ Yes I have a good background on NP-Completeness and how a problem is proven to be NP-complete. My question is more specifically about this particular reduction. I have a feeling that I have not understood QP 100% and I am missing some small thing somewhere. $\endgroup$
    – lvella
    Nov 12, 2013 at 9:30
  • 1
    $\begingroup$ Can you give a reference to what Quadratic Programming is? $\endgroup$
    – Raphael
    Nov 12, 2013 at 16:53
  • 1
    $\begingroup$ Raphael, by Quadratic Programming I was referring to optimising a quadratic function which is subject to several linear constraints. $\endgroup$
    – lvella
    Nov 12, 2013 at 22:04

2 Answers 2

6
$\begingroup$

The reduction of SAT to quadratic programming is pretty simple. The idea is that we can use the quadratic objective to "force" the variables to be Boolean, and so we can implement an integer linear program whose feasibility is equivalent to the SAT instance.

Given a SAT instance on a set of variables $x_1,\ldots,x_n$, we define the following quadratic program: $$ \begin{align*} & \min \sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 \\ \text{s.t.} & \\ & 0 \leq x_i \leq 1 & 1 \leq i \leq n \\ & x_{i_1} + \cdots + x_{i_j} + (1 - x_{k_1}) + \cdots + (1 - x_{k_\ell}) \geq 1 & \forall \text{ cl. } x_{i_1} \lor \cdots \lor x_{i_j} \lor \bar{x}_{k_1} \lor \cdots \lor \bar{x}_{k_l} \end{align*} $$ The linear constraints have a $0,1$ solution if and only if the SAT instance is satisfiable. Since $0 \leq x_i \leq 1$, a solution is $0,1$ if and only if $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 = 0$, and for any other solution $\sum_{i=1}^n x_i - \sum_{i=1}^n x_i^2 > 0$. Therefore the SAT instance is satisfiable if and only if the minimum is $0$ (or at most $0$).

$\endgroup$
3
  • 1
    $\begingroup$ They represent a clause. For example, the clause $x_7 \lor x_{18} \lor \bar{x}_9$ will result in the inequality $x_7 + x_{18} + (1-x_9) \geq 1$. $\endgroup$ Nov 12, 2013 at 21:37
  • $\begingroup$ Will it work to convert $3SAT$ to MAXCUT or INDSET preserving number of solutions (standard text reductions look like they will preserve solution count) and utilize resulting quadratic objective? $\endgroup$
    – Turbo
    May 16, 2018 at 10:49
  • $\begingroup$ This is a linear program with quadratic objective and not a quadratic program. $\endgroup$
    – Turbo
    Feb 10, 2021 at 18:20
0
$\begingroup$

Given $a,b,c\in\mathbb Z$ the quadratic program $$\exists x,y\in\mathbb Z$$ $$ax^2+by-c=0$$ is known to be $\mathsf{NP}$-complete by https://www.sciencedirect.com/science/article/pii/0022000078900442. If you had no non-linear constraints but a non-linear objective it is called a linear program having a non-linear objective (for example a convex objective). $\mathsf{SAT}$ can be converted to $\mathsf{SUBSETSUM}$ which reduces to the quadratic program.

$\endgroup$
2
  • 1
    $\begingroup$ I've always seen optimization of a quadratic objective under linear constraints referred to as quadratic programming. And a Google search for "quadratic programming" confirms that it is at least widely used that way. (I've also never seen optimization of a non-linear objective under linear constraints be referred to as linear programming, but that might just be me) $\endgroup$
    – Tassle
    Feb 10, 2021 at 23:52
  • $\begingroup$ To me programming specified the 'logic' which are the constraints. $\endgroup$
    – Turbo
    Feb 11, 2021 at 6:43

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.