Skip to main content
clarified the contents of the stuff that I wrote.
Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

EDIT The material below is not really an answer to the original question, but only highlights a technique for checking positivity of a specific polynomial, not an entire class. It might well be impossible to have a generic scheme for entire families of polynomials in general.


Let me recall some results, discussed in these lecture notes, which are helpful for numerically checking if a univariate polynomial is nonnegative.

Theorem A univariate polynomial is nonnegative if and only if it is a sum of squares.

Theorem Let $\mathbf{x}=[1,x,x^2,\ldots,x^m]^T$, and let $P(x)$ have degree $2m$. Then, $P(x)$ is nonnegative if and only if there exists a $m+1 \times m+1$ positive semidefinite matrix $Q$ such that $P(x) = \mathbf{x}^TQ\mathbf{x}$.

Let $P(x)=\sum_{i=0}^{2m} p_ix^i$. It can be further shown that the matrix $Q$ must satisfy \begin{equation*} p_i = \sum_{j+k=i} Q_{jk},\qquad i=0,1,\ldots,2m. \end{equation*}

Theorem If we can find a positive semidefinite matrix $Q$ that satisfies the above linear constraints (this can be done using regular semidefinite programming software), then the polynomial $P(x)=\sum_{i=0}^{2m} p_ix^i$ is nonnegative or SOS, otherwise not.

Let me recall some results, discussed in these lecture notes, which are helpful for numerically checking if a univariate polynomial is nonnegative.

Theorem A univariate polynomial is nonnegative if and only if it is a sum of squares.

Theorem Let $\mathbf{x}=[1,x,x^2,\ldots,x^m]^T$, and let $P(x)$ have degree $2m$. Then, $P(x)$ is nonnegative if and only if there exists a $m+1 \times m+1$ positive semidefinite matrix $Q$ such that $P(x) = \mathbf{x}^TQ\mathbf{x}$.

Let $P(x)=\sum_{i=0}^{2m} p_ix^i$. It can be further shown that the matrix $Q$ must satisfy \begin{equation*} p_i = \sum_{j+k=i} Q_{jk},\qquad i=0,1,\ldots,2m. \end{equation*}

Theorem If we can find a positive semidefinite matrix $Q$ that satisfies the above linear constraints (this can be done using regular semidefinite programming software), then the polynomial $P(x)=\sum_{i=0}^{2m} p_ix^i$ is nonnegative or SOS, otherwise not.

EDIT The material below is not really an answer to the original question, but only highlights a technique for checking positivity of a specific polynomial, not an entire class. It might well be impossible to have a generic scheme for entire families of polynomials in general.


Let me recall some results, discussed in these lecture notes, which are helpful for numerically checking if a univariate polynomial is nonnegative.

Theorem A univariate polynomial is nonnegative if and only if it is a sum of squares.

Theorem Let $\mathbf{x}=[1,x,x^2,\ldots,x^m]^T$, and let $P(x)$ have degree $2m$. Then, $P(x)$ is nonnegative if and only if there exists a $m+1 \times m+1$ positive semidefinite matrix $Q$ such that $P(x) = \mathbf{x}^TQ\mathbf{x}$.

Let $P(x)=\sum_{i=0}^{2m} p_ix^i$. It can be further shown that the matrix $Q$ must satisfy \begin{equation*} p_i = \sum_{j+k=i} Q_{jk},\qquad i=0,1,\ldots,2m. \end{equation*}

Theorem If we can find a positive semidefinite matrix $Q$ that satisfies the above linear constraints (this can be done using regular semidefinite programming software), then the polynomial $P(x)=\sum_{i=0}^{2m} p_ix^i$ is nonnegative or SOS, otherwise not.

Source Link
Suvrit
  • 28.6k
  • 7
  • 82
  • 150

Let me recall some results, discussed in these lecture notes, which are helpful for numerically checking if a univariate polynomial is nonnegative.

Theorem A univariate polynomial is nonnegative if and only if it is a sum of squares.

Theorem Let $\mathbf{x}=[1,x,x^2,\ldots,x^m]^T$, and let $P(x)$ have degree $2m$. Then, $P(x)$ is nonnegative if and only if there exists a $m+1 \times m+1$ positive semidefinite matrix $Q$ such that $P(x) = \mathbf{x}^TQ\mathbf{x}$.

Let $P(x)=\sum_{i=0}^{2m} p_ix^i$. It can be further shown that the matrix $Q$ must satisfy \begin{equation*} p_i = \sum_{j+k=i} Q_{jk},\qquad i=0,1,\ldots,2m. \end{equation*}

Theorem If we can find a positive semidefinite matrix $Q$ that satisfies the above linear constraints (this can be done using regular semidefinite programming software), then the polynomial $P(x)=\sum_{i=0}^{2m} p_ix^i$ is nonnegative or SOS, otherwise not.