On the complexity of finding a local minimizer of a quadratic function over a polytope
成果类型：
Article
署名作者：
Ahmadi, Amir Ali; Zhang, Jeffrey
署名单位：
Princeton University; Carnegie Mellon University
刊物名称：
MATHEMATICAL PROGRAMMING
ISSN/ISSBN：
0025-5610
DOI：
10.1007/s10107-021-01714-2
发表日期：
2022
页码：
783-792
关键词：
摘要：
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 >= 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.
来源URL：