An exact solution for bivalent quadratic problems using semidefinite bound and fixing criterions

Tongli Zhang, Yong Xia

Dachuan Xu, Shu-zhong Zhang

G raud Delaporte, S bastien Jouteau, Frédéric Roupin

SDP_S is a stand-alone program which formulates semidefinite (SDP) relaxations for any 0-1 quadratic problem. Moreover, it can solve the SDP by using the Spectral Bundle Method of C.Helmberg. SDP_S is an implementation of the recipe proposed by F.Roupin in the Cedric technical report RC388-2002. One of the major advantages of SDP_S is that it requires no knowledge about semidefinite programming. Indeed, the input problem has just to be stated as a natural 0-1 quadratic program. The source code (C/C++) and documentation can be found athttp://semidef.free.fr.

S. Pironio, Miguel Navascués, A. Acín

We consider optimization problems with polynomial inequality constraints in noncommuting variables. These noncommuting variables are viewed as bounded operators on a Hilbert space whose dimension is not fixed and the associated polynomial inequalities as semidefinite positivity constraints. Such problems arise naturally in quantum theory and quantum information science. To solve them, we introduce a hierarchy of semidefinite programming relaxations which generates a monotone sequence of lower bounds that converges to the optimal solution. We also introduce a criterion to detect whether the global optimum is reached at a given relaxation step and show how to extract a global optimizer from the solution of the corresponding semidefinite programming problem.

최혜지