On the complexity of approximating a Karush–Kuhn–Tucker 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 ε ∈ (0, 1) is O((1/ε) log(1/ε) log(log(1/ε))), compared to the previously best-known result O((1/ε)²). Furthermore, the limit of the KKT point satisifies the second-order necessary optimality condition of being a local minimizer.