An explicit equivalent positive semidefinite program for nonlinear 0-1 programs

We consider the general nonlinear optimization problem in 0-1 variables and provide an explicit equivalent positive semidefinite program in 2(n)-1 variables. The optimal values of both problems are identical. From every optimal solution of the former, one easily finds an optimal solution of the latter, and conversely, from every solution of the latter, one may construct an optimal solution of the former. For illustration, the equivalent positive semidefinite program is explicated for quadratic 0-1 programs and MAX-CUT in R-3. For unconstrained 0-1 programs, a special representation in terms of a weighted sum of squares is provided.