The complexity of computing KKT solutions of quadratic programs

DOI10.1145/3745017MaRDI QIDQ6892973zbMATH OpenFDO

Authors John Fearnley, Paul W. Goldberg, Alexandros Hollender, Rahul Savani

Publication date 27 November 2025

Published in Journal of the ACM (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://ora.ox.ac.uk/objects/uuid:ac914c53-69d0-448c-85c1-3a5361a4e176

zbMATH Keywords

continuous local searchKKTquadratic programming

Mathematics Subject Classification ID

Computational difficulty of problems (lower bounds, completeness, difficulty of approximation, etc.) (68Q17) Quadratic programming (90C20) Abstract computational complexity for mathematical programming problems (90C60)

Cites work

• Adaptive global algorithm for solving box-constrained non-convex quadratic minimization problems
• Algorithms for the solution of quadratic knapsack problems
• Approximating quadratic programming with bound and quadratic constraints
• Checking local optimality in constrained quadratic programming is NP- hard
• Complexity aspects of local minima and related notions
• Computationally Related Problems
• Convex optimization: algorithms and complexity
• Finding a Nash equilibrium is no easier than breaking Fiat-Shamir
• Hardness of continuous local search: query complexity and cryptographic lower bounds
• How easy is local search?
• scientific article; zbMATH DE number 6783433 (Why is no real title available?)
• Inapproximability of Nash equilibrium
• Maxima for Graphs and a New Proof of a Theorem of Turán
• On affine scaling algorithms for nonconvex quadratic programming
• On copositive programming and standard quadratic optimization problems
• On Finding and Verifying Locally Optimal Solutions
• On nonconvex quadratic programming with box constraints
• On the complexity of approximating a KKT point of quadratic programming
• On the complexity of finding a local minimizer of a quadratic function over a polytope
• On the Complexity of Nash Equilibria and Other Fixed Points
• On the complexity of the parity argument and other inefficient proofs of existence
• On total functions, existence theorems and computational complexity
• Open questions in complexity theory for numerical optimization
• Quadratic programming is in NP
• Quadratic programming with one negative eigenvalue is NP-hard
• Settling the complexity of computing two-player Nash equilibria
• Settling the complexity of Nash equilibrium in congestion games
• Simultaneous contests with equal sharing allocation of prizes: computational complexity and price of anarchy
• SNARGs for bounded depth computations and PPAD hardness from sub-exponential LWE
• Some NP-complete problems in quadratic and nonlinear programming
• The complexity of approximating a nonlinear program
• The complexity of computing a Nash equilibrium
• The complexity of gradient descent: CLS = PPAD pls
• Two prover protocols, low error at affordable rates

This page was built for publication: The complexity of computing KKT solutions of quadratic programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6892973)