| In 1900, David Hilbert in his famous address at the International Congress of Mathematicians in Paris proposed as his 17th problem the following:Conjecture 0.1 (Hilbert). Let f(x1,…,xn)∈R(x1,…,xn), A necessary and sufficient condition that f is a sum of squares in R(x1,…, xn) is that f is positive definite (i.e. f(x1,…, xn)≥0 for all (x1,…, xn)∈Rn for which f is definde).If f(x)∈R(x) is positive definite, then it is a sum of two squares in R(x). Hilbert proved in 1893 that If f(x, y)∈R(x, y) is positive definite, then it is a sum of four squares in R(x). This conjecture were proved by Artin in 1927 for both R and Q.Based on those discussions about Hilbert 17th problem, We consider a problem:How to check global nonnegativity of an univariate polynomial?A basic problem that appears in many areas of mathematics is that of checkingglobal nonnegativity of a function. Concretely, the problem is to give equivalentconditions or a procedure for checking the validity of the propositionThis is a very important problem, and lots of research efforts have been devoted to it.In this paper, we discuss three methods to check global nonnegativity of a univariate function. We mainly explore how to exactly certificate rational lower bounds of a univariate function near the global optima via SOS (Sums Of Squares) relaxations and semidefinite programming (SDP). We also discuss a method coming from John Harrison about finding SOS decompositions by adding a perturbed polynomial to the original univariate polynomials. And we introduce a method putting forward by YangLu about a complete discrimination system for polynomials.The problem of checking global nonnegativity of univariate polynomials can be formulated as computing lower bound certificates. In this paper, We mainly explore how to exactly certificate rational lower bounds of a univariate function near the global optima via SOS (Sums Of Squares) relaxations and semidefinite programming (SDP). Consider polynomial optimization problems of the formWe can formulate it as semidefinite programming (SDP) via sum-of-squares (SOS) and truncated moment techniquesWhere md(x) is the column vector of all terms up to degree d = deg(f)/2. The dimension of md(x) is d + 1. And there are 1 + 2d restricts.The problem of finding the rational SOS is equivalent to finding a rational positive semidefinite symmetric matrix W solving SOS problem (5). Inspired by the method in [Peyrl and Parrilo 2007], We start with a numerical solution W computed by semidefinite programming solving problem (5). However, we refine the matrix W further by using Newton iteration. In the next step, we lower r* to a rational bound (?)∈Q, convert W to a rational matrix and project the matrix onto the affine linear hyperplanedenoting the nearest matrix in X by (?). The projection is done by solving a rationalleast squares problem exactly. The hope is that W is positive semidefinite, yielding a SOS proof for the lower bound (?)∈Q. If W is not positive semidefinite, then we may increase the precision or reduce (?) future and try again. The numeric results and SOS produced by the current fixed precision SDP packages (SOSTOOLS, YALMIP, SeDuMi etc.) are usually too coarse. Therefore,before projection to exact SOS via Maple's exact linear algebra we refine the SOS by rank-preserving Newton iteration. This method can be used to find the rational SOS of polynomials exactly. In fact, within minutes we can establish a lower bound for our SOS problems.Given a semidefinite univariate polynomial with rational coefficients, we already know how to find the SOS decomposition of the polynomial exactly. Then an interesting question is whether can we reduce the number n of SOS decomposition f(x) = f1(x)2 +…+ fn(x)2, fi(x)∈Q[x]? Landau put forward a theorem about this question firstly.Theorem 0.1 (Landau). Let f(x)∈Q[x] be a positive definite function. Then f is a sum of eight squares in Q[x].Is eight best possible? If we let r be the smallest natural number such that every sum of squares in Q[x] is already a sum of r squares, then Theorem 0.1 says that r≤8. The function x2 + 7 = x2 + 22 + 1 + 1 + 1 shows that r≥5. Pourchet has shown that r = 5.Theorem 0.2 (Pourchet 1971). Let f(x)∈Q[x] be a non-zero positive definite function. Then there exist f1(x), f2(x), f3(x), f4(x), f5(x)∈Q[x] such thatWe shall give a series of lemmas leading towards a more general result. We make heavy use of the Local-Global principle; in particular the Haees-Minkowski theorem. Then we are searching for a constructive method to this problem. At present, our algorithms can only successfully apply to a small part of PSD univariate polynomial with rational coefficients. Given a random PSD univariate polynomial, we can construct a sum of squares of five polynomials in p-adic field (for any prime p). However, replacing the decomposition in Qp[x] to that of in Q[x] would be highly non-trivial even for univariate polynomial. Thus, it would be interesting to study it in the future.
|
PDF Full Text Request