3
$\begingroup$

I'm reading an article lately, and there is one point which confuses me. So, we have the following constrained binary quadratic problem.

min $x^{T}Qx$

with the constraints that $Ax≤b$

and $x\in {0,1}^{n}$

This can be relaxed into the following:

min $\sum_{1\leq i <j \leq n}2q_{ij}y_{ij} + \sum_{i=1}^{n}q_{ii}x_i$

with the constraints that

$Ax\leq b$

$y_{ij}\geq x_i+x_j-1 \text{ for any } i,j \text{ with } i<j \text{ and } q_{ij}>0 $

$y_{ij}\leq x_i \text{ for any } i,j \text{ with } i<j \text{ and } q_{ij}<0$

$y_{ij} \leq x_j \text{ for any } i,j \text{ with } i<j \text{ and } q_{ij}<0$

$0\leq x_i \leq 1\text{ for any } i=1,2,...n$

$y\geq 0$

So, the solution of the relaxed optimization problem would serve as a lower bound of the optimal solution for the original optimization problem. Could anyone help me explain the relaxation part? I was thinking to prove

$\sum_{1\leq i <j\leq n}2q_{ij}y_{ij} + \sum_{i=1}^{n}q_{ii}x_i \leq \sum_{j=1}^{n}\sum_{i=1}^{n}x_iq_{ij}x_j$ where $x_i$ is either 0 or 1.

It seems that the term $\sum_{i=1}^{n}q_{ii}x_i$ of the left part would cancel out the term $\sum_{i=1}^{n}x_i^{2}q_{ii}$ of the right part. Then, what shall I do next? Any comments would be greatly appreciated.

$\endgroup$
  • 1
    $\begingroup$ You may find it to be easier to do this by starting with $y_{i,j}$ as a binary variable (it will be equal to $x_{i}x_{j}$ and then relaxing that binary constraint as the last step in your derivation. $\endgroup$ – Brian Borchers Feb 13 '17 at 15:47
  • $\begingroup$ Is Q required to be a symmetric matrix then? $\endgroup$ – Joseph Stone Feb 13 '17 at 20:51
  • $\begingroup$ It's certainly simpler to have $Q$ as a symmetric matrix. You can always write a quadratic form using a symmetric matrix, so there's no reason to not assume symmetry of $Q$. $\endgroup$ – Brian Borchers Feb 13 '17 at 21:13
  • $\begingroup$ I thought the matrix $Q$ as a parameter is given. So, what if $Q$ is not symmetric then? $\endgroup$ – Joseph Stone Feb 13 '17 at 21:27
  • $\begingroup$ You can simply take $Q=(Q+Q^{T})/2$ and get exactly the same result. $\endgroup$ – Brian Borchers Feb 13 '17 at 21:34

Your Answer

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

Browse other questions tagged or ask your own question.