PolSys seminar
Real roots of polynomial systems, semi-definite programming and border basis
Intervenant(s) : Bernard Mourrain (projet GALAAD, Inria Sophia-Antipolis)
Computing the real roots of polynomial equations is a problem for which, several algebraic methods have been developed over the last decade(s). This problem can also be seen from the perspective of "mathematical programming": find the minimum (and all the minimizers) of a (polynomial) function on a (semi-algebraic) set.
Such a general polynomial minimization problem can be approximated by a hierarchy of finite dimensional convex optimization problems, which can be solved efficiently by Semi-Definite Programming tools. This approach proposed by Lasserre some years ago is known to converge to the optimal value in good situations.
We show that we can construct an exact hierarchy of semi-definite programming problems for solving a general polynomial optimization problem: in a finite number of steps, either it detects that there is no minimizer or it reaches the minimum and yields the minimizer ideal. The approach provides a uniform treatment of different optimization problems considered previously. Applications to global optimization, optimization on a smooth real variety, optimization on finite semi-algebraic sets, real radical computation illustrate it. Combining it with algebraic techniques such as border bases and flat extension criteria, we describe a new algorithm to compute the minimizers of a polynomial function on a closed semi-algebraic set and in particular to compute real roots of polynomial equations, when there is a finite number of minimizers. Experimentations show the good practical behaviour of the approach.
This is a joint work with M. Abril - Bucero.
Plus d'informations ici …
Elias.Tsigaridas (at) nulllip6.fr