Abstract : We propose a new approach to bound Boolean quadratic optimization problems. The idea is to re-express Boolean constraints as one ''spherical'' constraint. Dualizing this constraint then amounts to a semidefinite least-squares problem which can be efficiently solved. Studying this dualization also provides an alternative interpretation of the relaxation and reveals a new class of non-convex problems with no duality gap.
https://hal.inria.fr/inria-00070518 Contributor : Jérôme MalickConnect in order to contact the contributor Submitted on : Monday, March 25, 2013 - 2:27:01 PM Last modification on : Thursday, January 20, 2022 - 5:28:36 PM Long-term archiving on: : Wednesday, June 26, 2013 - 4:01:26 AM