2

Given the coefficients of a multivariable polynomial, how can I determine if it's bounded from below? In other words, given a polynomial $p\left(x_1,x_2,...x_n\right)$, does there exist a real number $C$ such that $p\left(x_1,x_2,...x_n\right) \ge C$?

I do not need to find the minimum value of the polynomial, I just want to know whether or not it is bounded.

Rodrigo de Azevedo
  • 1
Max Radin
  • 207

1 Answers1

5

Deciding whether the polynomial

$$p (x_1, x_2, \dots, x_n) - c$$

is globally nonnegative is not easy. Fortunately, deciding whether $p (x_1, x_2, \dots, x_n) - c$ can be written as a sum of squares (SOS) is easy, as the decision procedure is a semidefinite program, which is in P. However, not all globally nonnegative polynomials can be written as a sum of squares.

From one of Parrilo's papers [0], an example to clarify the above:

enter image description here

[0] Pablo Parrilo, Semidefinite programming relaxations for semialgebraic problems, 2001.

Rodrigo de Azevedo
  • 1
  • So, given a homogeneous polynomial of even degree in several variables, can be tell whether it is positive at infinity? – Will Jagy Jan 18 '17 at 01:46
  • 1
    Understood, I am trying to figure out what is going on; one sufficient condition for the whole polynomial to have a lower bound is for the highest degree homogeneous part to be strictly positive at infinity, meaning strictly positive on the standard unit sphere. Sorry for, well, changing the subject a bit. – Will Jagy Jan 18 '17 at 01:52
  • @WillJagy As I am not a mathematician, I am not qualified to comment on that. From a computational viewpoint, one finds a symmetric positive semidefinite matrix via semidefinite programming, then one obtains the SOS decomposition via Cholesky decomposition. There is some "voodoo magic" here, as the SDP solver uses floating-point numbers and may produce an SOS decomposition that is not quite exact. If one used arbitrary-precision rational numbers, it would be nicer, but slower. – Rodrigo de Azevedo Jan 18 '17 at 01:58
  • Rodrigo, thank you. I will read up a bit on Hilbert's 17th problem, see whether my sub-problem is known. – Will Jagy Jan 18 '17 at 02:01
  • The paper I linked to above has lots of references. Another one is: Pablo A. Parrilo, Bernd Sturmfels, Minimizing Polynomial Functions, arXiv:math/0103170. – Rodrigo de Azevedo Jan 18 '17 at 02:04
  • 1
    Excellent. The problem I made up is known but far more difficult than I thought... see the example " p is homogeneous of even degree " in https://en.wikipedia.org/wiki/Positive_polynomial#Examples The article by Reznick is available online. – Will Jagy Jan 18 '17 at 02:30