Past exam of the mathematics course of the University of Cambridge / 2017 / iii / Paper 339 / 2 / b / Solution

Every feasible sign vector gives the rank-one matrix $X=x{x}^T$. It is a positive semidefinite matrix, since $u^{T}Xu=(u^{T}x{)}^2\ge 0$, and $X_{ii}=x_i^2=1$. The matrix trace identity givesThus all original feasible objectives appear among the relaxed ones, provingThe semidefinite relaxation of binary quadratic optimization drops the rank-one requirement and keeps the elliptope constraints.

An optimal relaxed matrix exists. The feasible set is nonempty, since it contains $I$, and closed. Its two-by-two principal minors give $|X_{ij}{|}^2\le X_{ii}{X}_{jj}=1$, so it is bounded and therefore compact. The linear objective attains its maximum. Also $\mathrm{tr}(AI)=0$ and hence $p_{\mathrm{SDP}}^{\ast }\ge 0$, including the zero-objective case.