Border Basis relaxation for polynomial optimization

Marta Abril Bucero 1 Bernard Mourrain 1
1 GALAAD2 - Géométrie , Algèbre, Algorithmes
CRISAM - Inria Sophia Antipolis - Méditerranée
Abstract : A relaxation method based on border basis reduction which improves the efficiency of Lasserre's approach is proposed to compute the optimum of a polynomial function on a basic closed semi algebraic set. A new stopping criterion is given to detect when the relaxation sequence reaches the minimum, using a sparse flat extension criterion. We also provide a new algorithm to reconstruct a finite sum of weighted Dirac measures from a truncated sequence of moments, which can be applied to other sparse reconstruction problems. As an application, we obtain a new algorithm to compute zero-dimensional minimizer ideals and the minimizer points or zero-dimensional G-radical ideals. Experimentations show the impact of this new method on significant benchmarks.
Type de document :
Article dans une revue
Journal of Symbolic Computation, Elsevier, 2015, 74, pp.378-399. 〈10.1016/j.jsc.2015.08.004〉
Liste complète des métadonnées

https://hal.inria.fr/hal-00981546
Contributeur : Marta Abril Bucero <>
Soumis le : vendredi 21 août 2015 - 12:44:52
Dernière modification le : mardi 3 mai 2016 - 15:11:34
Document(s) archivé(s) le : mercredi 26 avril 2017 - 10:02:44

Fichiers

jsc-bbr-rev.pdf
Fichiers produits par l'(les) auteur(s)

Licence


Distributed under a Creative Commons Paternité - Pas d'utilisation commerciale 4.0 International License

Identifiants

Collections

Citation

Marta Abril Bucero, Bernard Mourrain. Border Basis relaxation for polynomial optimization. Journal of Symbolic Computation, Elsevier, 2015, 74, pp.378-399. 〈10.1016/j.jsc.2015.08.004〉. 〈hal-00981546v3〉

Partager

Métriques

Consultations de la notice

408

Téléchargements de fichiers

70