On Positivity of Polynomials: The Dilation Integral Method
B. Ross Barmish, Pavel Sergeevich Shcherbakov, Sheila R. Ross, Fabrizio Dabbene · IEEE Transactions on Automatic Control · 2009
The focal point of this paper is the well known problem of polynomial positivity over a given domain. More specifically, we consider a multivariate polynomialf(x) with parameter vectorxrestricted to a hypercubeXsubRn. The objective is to determine iff(x) > 0 for allxisinX. Motivated by NP-Hardness considerations, we introduce the so-called dilation integral method. Using this method, a ldquosofteningrdquo of this problem is described. That is, rather than insisting thatf(x) be positive for allxisinX, we consider the notions of practical positivity and practical non-positivity. As explained in the paper, these notions involve the calculation of a quantity epsiv > 0 which serves as an upper bound on the percentage volume of violation in parameter space wheref(x) les 0 . Whereas checking the polynomial positivity requirement may be computationally prohibitive, using our epsiv-softening and associated dilation integrals, computations are typically straightforward. One highlight of this paper is that we obtain a sequence of upper bounds epsivkwhich are shown to be ldquosharprdquo in the sense that they converge to zero whenever the positivity requirement is satisfied. Since for fixedn, computational difficulties generally increase withk, this paper also focuses on results which reduce the size of the requiredkin order to achieve an acceptable percentage volume certification level. For large classes of problems, as the dimension of parameter spacengrows, the requiredkvalue 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 ask=2.