Semidefinite representations of non-compact convex sets

We consider the problem of the semidefinite representation of a class of non-compact basic semialgebraic sets. We introduce the conditions of pointedness and closedness at infinity of a semialgebraic set and show that under these conditions our modified hierarchies of nested theta bodies and Lasserres relaxations converge to the closure of the convex hull of $S$. Moreover, if the PP-BDR property is satisfied, our theta body and Lasserres relaxation are exact when the order is large enough; if the PP-BDR property does not hold, our hierarchies convergent uniformly to the closure of the convex hull of $S$ restricted to every fixed ball centered at the origin. We illustrate through a set of examples that the conditions of pointedness and closedness are essential to ensure the convergence. Finally, we provide some strategies to deal with cases where the conditions of pointedness and closedness are violated.

Certificates of Impossibility of Hilbert-Artin Representations of a Given Degree for Definite Polynomials and Functions

We deploy numerical semidefinite programming and conversion to exact rational inequalities to certify that for a positive semidefinite input polynomial or rational function, any representation as a fraction of sums-of-squares of polynomials with real coefficients must contain polynomials in the denominator of degree no less than a given input lower bound. By Artins solution to Hilberts 17th problems, such representations always exist for some denominator degree. Our certificates of infeasibility are based on the generalization of Farkass Lemma to semidefinite programming. The literature has many famous examples of impossibility of SOS representability including Motzkins, Robinsons, Chois and Lams polynomials, and Reznicks lower degree bounds on uniform denominators, e.g., powers of the sum-of-squares of each variable. Our work on exact certificates for positive semidefiniteness allows for non-uniform denominators, which can have lower degree and are often easier to convert to exact identities. Here we demonstrate our algorithm by computing certificates of impossibilities for an arbitrary sum-of-squares denominator of degree 2 and 4 for some symmetric sextics in 4 and 5 variables, respectively. We can also certify impossibility of base polynomials in the denominator of restricted term structure, for instance as in Landaus reduction by one less variable.