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.
Next: Call for Participation
Workshop Index
DIMACS Homepage