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

DOI10.1007/S10107-021-01714-2zbMath1504.90085arXiv2008.05558OpenAlexW3048750752MaRDI QIDQ2089789

Jeffrey Zhang, Amir Ali Ahmadi

Publication date: 24 October 2022

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/2008.05558

zbMATH Keywords

computational complexitylocal minimizerspolynomial optimizationquadratic programs

Mathematics Subject Classification ID

Quadratic programming (90C20) Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Polynomial optimization (90C23)

Cites Work

• Unnamed Item
• Open questions in complexity theory for numerical optimization
• Checking local optimality in constrained quadratic programming is NP- hard
• Quadratic programming with one negative eigenvalue is NP-hard
• Complexity aspects of local minima and related notions
• On the complexity of detecting convexity over a box
• On the solution of concave knapsack problems
• Quadratic programming is in NP
• Approximation of the Stability Number of a Graph via Copositive Programming
• Some NP-complete problems in quadratic and nonlinear programming
• The polynomial solvability of convex quadratic programming
• Maxima for Graphs and a New Proof of a Theorem of Turán

This page was built for publication: On the complexity of finding a local minimizer of a quadratic function over a polytope