 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.