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 metadatas

https://hal.inria.fr/hal-00981546
Contributor : Marta Abril Bucero <>
Submitted on : Friday, August 21, 2015 - 12:44:52 PM
Last modification on : Wednesday, October 10, 2018 - 10:09:42 AM
Long-term archiving on : Wednesday, April 26, 2017 - 10:02:44 AM

Files

jsc-bbr-rev.pdf
Files produced by the author(s)

Licence


Distributed under a Creative Commons Attribution - NonCommercial 4.0 International License

Identifiers

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⟩

Share

Metrics

Record views

559

Files downloads

229