Organizer(s):

Greg Blekherman, Georgia Institute of Technology

Ankur Moitra, Massachusetts Institute of Technology

Pablo Parrilo, Massachusetts Institute of Technology

Rekha Thomas, University of Washington

Description

COVID-19 Notice: This workshop has been cancelled.

Polynomial optimization concerns optimizing a polynomial subject to polynomial equations and inequalities. A wide variety of problems in the sciences and engineering can be modeled in this way, making both the theory and applications of the topic important and interesting. In recent years, there has been tremendous progress in this field as a result of a merging of tools from classical real algebraic geometry, semidefinite optimization, and the theory of moments. This interdisciplinary field now has strong connections to a wide array of areas such as convex geometry, classical algebraic geometry, and theoretical computer science, with applications to engineering, combinatorics, coding theory, biology, computer vision, and many more. This workshop will explore several topics in and around polynomial optimization, such as the following:

(1) Convex Algebraic Geometry: The semidefinite programming that underlies polynomial optimization is done on semialgebraic convex sets called spectrahedra. Their study naturally leads to a merging of classical methods in (semi) algebraic geometry with the powerful property of convexity, leading to new insights on core issues such as duality, lift-and-project methods for non-convex problems, and the geometry of spectrahedra.

(2) Algebraic Geometry: An intriguing connection is emerging between the geometry of spectrahedra and classical topics in algebraic geometry, such as free resolutions. A recent breakthrough is Scheiderer’s negative answer to the Helton-Nie conjecture, that not every convex, semi-algebraic set is semidefinitely representable.

(3) Theoretical Computer Science: Relaxations to polynomial optimization – most notably semidefinite programming hierarchies – play a key role in theoretical computer science. Recently powerful new rounding algorithms and frameworks to construct integrality gaps have been discovered, but the full range of their implications for approximation algorithms, machine learning, and average-case analysis has yet to be realized.

(4) Applications: The special structure of a problem is often crucial to making progress in both the practical and theoretical understanding of it. Features that have received attention in the past are sparsity and symmetries. These developments have made possible new applications in coding theory, extremal combinatorics, discrete optimization, and control theory, among others. More tools and methods to exploit structure are needed.

(5) Software and Algorithms: Polynomial optimization software is still at its infancy when compared to established areas of optimization. This workshop will include researchers working on developing new algorithms and software in this field. Some exciting new ideas come from looking for alternate methods to semidefinite programming and sums of squares polynomials to model relaxations of polynomial optimization.

Workshop topics will include areas of convex and discrete optimization, semidefinite programming, real and complex algebraic geometry, convex geometry, theoretical computer science, and applications.

Confirmed speakers (so far):

• Gennadiy Averkov, Brandenburg University of Technology
• Dan Bienstock, Columbia University
• Santanu Dey, Georgia Tech
• Cemil Dibek, Princeton University
• Maria Dostert, EPFL
• Mareike Dressler, UC San Diego
• Hamza Fawzi, University of Cambridge
• Georgina Hall, INSEAD
• Sam Hopkins, UC Berkeley
• Lea Kapelevich, MIT
• Riley Murray, Cal Tech
• David Papp, North Carolina State University
• Annie Raymond, University of Massachusetts
• Jim Renegar, Cornell University
• Tselil Schramm, MIT
• Cynthia Vinzant, North Carolina State University
• Alex Wein, NYU

Call For Participation

This event is open to all.

Presented in association with the Special Focus on Bridging Continuous and Discrete Optimization.

Please click here to get information for travel and accomodations information for this event.

Registration is required but not yet open.