Banff International Research Station

Workshop on Positive Polynomials and Optimization

October 7 - 12 2006
Hike the Victoria Glacier!
Organizers:
Salma Kuhlmann, University of Saskatchewan.
Sanjay Lall, Stanford University.
Vicki Powers, Emory University, Atlanta.
Frank Sottile, Texas A&M University.
Participants:
Doris Augustin, University of Regensburg
Mari Castel, Emory University
Jaka Cimpric, University of Ljubljana
Raul Curto, University of Iowa
Daniele Gondard, Université Pierre et Marie Curie
Bill Helton, University of California at San Diego
Chris Hillar, Texas A&M University
Ali Jadbabaie, University of Pennsylvannia
Salma Kuhlmann, University of Saskatchewan.
Sanjay Lall, Stanford University
Jean-Bertrand Lasserre, LAAS-CNRS Toulouse
Monique Laurent, CWI, Amsterdam
Muarry Marshall, University of Saskatchewan
Yurii Nesterov, Louvain-la-Neuve
Tim Netzer, Universitä Konstanz
Jiawang Nie, University of California at Berkeley
Antonis Papachristodoulou, Oxford University
Pablo Parrilo, MIT
Dima Pasechnik, Singapore
Javier Pena, Carnegie Mellon University
Daniel Plaumann, Universitä Konstanz
Vicki Powers, Emory University
Alex Prestel, Universität Konstanz
Mihai Putinar, University of California at Santa Barbara
James Renegar, Cornell University
Bruce Reznick, University of Illinois
Marie-Françoise Roy, Université Rennes
Claus Scheiderer, Universität Konstanz.
Konrad Schmüdgen, Universitët Leipzig
Niels Schwartz, Universität Passau
Markus Schweighofer, Universität Konstanz
Frank Sottile, Texas A&M University.
Thorsten Theobald, Yale University
Levent Tunçel, University of Waterloo
Henry Wolkowicz, Waterloo
Yuriy Zinchenko, McMaster University
Luis Zuluaga, University of New Brunswick

Scientific Overview:

About five years ago, deep theoretical results on positive polynomials were combined with numerical methods from semi-definite 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 semi-definite programming. Letting the degree d increase gives a sequence of tractable relaxations to the NP-complete 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 Rn 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.