Prof. Juan Vera and Olga Kuryatnikova of Tilburg University to visit in March

Prof. Juan Vera and Olga Kuryatnikova of Tilburg University are scheduled to visit the Research Training Group ALOP in March for research collaboration.

During their visit, they will speak on the following topics:

Copositive certificates of non-negativity (Prof. Juan Vera)

Abstract:

Sum-of-squares (sos) certificates of non-negativity, such as Putinar’s Positivstellensatz, have been used to obtain powerful numerical techniques to solve polynomial optimization (PO) problems. Using such certificates, hierarchies of semidefinite relaxations are obtained for PO. Usually the use of sos-certificates requires compactness or stronger assumptions on the feasible set, limiting the range of applications.

We show that under suitable conditions on the polynomial h(x) and the set S, the non-negativity of a polynomial over the set  {x in S: h(x) = 0} can be certified in terms of the non-negative polynomials on S even if the set S is unbounded. Moreover, a characterization of the pairs (S, h) for which  such type of non-negativity certificate exists is provided in terms of an appropriate condition on S and h. Moreover, the non-negativity certificate presented here readily allows the use of copositive polynomials (as opposed to the more common use of sos). In particular it encompasses the results of Burer and Pena-Vera-Zuluaga for representation of polynomial optimization problems as copositive ones.

Approximating the cone of copositive kernels with application to the kissing number problem. (Olga Kuryatnikova)

Abstract:

Recent research has shown how to generalize copositive formulations of the stable set problem in finite graphs to infinite graphs. This allows to express the kissing number problem, i.e., finding the maximum number of non-overlapping unit spheres that can simultaneously touch another unit sphere, as an optimization problem over copositive kernels. We generalize two existing approximations to the cone of copositive matrices to obtain approximations to the cone of copositive kernels.

Using the latter approximations, we construct a hierarchy of upper bounds on the kissing number. As a side result, we characterize positive definite functions invariant under automorphisms of the sphere fixing a given set of points. The presentation will be self-contained.

The presentations will take place on Monday March 5 at 10:30 c.t. in E 51.