[Home]
[
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Certification via Symbolic-Numeric Computations
Lihong Zhi
Chinese Academy of Sciences
Abstract:
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
News]
[ Events]
[ People]
[ Research]
[ Education]
[Visitor Info]
[UCSD Only]
[Admin]
Directors:
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Randolph E. Bank
Philip E. Gill
Michael Holst
Administrative Contact:
[ Click to Send Email ]
Lihong Zhi
Chinese Academy of Sciences
Abstract:
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