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

Jean B. Lasserre (lasserrelaas.fr)

Abstract: 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 find 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 psd program is explicited for quadratic 0-1 programs and MAX-CUT in $\R^3$. For unconstrained 0-1 programs, a special representation in terms of weighted sum of squares is provided.

Keywords: 0-1 programming; SDP relaxations;

Category 1: Integer Programming (0-1 Programming )

Category 2: Linear, Cone and Semidefinite Programming (Semi-definite Programming )

Category 3: Other Topics (Other )

Citation: SIAM J. Optim. 12 (2002), pp. 756--769. http://epubs.siam.org/sam-bin/dbq/article/38007

Download:

Entry Submitted: 12/06/2001
Entry Accepted: 12/06/2001
Entry Last Modified: 05/14/2002

Modify/Update this entry