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

Amir Ali Ahmadi, Jeffrey Zhang

Research output: Contribution to journalArticlepeer-review

Abstract

We show that unless P=NP, there cannot be a polynomial-time algorithm that finds a point within Euclidean distance cn (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.

Original languageEnglish (US)
JournalMathematical Programming
DOIs
StateAccepted/In press - 2022

All Science Journal Classification (ASJC) codes

  • Software
  • Mathematics(all)

Keywords

  • Computational complexity
  • Local minimizers
  • Polynomial optimization
  • Quadratic programs

Fingerprint

Dive into the research topics of 'On the complexity of finding a local minimizer of a quadratic function over a polytope'. Together they form a unique fingerprint.

Cite this