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?


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.

  • $\begingroup$ Why did you write $\operatorname{trace}(A^TAX - 2b^TAx + b^Tb)$ instead of $\operatorname{trace}(A^TAX) - 2b^TAx + b^Tb$ which is what the original objective function is. Am I missing something? $\endgroup$ – Eagle1992 Apr 16 '14 at 8:47
  • $\begingroup$ @Eagle1992 It's a typo. $\endgroup$ – user1551 Apr 16 '14 at 10:14
  • $\begingroup$ ah I caught it before you replied. Thank you for your answer. Very elegant and simple to understand. $\endgroup$ – Eagle1992 Apr 16 '14 at 10:45

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.