On the complexity of approximating a KKT point of quadratic programming

Yinyu Ye

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 $O((1/\epsilon)\log(1/\epsilon)\log(\log(1/\epsilon)))$, 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.