To prove that a polynomial is nonnegative on Rn, one can try to show that it
is a sum of squares of polynomials (SOS). The latter problem is now known to be
reducible to a semi-definite programming (SDP) computation that is much faster than
classical algebraic methods, thus enabling new speed-ups in algebraic optimization.
However, exactly how often nonnegative polynomials are in fact sums of squares of
polynomials remains an open problem. Blekherman was recently able to show that
for degree k polynomials in n variables with k = 4 fixed those that are SOS occupy
a vanishingly small fraction of those that are nonnegative on Rn, as n -> 1. With
an eye toward the case of small n, we refine Blekherman'[s bounds by incorporating
the underlying Newton polytope, simultaneously sharpening some of his older bounds
along the way. Our refined asymptotics show that certain Newton polytopes may lead
to families of polynomials where efficient SDP can still be used for most inputs.
| Identifer | oai:union.ndltd.org:tamu.edu/oai:repository.tamu.edu:1969.1/ETD-TAMU-2009-05-787 |
| Date | 16 January 2010 |
| Creators | Sethuraman, Swaminathan |
| Contributors | Rojas, J M. |
| Source Sets | Texas A and M University |
| Language | en_US |
| Detected Language | English |
| Type | Book, Thesis, Electronic Dissertation |
| Format | application/pdf |
Page generated in 0.002 seconds