On Positivity of Polynomials: The Dilation Integral Method

The focal point of this paper is the well known problem of polynomial positivity over a given domain. More specifically, we consider a multivariate polynomial f(x) with parameter vector x restricted to a hypercube X subset of R-n. The objective is to determine if f (x) > 0 for all x is an element of X. Motivated by NP-Hardness considerations, we introduce the so-called dilation integral method. Using this method, a "softening" of this problem is described. That is, rather than insisting that f(x) be positive for all x is an element of X, we consider the notions of practical positivity and practical non-positivity. As explained in the paper, these notions involve the calculation of a quantity epsilon > 0 which serves as an upper bound on the percentage volume of violation in parameter space where f(x) <= 0. Whereas checking the polynomial positivity requirement may be computationally prohibitive, using our epsilon-softening and associated dilation integrals, computations are typically straightforward. One highlight of this paper is that we obtain a sequence of upper bounds epsilon(k) which are shown to be "sharp" in the sense that they converge to zero whenever the positivity requirement is satisfied. Since for fixed n, computational difficulties generally increase with k, this paper also focuses on results which reduce the size of the required k in order to achieve an acceptable percentage volume certification level. For large classes of problems, as the dimension of parameter space n grows, the required k value for acceptable percentage volume violation may be quite low. In fact, it is often the case that low volumes of violation can be achieved with values as low as k = 2.