Skip to Main content Skip to Navigation
New interface
Journal articles

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.
Document type :
Journal articles
Complete list of metadata
Contributor : Marta Abril Bucero Connect in order to contact the contributor
Submitted on : Friday, August 21, 2015 - 12:44:52 PM
Last modification on : Saturday, June 25, 2022 - 7:41:55 PM
Long-term archiving on: : Wednesday, April 26, 2017 - 10:02:44 AM


Files produced by the author(s)


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License




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



Record views


Files downloads