An explicit equivalent positive semidefinite program for nonlinear 0-1 programs. (English) Zbl 1007.90046

Lasserre, Jean B.

SIAM J. Optim. 12, No. 3, 756-769 (2002).

Summary: 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 \(\mathbb{R}^3\). For unconstrained 0-1 programs, a special representation in terms of a weighted sum of squares is provided.

MSC:

90C22	Semidefinite programming
90C09	Boolean programming
90C27	Combinatorial optimization
90C30	Nonlinear programming

Keywords:

integer programming; semidefinite programming; moment problem; real algebraic geometry