Border basis relaxation for polynomial optimization. (May 2016)

• Record Type: Journal Article
• Authors: Abril Bucero, Marta; Mourrain, Bernard
• Is Part Of: Journal of symbolic computation. Volume 74(2016)
• Page Start: 378
• Page End: 399
• Publication Date: 2016-05
• Subjects: Polynomial optimization -- Moment matrices -- Flat extension -- Border basis; Mathematics -- Data processing -- Periodicals; Numerical analysis -- Data processing -- Periodicals; Automatic programming (Computer science) -- Periodicals; Mathématiques -- Informatique -- Périodiques; Analyse numérique -- Informatique -- Périodiques; Programmation automatique -- Périodiques; Automatic programming (Computer science); Mathematics -- Data processing; Numerical analysis -- Data processing; Periodicals; Electronic journals; 510.285
• DOI: 10.1016/j.jsc.2015.08.004
• Languages: English
• ISSNs: 0747-7171

Abstract

Abstract: A relaxation method based on border basis reduction which improves the efficiency of Lasserre's approach is proposed to compute the infimum 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 infimum, 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. Experiments show the impact of this new method on significant benchmarks.