= Solution
Every feasible sign <vector> gives the <rank-one matrix> $X=xx^T$. It is a <positive semidefinite matrix>, since $u^TXu=(u^Tx)^2\geq0$, and $X_{ii}=x_i^2=1$. The <matrix trace> identity gives
$$
\operatorname{tr}(Axx^T)=x^TAx.
$$
Thus all original feasible objectives appear among the relaxed ones, proving
$$
\boxed{p_{\rm SDP}^*\geq v^*}.
$$
The <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\leq X_{ii}X_{jj}=1$, so it is bounded and therefore <compact>. The linear objective attains its maximum. Also $\operatorname{tr}(AI)=0$ and hence $p_{\rm SDP}^*\geq0$, including the zero-objective case.
Back to article page
