Amir Ali Ahmadi, Princeton University

Abstract

We show that local minimality of a point for a cubic polynomial can be checked in polynomial time. This settles the only case in constrained or unconstrained polynomial optimization where the complexity of testing local optimality was left open by prior literature. We also show that a local minimum of a cubic polynomial can be found by solving polynomially many semidefinite programs of polynomial size. What enables these results is some intriguing geometry and algebra that cubic polynomials give rise to. Joint work with Jeffrey Zhang (Princeton).