The next AMS Short Course on Sum of Squares: Theory and Applications, will be held on January 14-15, 2019 before the Joint Mathematics Meetings in Baltimore, MD, which will take place January 16-19, 2019. Registration opens on September 6 on the registration form for the Joint Mathematics Meetings.
Organizers: Pablo A. Parrilo, Massachusetts Institute of Technology, and Rekha R. Thomas, University of Washington
Interest in the theory and application of sums of squares (SOS) polynomials has exploded in the last two decades, spanning a wide spectrum of mathematical disciplines from real algebraic geometry to convex geometry, combinatorics, real analysis, theoretical computer science, quantum information and engineering. SOS theory and applications are accessible to well-prepared undergraduate or beginning graduate students, as well as academics who wish to learn this material.
The origins of SOS polynomials are anchored in the 19th century by Hilbert’s famous characterization of nonnegative polynomials that are SOS. In 1924 Artin gave an affirmative answer to Hilbert’s 17th problem on whether all nonnegative polynomials were SOS of rational functions. From this the field of real algebraic geometry was born—the study of real solutions to polynomial systems. While real solutions of polynomials equations are considerably more complicated than their complex counterpart, their role in applications cannot be overstated. SOS polynomials have experienced a renaissance in the last few years following the work of Shor, Nesterov, Lasserre, and Parrilo that connected them to modern optimization via semidefinite programming. A diverse interdisciplinary community now exists around SOS polynomials with an array of conferences and research programs at many of the top institutions worldwide. While the theory is rich and fascinating with many open questions, the large array of applications are equally enticing, allowing for many different angles and access points to the field.
(1) Overview of SOS polynomials, Greg Blekherman, Georgia Institute of Technology
A polynomial with real coefficients is nonnegative if it takes only nonnegative values. For example, any SOS of polynomials is obviously nonnegative. The study of the relationship between nonnegative polynomials and SOS is a classical area in real algebraic geometry. Recent developments show this topic is inextricably linked to classical topics in algebraic geometry, and SOS techniques now play a prominent role in optimization and theoretical computer science. This lecture will be an introduction to nonnegative polynomials, sums of squares and their many applications.
(2) Lifts of Convex Sets, Hamza Fawzi, University of Cambridge
The linear projection of a convex set is convex. Consider the inverse operation: given a convex set, can we express it as the projection of a "simpler" higher-dimensional convex set? This lecture will present recent progress on this question, its connection to SOS polynomials, and some of its applications.
(3) Engineering Applications, Georgina Hall, Princeton University
SOS programs are optimization problems where the decision variables are coefficients of multivariate polynomials, the objective function is linear in these coefficients, and the constraints comprise both affine constraints in the coefficients, and SOS constraints on the polynomials. SOS programs naturally arise in a number of problems in engineering and applied mathematics, including problems in power engineering, control and robotics, statistics, machine learning, and economics and game theory. This lecture presents an overview of such applications together with some directions that could be pursued to further disseminate these techniques within more applied fields.
(4) Theoretical Computer Science, Ankur Moitra, Massachusetts Institute of Technology
Within theoretical computer science, the SOS hierarchy plays a dual role both as a methodology for devising new algorithms as well as providing evidence for computational hardness. This lecture will discuss the unique games conjecture and the planted clique problem, and how a deeper understanding of the power of SOS proofs has been intertwined with progress on these questions.
(5) Algebraic Geometry, Mauricio Velasco, Los Andes University
Looking at real projective varieties through the lens of nonnegative/SOS polynomials provides a wealth of new invariants of varieties and allow the use of powerful tools from algebraic geometry to study, and sometimes solve, problems in polynomial optimization. This lecture will be an introduction to the interplay between convex geometry and algebraic geometry focussed on a few basic examples where we understand this relationship: sets of points, algebraic curves and varieties of (very) small degree in all dimensions.
(6) Geometry of Spectrahedra, Cynthia Vinzant, North Carolina State University
Spectrahedra form a rich class of convex bodies that are computationally tractable and appear in many areas of mathematics. Examples include polytopes, ellipsoids, and more exotic convex sets, like the convex hull of some curves. This lecture will introduce the theory of spectrahedra with many examples, and discuss applications in distance geometry, moments geometry, and combinatorial optimization.
Problem set sessions are planned for both days, and speakers and organizers will be available to assist participants with these exercises. Some exercises will be facilitated by numerical software such as Macaulay2, Maple, MATLAB, or Julia. The speakers will also provide participants with a list of research questions to guide their explorations after the course.
This short course is aimed at students with minimal to no background in the theory of SOS polynomials. Familiarity with properties of polyhedra, convex sets, and polynomials will provide useful background. Participants with a desire to experiment with computations and an interest in applications should find this experience especially stimulating.
Participants will find Appendix A in the following book (available for free at the indicated URL) useful preparatory reading:
Semidefinite Optimization and Convex Algebraic Geometry, G. Blekherman, P.A. Parrilo and R.R. Thomas (eds.), MOS-SIAM Series on Optimization, SIAM 2012. (http://www.mit.edu/~parrilo/sdocag/)