= Solution
Split the sign <vector> as $x=(p^T,q^T)^T$. Multiplication of the two off-diagonal blocks gives
$$
x^TAx=\frac12(p^TSq+q^TS^Tp)=p^TSq,
$$
because the two terms are the same real <scalar>. The map $(p,q)\mapsto x$ is a bijection between the feasible sign choices. Therefore
$$
\boxed{\max_{p,q}p^TSq=\max_x x^TAx}.
$$
This is the symmetric lifting of <bipartite binary quadratic optimization> to <binary quadratic optimization>. The factor $1/2$ is necessary: otherwise the two blocks would double the objective. No <positive semidefiniteness> of $A$ is assumed; generally its off-diagonal structure makes its <quadratic form> indefinite.
Back to article page
