Bivalent quadratic optimization with sum-of-square of quadratic penalties

The problem of maximizing the sum-of-square of quadratic functions with bivalent variables, denoted by (P), arises from bivalent quadratic optimization with K quadratic disjunctive penalties. Though NP-hard in general, (P) is polynomially solvable when the input matrices can concatenate to a fixed-rank matrix. We present a nonconvex quadratic semidefinite programming (SDP) relaxation, which provides a 0.4-approximate solution for (P). We show that the quadratic SDP relaxation can be approximately and globally solved to a precision via solving at most linear SDP subproblems.