The Spherical Constraint in Boolean Quadratic Programs

Jérôme Malick 1
1 BIPOP - Modelling, Simulation, Control and Optimization of Non-Smooth Dynamical Systems
Inria Grenoble - Rhône-Alpes, LJK - Laboratoire Jean Kuntzmann, INPG - Institut National Polytechnique de Grenoble
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.
Type de document :
Article dans une revue
Journal of Global Optimization, Springer Verlag, 2007, 39 (4), pp.609-622. 〈10.1007/s10898-007-9161-1〉
Liste complète des métadonnées

Littérature citée [33 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/inria-00070518
Contributeur : Jérôme Malick <>
Soumis le : lundi 25 mars 2013 - 14:27:01
Dernière modification le : jeudi 11 janvier 2018 - 06:21:51
Document(s) archivé(s) le : mercredi 26 juin 2013 - 04:01:26

Fichier

07-malick.pdf
Fichiers produits par l'(les) auteur(s)

Identifiants

Collections

Citation

Jérôme Malick. The Spherical Constraint in Boolean Quadratic Programs. Journal of Global Optimization, Springer Verlag, 2007, 39 (4), pp.609-622. 〈10.1007/s10898-007-9161-1〉. 〈inria-00070518v2〉

Partager

Métriques

Consultations de la notice

217

Téléchargements de fichiers

373