Complexity of Finding Local Minima in Continuous Optimization

Monday, October 2, 2023 - 4:00pm to 5:00pm

Event Calendar Category

LIDS Seminar Series

Speaker Name

Amir Ali Ahmadi



Building and Room Number



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).


Amir Ali Ahmadi is a Professor at the Department of Operations Research and Financial Engineering at Princeton University and an Associated Faculty member of the Program in Applied and Computational Mathematics, the Department of Computer Science, the Department of Mechanical and Aerospace Engineering, the Department of Electrical Engineering, and the Center for Statistics and Machine Learning. He serves as the Director of the Certificate Program in Optimization and Quantitative Decision Science. He has also held visiting appointments with the industry, as a Visiting Senior Optimization Fellow at Citadel, Global Quantitative Strategies, and a Visiting Research Scientist at Google Brain (in the Robotics group). Amir Ali received his PhD in EECS from MIT and was a Goldstine Fellow at the IBM Watson Research Center prior to joining Princeton. His research interests are in optimization theory, computational aspects of dynamical systems, control-oriented learning, and algorithms and complexity.

Amir Ali's distinctions include the Sloan Fellowship in Computer Science, the Presidential Early Career Award for Scientists and Engineers (PECASE), the NSF CAREER Award, the AFOSR Young Investigator Award, the DARPA Faculty Award, the Google Faculty Award, the MURI award of the AFOSR, the Howard B. Wentz Junior Faculty Award, as well as the Innovation Award of Princeton University, the Goldstine Fellowship of IBM Research, and the Oberwolfach Fellowship of the NSF. His undergraduate course at Princeton (ORF 363, ``Computing and Optimization'') is a three-time recipient of the Teaching Award of the Princeton Engineering Council, as well as a recipient of the Excellence in Teaching of Operations Research Award of the Institute for Industrial and Systems Engineers, the Princeton SEAS Distinguished Teaching Award, and the Phi Beta Kappa Award for Excellence in Undergraduate Teaching at Princeton. Amir Ali's research has been recognized by a number of best-paper awards, including the INFORMS Optimization Society's Young Researchers Prize, the INFORMS Computing Society Prize (for best series of papers at the interface of operations research and computer science), the best conference paper award of the IEEE International Conference on Robotics and Automation, and the best paper prize of the SIAM Journal on Control and Optimization. Amir Ali was a plenary speaker at the 2021 SIAM Conference on Optimization and the 2022 Colombian Conference on Applied and Industrial Mathematics.