Boolean Quadratic Programming

Motivation: maximum cut (MAXCUT) problem
Boolean quadratic programming
Rank-constrained formulation
SDP relaxation
Sub-optimal solution via the SDP relaxation

Motivation: MAXCUT Problem

We consider an undirected graph with

nodes, described by its weight matrix $W in mathbf{S}^ n$ , with $W_{ij} = W_{ji} ge 0$ the weight of the arc joining node

and

(with the convention that the weight is zero if there these nodes have no edge connecting them). The maximum cut problem is to find a partition of the nodes in two complementary groups, so that the total weight of the edges that connect the two groups is maximized.

The max-cut problem can be formalized via the following boolean quadratic problem:

Here, the boolean variable $x in {-1,1}^n$ corresponds to a particular assignement of each node into one of the two groups. The constraints in the above problem enforce the Boolean conditions on

. We check that the term $W_{ij}(1-x_ix_j)$ is zero if and only if x_i

and

are equal, which means that node

and node

are in the same group; otherwise, the cost is $2W_{ij}$ .

Boolean QP

The above problem falls into the more general class of Boolean quadratic programs, which are of the form

where $W in mathbf{S}^n$ , with $W_{ij}$ of arbitrary sign. Boolean QPs, as well as the special case of max-cut problems, are combinatorial, and hard to solve exactly. However, theory (based on SDP relaxations seen below) says that we can approximate the above quantity with a relative error of at most pi/2-1

(the number falls to 0.87

in the case of MAX-CUT, which has special structure).

Rank-Constrained Formulation

We will introduce a semidefinite approximation to the problem, which is based on an expression of the original Boolean QP in terms of a matrix variable $X in mathbf{S}^n$ , with components $X_{ij} = x_ix_j$ , 1 le i,j le n

. We can write the relationship between the vector

and the matrix

more compactly, as

We note that the objective of the Boolean QP, while quadratic in the original decision vector

, is actually linear in the matrix

, since

Finally, we note that a given symmetric matrix

has the form X = xx^T

for some vector $x in mathbf{R}^n$ if and only if it is positive semi-definite and its rank is one.

This means that we can formulate the Boolean QP in an equivalent, ’'rank-constrained’’ form:

$phi = max_X : mbox{bf Tr} (W X ) ~:~ X succeq 0, ;; mbox{bf rank}(X) = 1, ;; X_{ii} = 1, ;; i=1,ldots,n.$

Semidefinite Relaxation

The above rank-constrained problem is not convex, precisely due to the rank constraint. If we remove the constraint, we do obtain a convex problem — in fact, an SDP. This SDP is a relaxation of the original problem, that is, it is a new problem obtained by removing constraints. Since we are maximizing, the new problem yields an upper bound on the original one:

$phi le psi := max_X : mbox{bf Tr} (W X ) ~:~ X succeq 0, ;; X_{ii} = 1, ;; i=1,ldots,n.$

The gap between phi

(the true value of the combinatorial problem) and psi

(the SDP approximation) can be large, but not arbitrarily so. In fact, as mentioned above, it has been shown (by Nesterov in 1996) that the relative error satisfies