inria-00070518, version 2
The Spherical Constraint in Boolean Quadratic Programs
Jérôme Malick
a, 1, 2
Journal of Global Optimization 39, 4 (2007) 609-622
Résumé : 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.
- a – CNRS
- 1 : Laboratoire Jean Kuntzmann (LJK)
- CNRS : UMR5224 – Université Joseph Fourier - Grenoble I – Université Pierre-Mendès-France - Grenoble II – Institut Polytechnique de Grenoble - Grenoble Institute of Technology
- 2 : BIPOP (INRIA Grenoble Rhône-Alpes / LJK Laboratoire Jean Kuntzmann)
- INRIA – Laboratoire Jean Kuntzmann
- Domaine : Informatique/Autre
- Mots-clés : Combinatorial Optimization – Relaxation – Lagrangian Duality – Semidefinite Least-Squares
- Référence interne : RR-5489
- Versions disponibles : v1 (31-05-2006) v2 (25-03-2013)
- inria-00070518, version 2
- http://hal.inria.fr/inria-00070518
- oai:hal.inria.fr:inria-00070518
- Contributeur : Jérôme Malick
- Soumis le : Lundi 25 Mars 2013, 14:27:01
- Dernière modification le : Jeudi 9 Mai 2013, 11:12:28
Documents associés
Exporter