Complexity of Finding Approximate Critical Points and Local Minima in Continuous Optimization
Can we efficiently find a local minimum of a nonconvex continuous optimization problem? What about a critical point? Does the complexity of these problems change when approximation is allowed? We give a rather complete answer to these questions in the Turing model of computation and for optimization problems defined by polynomial data. This talk will highlight three results that pinpoint sharp transitions in computational complexity as a function of the degree of the input polynomial:
(i) Unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance $2^n$ of a local minimum of an $n$-variate quadratic polynomial over a polytope. This result answers a question of Pardalos and Vavasis that appeared on a list of seven open problems in complexity theory for numerical optimization in 1992.
(ii) Unless P=NP, there cannot be a polynomial-time algorithm that finds a $2^n$-approximate critical point of an $n$-variate cubic polynomial (i.e., a point where the Euclidean norm of the gradient is at most $2^n$).
(iii) In sharp contrast to (ii), the seemingly harder task of computing a local minimum of a cubic polynomial can be carried out by solving semidefinite programs of linear size.
Time permitting, we will also discuss implications of these results for the design of higher-order Newton methods with super-quadratic convergence rates and polynomial work per iteration. Based on joint work with Abraar Chaudhry (Georgia Tech), Georgina Hall (INSEAD), and Jeffrey Zhang (UC Riverside).
Bio: 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 and Computer Engineering, the Center for Statistics and Machine Learning, Robotics, and the AI Lab. He serves as the director of the minor 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 Ph.D. in electrical engineering and computer science 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.