Seminars

Title: On the existence of sums-of-squares decompositions of
multivariate polynomials.

Joint works with Feng Guo and Lihong Zhi (Chinese Academy of Sciences, KLMM)

Abstract: Decomposing multivariate polynomials into sums-of-squares
(SOS) is a fundamental algorithmic problem which has applications in
global optimization, control theory, etc. From Artin's work, it is
well-known that that not all non-negative polynomials are
sums-of-squares of polynomials. Moreover, Blekherman proved that the
volume of SOS divided by the volume of non-negative polynomials tends
to $0$ when the number of variables tends to infinity. Thus,
identifying families of problems on which algebraic certificates based
on sums-of-squares can be obtained is relevant.

In this talk, we will consider two problems. The first one is related
to Sturmfels' conjecture: "given $f$ with {\em rational} coefficients,
that is a sums-of-squares of polynomials with {\em real} coefficients,
then there exist a sums-of-squares decompositions of $f$ with {\em
rational coefficients}". We won't discuss the truth of this conjecture
but we will give an algorithm which takes as input a multivariate
polynomial $f$ with rational coefficients and which returns a
sums-of-squares decomposition of $f$ over the rationals iff such a
decomposition exist. Complexity estimates are given on the number of
bit-operations and the bit size of the output.

The second problem we will discuss is the problem of certifying lower
bounds for the infimum of a multivariate polynomial by means of
sums-of-squares. In a previous work, Nie, Demmel and Sturmfels prove
that, in the case of existence of a minimizer, such a certificate can
be obtained modulo the gradient ideal of the considered polynomial if
this ideal is radical and 0-dimensional. By relating the global
optimization problem to the notion of generalized critical values, we
provide new algebraic certificates by means of sums-of-squares without
any assumption.