Local Minima, Stable Sets, and Sums of Squares
Explore the complexity of finding local minimizers in polynomial optimization problems through this invited talk from the SIAM Conference on Optimization 2021. Delve into the characterization of problem complexity based on polynomial degrees, examining two key results: the NP-hardness of finding approximate local minimizers for quadratic polynomials over polytopes, and the efficient discovery of local minimizers for cubic polynomials using semidefinite programming. Investigate the connections between stable sets in graph theory and sum of squares polynomials in algebra, leading to an algebraic characterization of perfect graphs. Gain insights into optimization challenges, computational complexity, and the interplay between graph theory and algebraic methods in this comprehensive presentation by Amir Ali Ahmadi from Princeton University.