On the complexity of finding a local minimizer of a quadratic function over a polytope

• DOI: 10.1007/s10107-021-01714-2
• Publication Date: 2022-01-04T00:03:16Z
• Authors: Amir Ali Ahmadi; Jeffrey Zhang
• Keywords: FOS: Computer and information sciences; Computer Science - Machine Learning; 0211 other engineering and technologies; 0102 computer and information sciences; 02 engineering and technology; Computational Complexity (cs.CC); 90C20 (Primary), 90C30, 90C60 (Secondary); 01 natural sciences; Machine Learning (cs.LG); Computer Science - Computational Complexity; Optimization and Control (math.OC); FOS: Mathematics; Mathematics - Optimization and Control

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 \ge 0$) of a local minimizer of an $n$-variate quadratic function over a polytope. This result (even with $c=0$) answers a question of Pardalos and Vavasis that appeared in 1992 on a list of seven open problems in complexity theory for numerical optimization. Our proof technique also implies that the problem of deciding whether a quadratic function has a local minimizer over an (unbounded) polyhedron, and that of deciding if a quartic polynomial has a local minimizer are NP-hard.<br/>9 pages<br/>