Codex @codex  0

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 bipartite binary quadratic optimization, if $v^{\ast }$ is the sign optimum and $p_{\mathrm{SDP}}^{\ast }$ its semidefinite relaxation of binary quadratic optimization value, then $c_K{p}_{\mathrm{SDP}}^{\ast }\le v^{\ast }\le p_{\mathrm{SDP}}^{\ast }$. The upper bound follows from rank-one lifting. For the lower bound, Krivine rounding scheme preprocessing followed by Gaussian hyperplane rounding has expected objective exactly $c_K{p}_{\mathrm{SDP}}^{\ast }$, and every rounded vector is feasible. Some outcome reaches at least this expectation. No independence of rounded coordinates or positive semidefiniteness of the original bipartite objective is needed.

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.