Suppose that we have an objective function that involves two binary variables, i.e. $x, y \in \lbrace 0,1 \rbrace$ ($x$ represents the assignment of category A to category B and $y$ represents the assignment of Category A to category C that is different from category B) that are multiplied by each other.

Can such problems be relaxed using semidefinite programming? I know that if $x$ is multiplied by itself like in $x^T Qx$ can be relaxed but if we have a different variable like $y$: is it still possible to be relaxed?

  • $\begingroup$ Do you mean you want to minimize $xy$ where both are binary ? $\endgroup$ – Ahmad Bazzi Mar 1 at 17:16
  • $\begingroup$ What is the objective function? $\endgroup$ – Rodrigo de Azevedo Mar 1 at 17:48
  • 1
    $\begingroup$ You'll need to tell us more about your problem. $\endgroup$ – Brian Borchers Mar 1 at 17:51

It is not clear if you are asking about the semidefinite relaxation of binary condition in general, or semidefinite relaxation of bilinear products of binary variables.

Bilinear products you have already in the expression $x^TQx$ which you refer to so obviously yes.

Binary constraint simply means you have the quadratic constraint $x_i(1-x_i) = 0$, which you thus incorporate in your semidefinite relaxation as any other polynomial constraint.

  • $\begingroup$ you mean $x^TQy$, right ? $\endgroup$ – Ahmad Bazzi Mar 1 at 17:22
  • $\begingroup$ No. $x$ is a vector, leading to bilinear and quadratic products $x_ix_j$ when you work with quadratic expressions. The question is confusing as it first appear to reference to $x$ and $y$ as scalars, but then $x$ is a vector when talking about $x^TQx$. $\endgroup$ – Johan Löfberg Mar 1 at 17:24
  • $\begingroup$ I agree that it is confusing. But also quantities of the form $x^T Q y$ are referred to as bilinear, right ? .. look here en.wikipedia.org/wiki/Bilinear_form $\endgroup$ – Ahmad Bazzi Mar 1 at 17:27
  • 1
    $\begingroup$ Yes but it adds no value here. From the question it appears the poster is familiar with relaxation of general quadratic expressions, and then it should be clear that bilinear expressions automatically are supported as that simply means the matrix $Q$ has some zeros. $\endgroup$ – Johan Löfberg Mar 1 at 17:30
  • $\begingroup$ ah yes you're right $+1$ :) $\endgroup$ – Ahmad Bazzi Mar 1 at 17:32

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.