2011 Apr 09 at 11:30
DC 1302
Victoria Powers, Emory University
Let R[X] denote the real polynomial ring in n variables R[X_1, ... , X_n]. Given f in R[X] and suppose f > 0 or f >= 0 on a semialgbraic set K, a subset of R^n, i.e., one defined by a finite number of polynomial inequalities. By a "certificate of positivity" for f on K, we mean an expression for f, usually involving sums of squares and the defining polynomials of K, from which one can observe the positivity condition immediately. In recent years, techniques from semidefinite programming have produced algorithms for finding certificates of positivity; these algorithms have many applications in optimization, control theory, and other areas. However, the output of these algorithms is, in general, numerical, while for many applications exact polynomial identities are needed. In this talk, we look at questions such as these: If f and K are defined over Q, does there exist a certificate of positivity for f on K for which the sums of squares are sums of squares of polynomials defined over Q? How can a numerical certificate of positivity be transformed into an exact rational identity? We will discuss theoretical results as well as hybrid symbolic-numeric algorithms due to Peyrl-Parrilo, Kaltofen-Li-Yang-Zhi, and others.
This talk is part of the East Coast Computer Algebra Day (ECCAD 2011). ECCAD is open to all and free to attend, but we encourage registration. See http://www.cs.uwaterloo.ca/conferences/eccad2011