Binary quadratic optimization Created 2026-10-06 Updated 2026-10-14
Optimization of a quadratic form over binary choices, here using signs . Lifting 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 is the sign optimum and its semidefinite relaxation of binary quadratic optimization value, then . 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 , 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 . It is a positive semidefinite matrix, since , and . The matrix trace identity gives
Thus all original feasible objectives appear among the relaxed ones, proving
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 , and closed. Its two-by-two principal minors give , so it is bounded and therefore compact. The linear objective attains its maximum. Also and hence , including the zero-objective case.
Randomized rounding Created 2026-10-06 Updated 2026-11-05
Randomized rounding converts a solution of a continuous relaxation of a integer programming problem into a random discrete candidate. For fractional binary variables , independent Bernoulli random variables with preserve a linear objective in expectation: . They do not automatically preserve every constraint.
For example, satisfies , but independent rounding chooses both items with probability . A feasibility argument, rejection, repair, or a dependent rounding construction is therefore needed before this becomes an approximation algorithm. The objective bound and the feasibility guarantee are separate parts of its proof.
Gaussian hyperplane rounding uses a shared random hyperplane to produce a feasible sign vector for a semidefinite relaxation of binary quadratic optimization. Rademacher rounding for a semidefinite relaxation instead uses random signs in its construction. In both cases the distribution is chosen so that an expected objective bound can be related to the relaxation value.