Banff International Research StationWorkshop on Positive Polynomials and
Optimization

Hike the Victoria Glacier! 
About five years ago, deep theoretical results on positive polynomials were combined with numerical methods from semidefinite programming to create a powerful tool for solving some classes of decision and optimization problems. A solution to the moment problem by Schm¨dgen, Putinar, and Jacobi and Prestel showed that polynomials positive on compact semialgebraic sets have algebraic certificates of positivity, which are representations involving squares of polynomials from which positivity on the given domain is immediate. Positivity is related to optimization: the minimum of a polynomial f(x) on a domain is the maximum number m such that f(x)m is positive on that domain. N.Z. Shor and Parrilo, as well as Lasserre, realized that optimizing m such that f(x)m had a certificate of positivity involving squares of bounded degree d is readily computed via semidefinite programming. Letting the degree d increase gives a sequence of tractable relaxations to the NPcomplete problem of minimizing a polynomial on a compact domain.
This algorithm has subsequently inspired advances in several directions within different mathematical communities. There have been new developments in positive polynomials, new work on the convergence of this sequence of relaxations, clever new formulations of other decision problems as such semidefinite programs, and innovative applications of these algorithms. For example, Blekherman gave a precise and quantitative result showing that it is rare for a polynomial that is positive on R^{n} to be a sum of squares, Lasserre and others now understand the robustness and convergence of the sequence of approximate minima coming from his algorithm, Lall and others use these methods decisively in some problems of control theory, and De Klerk and his coauthors have used Lasserre's relaxations to determine better bounds for the crossing number of complete bipartite graphs.