This volume is based on lectures delivered at the 2019 AMS Short Course Sum of Squares: Theory and Applications , held January 14 15, 2019, in Baltimore, Maryland. This book provides a concise state-of-the-art overview of the theory and applications of polynomials that are sums of squares. This is an exciting and timely topic, with rich connections to many areas of mathematics, including polynomial and semidefinite optimization, real and convex algebraic geometry, and theoretical computer science. The six chapters introduce and survey recent developments in this area; specific topics include the algebraic and geometric aspects of sums of squares and spectrahedra, lifted representations of convex sets, and the algorithmic and computational implications of viewing sums of squares as a meta algorithm. The book also showcases practical applications of the techniques across a variety of areas, including control theory, statistics, finance and machine learning.
Author(s): Pablo A. Parrilo, Rekha R. Thomas
Series: Proceedings of Symposia in Applied Mathematics, 77
Publisher: American Mathematical Society
Year: 2020
Language: English
Pages: 153
City: Providence
Cover
Title page
Contents
Preface
A brief introduction to sums of squares
1. Two guiding questions
2. Finding sum of squares decompositions
3. Nonnegative polynomials and sums of squares
4. Sums of squares and optimization
5. Adding constraints
References
The geometry of spectrahedra
1. Introduction
2. Background
3. Convex duality
4. Facial structure, extreme points and ranks
5. Moment problems and sums of squares
References
Lifts of convex sets
1. Introduction
2. Linear programming lifts and Yannakakis’ theorem
3. Semidefinite programming lifts, positive semidefinite factorizations, and sums of squares
4. Conclusion
5. Summary
References
Algebraic geometry and sums of squares
1. Introduction
2. Projective geometry and sums of squares.
3. Main Theorem and the classification of varieties of minimal degree.
References
Sums of squares in theoretical computer science
1. MAXCUT
2. Rounding SOS for MAXCUT
3. Rounding Higher Degree SOS
4. Degree Lower Bounds for Constraint Satisfaction Problems
5. Constructing a Pseudo-Expectation
6. Discussion
References
Applications of sums of squares
Part 1. Dynamical systems and control
1. Certifying properties of a polynomial dynamical system
2. Stability of switched linear systems
3. Related applications
Part 2. Probability and measure theory
4. The moment problem
5. Probability bounds given moments of a random variable and applications to option pricing
Part 3. Statistics and machine learning
6. Shape-constrained regression
7. Optimal design
Part 4. Other applications
8. Optimization
9. Game theory: polynomial games
Part 5. Conclusion: a word on implementation challenges
Acknowledgments
References
Back Cover
