We present a hybrid symbolic-numeric algorithm for certifying a
polynomial or a rational function with rational coefficients to be
non-negative for all real values of the variables by computing a
representation for it as a fraction of two polynomial sum-of-squares
(SOS) with rational coefficients. We can either perform high
precision Newton iterations on the numerical SOS computed by SDP
solvers in Matlab or use the high precision SDP solver in Maple
to get the SOS with necessary precision, then we can
convert the numerical SOS into an exact rational SOS by orthogonal
projection or rational coefficient vector recovery. Sums-of-squares rational lower bound certificates
for the radius of positive semidefiniteness of a multivariate
polynomial also offer an alternative SOS proof for those positive
definite polynomials that are not SOS but have a positive distance
to the nearest polynomial with a real root. Moreover,
we show that a random linear transformation of the variables allows
with probability one for certifying the positive semidefinteness
of a multivariate polynomial by representing it as an SOS over the
variety defined by partial derivatives of the polynomial with
respect to each variable except one.
Joint work with Feng Guo, Sharon E. Hutton, Erich L.
Kaltofen, Bin Li, Mohab Safey El Din and Zhengfeng Yang.
Tuesday, November 23, 2010
11:00AM AP&M 2402
Center for Computational Mathematics9500 Gilman Dr. #0112La Jolla, CA 92093-0112Tel: (858)534-9056