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.

Intro
A bird's eye view of optimization
Step size too small
Forcing a smart initialization?
Finding a local minimum
Finding a local minimizer of a quadratic program
Stable sets in graphs
Proof outline
What about the unconstrained case?
Finding local minima of cubics Let's start with a simpler question. Can we efficiently find a critical point
Unexpected convexity
Local minima of cubics and SDP
All roads lead to sums of squares
A more complete story
Remainder of the talk
Nonnegativity vs. sum of squares
Nonnegative polynomials that are not SOS?
A new notion: SOS-perfect graphs
Example
An immediate implication
What happens on random graphs?
A challenge for the SOS/SDP community is
Feel the need for more SOS?