The ACO Seminar (2020–2021)

We settle the computational complexity of some fundamental questions about local minima in polynomial optimization. We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c$) of a local minimum of an $n$-variate quadratic program. This result answers a question of Pardalos and Vavasis that appeared in 1992 on a list of seven open problems in complexity theory for numerical optimization. By contrast, through leveraging techniques from algebraic geometry, we show that a local minimum of a cubic polynomial can be found efficiently by semidefinite programming (SDP). We prove that second-order points of cubic polynomials admit an efficient semidefinite representation, even though their critical points are NP-hard to find. We also give an efficiently-checkable necessary and sufficient condition for local minimality of a point for a cubic polynomial.

Please email Boris Bukh (bbukh ~at~ math) for a password.