Semidefinite relaxation for Boolean least squares I am working on the Boolean least squares problem, which comes up a lot in circuit design. In its raw form, it looks like this
$$\begin{array}{ll} \text{minimize} & \operatorname{tr}(A^TAX) - 2b^TAx + b^Tb\\ \text{subject to} & X = xx^T\\ & X_{ii} = 1\end{array}$$
This is definitely not convex because of the first constraint so when we apply a semidefinite relaxation, we can change the first constraint to this
$$\begin{bmatrix}
  X & x \\
  x^T & 1
 \end{bmatrix}
\succeq 0$$
What exactly is the intuitive reason behind this? How does this new SDP constraint reflect the original constraint?
 A: Using the cyclicity property of matrix trace, we have
\begin{align*}
&\operatorname{trace}(A^TAX) - 2b^TAx + b^Tb\\
=&\operatorname{trace}\left[(x^TA^T-b^T)(Ax - b)\right]\\
=&\operatorname{trace}\left[\pmatrix{x^T&1}\pmatrix{A^T\\ -b^T}\pmatrix{A&-b}\pmatrix{x\\ 1}\right]\\
=&\operatorname{trace}\left[\pmatrix{A^T\\ -b^T}\pmatrix{A&-b}\pmatrix{x\\ 1}\pmatrix{x^T&1}\right]\\
=&\operatorname{trace}\left[
\underbrace{\pmatrix{A^TA&-A^Tb\\ -b^TA&b^Tb}}_B
\underbrace{\pmatrix{X&x\\ x^T&1}}_Y\right].
\end{align*}
So, the problem is equivalent to minimising the trace of $BY$, subject to the constraint that
$$
Y=\pmatrix{x\\ 1}\pmatrix{x^T&1},\text{ with } x_i=\pm1\text{ for } i=1,2,\ldots,n.\tag{1}
$$
The set of all feasible $Y$ is not convex. However, if you relax the constraint $(1)$ to
$$
Y\succeq0,\ Y_{ii}=1\text{ for } i=1,2,\ldots,n\tag{2}
$$
(note that this is a relaxation because $(1)$ implies $(2)$ but not vice versa), then the feasible region becomes convex. So, if you minimise the trace of $BY$ subject to constraint $(2)$, and if it happens that the solution also satisfies constraint $(1)$, then you have solved the original problem.
