Erich Kaltofen (North Carolina State University)

will speak on

Exact certification in global polynomial optimization via sums-of-squares of rational functions with rational coeffs.

Time: 4:00PM
Date: Mon 31st May 2010
Location: Mathematical Sciences Seminar Room [map]

Further information

Abstract: Any positive semidefinite polynomial f with real (rational) coefficients, i.e., a polynomial that does not evaluate to a negative value, can be written as a finite sum

f(x_1,...,x_n) = ( g_1(x_1,...,x_n)2 + ... + g_k(x_1,...,x_n)2 )
/ g_0(x_1,...,x_n)2

where g_i are polynomials with real (rational) coefficients. If there exist g_i with g_0 = 1, f is said to be SOS, but not all f are, e.g., Motzkin's
polynomial. Any polynomial inequality f>= h is equivalent to f - h being positive semidefinite; h in global optimization is the real infimum (or a rational lower bound) of all values of f. Therefore, any g_i satisfying
f - h = 1/g_02 (g_12 + ... + g_k2) constitute a proof (exact certificate) for the inequality/optimum. Optimization with additional polynomial inequality constraints are handled by various so-called Positivstellensaetze.

Two recent developments have made it possible to compute such certificates. The first are the numerical optimization algorithms for semidefinite programming. The second is a symbolic technique for converting an imprecise SOS with floating point coefficients to an exact identity over the rational numbers. Among our recent successes are a proof of the Monotone Column Permanent Conjecture for n = 4, which was completed shortly before the general conjecture could be established, proofs for sharp factor coefficient bounds of degree<= 17 ("Rump's model problem"), new SOS proofs for many known inequalities, and a deformation analysis approach to Seidenberg's problem.

In my talk I will explain how our certificates have been found and what difficulties remain. This is joint work with Sharon Hutton, Bin Li, Zhengfeng Yang, and Lihong Zhi.

(This talk is part of the Algebra and Number Theory series.)

PDF notice

Return to all seminars