×

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

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
PDFBibTeX XMLCite
Full Text: DOI