Skip to main content
2 of 4
added tag ag.algebraic-geometry
opti
  • 51
  • 3

Characterizing non-zero polynomials on semialgebraic sets: a kind of positivstellensatz generalization

A polynomial positivstellensatz is an algebraic characterization of polynomials which are positive on a semialgebraic sets. Is there a similar kind of characterization which can determine whether a polynomial is non-zero?

One "straightforward" answer to this is to simply apply a positivstellensatz to the square of the polynomial, but I am wondering if there is an approach which avoids the squaring operation.

To motivate this further, let $S = \{ x \in {\mathbb R}^n : f_i(x) \geq 0\}$ be a semialgebraic set. There are various kinds of positivstellensatz methods, here I will use Putinar's (along with its implied assumptions on $S$, which are mildly stronger than compactness): if a polynomial $p$ is positive on $S$, then $p$ can be written in the form $$p = \sigma_0 + \sum_i \sigma_i f_i$$ where $\sigma_0, \sigma_i$ are polynomial sums of squares (sos). Such a characterization lends itself to semidefinite programming, which is part of the underlying motivation behind this question.

If $S$ has only one connected component, determining whether $p$ is non-zero on $S$ is trivial: simply apply the positivstellensatz to $p$ or $-p$, one of which will succeed if $|p| > 0$ on $S$. My question is more interesting in the case when $S$ has multiple connected components. As mentioned, one possible approach is to apply a positivstellensatz to $p^2$, which in the case of Putinar's asks whether there exists sos $\sigma_i$ such that $$p^2 = \sigma_0 + \sum_i \sigma_i f_i.$$ However, note the equality constraint is now quadratic in the coefficients of $p$. In my application, I am attempting to find a polynomial $p$ such that $|p| > 0$ on $S$ (along with other conditions), and so this quadratic constraint becomes more of an issue, i.e., if the coefficients of $p$ are the unknowns, then the quadratic constraint is not convex, one cannot easily apply semidefinite programming, and the optimization/feasibility problem in finding $p$ is much harder, potentially NP-hard. One way out of this is to search among all polynomials of the form $q = \sigma_0 + \sum_i \sigma_i f_i$, and try to find a $q$ whose symmetric positive semidefinite Gram matrix is of rank one, a convex proxy of which is to minimize the trace of $q$'s Gram matrix. This can work sometimes, but not always.

In short, I am wondering: are there any kind of characterizations of non-zero polynomials on compact semialgebraic sets without resorting to squaring the polynomial and applying a positivstellensatz? I am relatively new to these methods in real algebraic geometry, so I may have missed something in my literature search; any insights from the community here would be much appreciated.

opti
  • 51
  • 3