Wednesday 22 January

Complexity of Finding Local Minima in Continuous Optimization

Amir Ali Ahmadi – Princeton University, USA

Abstract:

Can we efficiently find a local minimum of a nonconvex continuous optimization problem? We give a rather complete answer to this question for optimization problems defined by polynomial data. In the unconstrained case, the answer remains positive for polynomials of degree up to three: We show that while the seemingly easier task of finding a critical point of a cubic polynomial is NP-hard, the complexity of finding a local minimum of a cubic polynomial is equivalent to the complexity of semidefinite programming. In the constrained case, we prove that unless P=NP, there cannot be a polynomial-​time algorithm that finds a point within Euclidean distance $c^n$ (for any constant $c\geq 0$) of a local minimum of an $n$-​variate quadratic polynomial over a polytope. This result (with $c=0$) answers a question of Pardalos and Vavasis that appeared on a list of seven open problems in complexity theory for numerical optimization in 1992.

Based on joint work with Jeffrey Zhang (Yale).

Registration, please contact robin@em-lyon.com

Room A2-116, Lyon campus