Border Basis relaxation for polynomial optimization

Marta Abril Bucero (1) , Bernard Mourrain (1)

1 GALAAD2 - Géométrie , Algèbre, Algorithmes

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.

Mots clés: border basis; polynomial optimization; moment matrices; SDP; flat extension

Domaines: Géométrie algébrique [math.AG]

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⟩