Binary quadratic optimization

Optimization of a quadratic form over binary choices, here using signs $x_i\in \{-1,1\}$. Lifting $x{x}^T$ turns the objective into a matrix trace; dropping the rank-one condition gives a semidefinite relaxation of binary quadratic optimization.

For a real rectangular matrix $S$, maximize $p^{T}Sq$ over separate sign choices for $p$ and $q$. With $x=(p,q)$, the symmetric block matrix $A=\frac{1}{2}\left(\begin{array}{cc}0& S\\ S^T& 0\end{array}\right)$ satisfies $x^{T}Ax=p^{T}Sq$. Its zero diagonal blocks allow the Krivine rounding scheme to linearize the cross-block expected objective.