Conference Agenda

A description of a nonnegative polynomial as a sum of squares gives a concise proof of its nonnegativity. Computationally, such sum-of-squares decompositions are appealing because we can search for them by solving a semidefinite feasibility problem. This connection means that optimization and decision problems arising in a range of areas, from robotics to extremal combinatorics, can be reformulated as, or approximated with, semidefinite optimization problems.

This minisymposium highlights the roles of various kinds of additional structures, including symmetry and sparsity, in understanding when (structured) sum of squares decompositions do and do not exist. It will also showcase interesting connections between sums of squares and a range of areas, such as extremal combinatorics, dynamical systems and control, and algorithms and complexity theory.

In several safety-critical applications, one has to learn the behavior of an unknown dynamical system from noisy observations of a very limited number of trajectories. For example, to autonomously land an airplane that has just gone through engine failure, limited time is available to learn the modified dynamics of the plane before appropriate control action can be taken. Similarly, when a new infectious disease breaks out, few observations are initially available to understand the dynamics of contagion.

In situations of this type where data is limited, it is essential to exploit “side information”---e.g. physical laws or contextual information---to assist the task of learning. We present a mathematical formalism of the problem of learning a dynamical system with side information, where side information can mean a concrete collection of local or global properties of the dynamical system. We show that sum of squares optimization is particularly suited for learning a dynamical system that best agrees with the observations and respects the side information.

Based on joint work with Bachir El Khadir (Princeton).

We investigate the convergence rate of a hierarchy of measure-based upper bounds introduced by Lasserre (2011) for the minimization of a polynomial f over a compact set K. These bounds are obtained by searching for a degree 2r sum-of-squares density function h minimizing the expected value of f over K.

The convergence rate to the global minimum of f over K is known to be in O(1/r^2) for special sets K like the box, ball and sphere, so we consider here general compact sets. We show a convergence rate in O((log r)/r) when K satisfies a minor geometric condition and a rate in O(((log r)/r)^2) when K is a convex body, improving on the current best known bounds for these cases. These results can be refined when making assumptions on the order of f at a global minimizer.

Our analysis relies on combining tools from convex geometry and approximation theory, making use in particular of approximations of the Dirac delta function by fast-decreasing polynomials.

This is based on joint work with Monique Laurent.

In this talk I will show how one can apply sum-of-squares techniques for various extremal geometric problems on the unit sphere, especially finding thinnest coverings or spherical designs.