On the complexity of approximating a KKT point of quadratic programming
We present a potential reduction algorithm to approximate a
Karush-Kuhn-Tucker (KKT) point of general quadratic
programming. We show that the algorithm is a fully polynomial-time
approximation scheme, and its running-time dependency on
accuracy $\epsilon\in (0,1)$ is
compared to the previously best-known result $O((1/\epsilon)^2)$.
Furthermore, the limit of the KKT point satisfies the second-order necessary
optimality condition of being a local minimizer.